Unfriendly partition

In the mathematics of infinite graphs, an unfriendly partition or majority coloring is a partition of the vertices of the graph into disjoint subsets, so that every vertex has at least as many neighbors in other sets as it has in its own…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In the mathematics of infinite graphs, an unfriendly partition or majority coloring is a partition of the vertices of the graph into disjoint subsets, so that every vertex has at least as many neighbors in other sets as it has in its own set. It is a generalization of the concept of a maximum cut for finite graphs, which is automatically an unfriendly partition.

(If not, a vertex with more neighbors in its own set could be moved to the other set, increasing the number of cut edges.) The unfriendly partition conjecture is an unsolved problem asking whether every countable graph has an unfriendly partition into two subsets.

Robert H. Cowan and William R. Emerson, in unpublished work, conjectured that every infinite graph has an unfriendly partition into two subsets. However, Saharon Shelah and Eric Charles Milner disproved the conjecture, showing that uncountable graphs might not have two-subset unfriendly partitions. Nevertheless, they showed that an unfriendly partition into three subsets always exists.…

In the mathematics of infinite graphs, an unfriendly partition or majority coloring is a partition of the vertices of the graph into disjoint subsets, so that every vertex has at least as many neighbors in other sets as it has in its own set. It is a generalization of the concept of a maximum cut for finite graphs, which is automatically an unfriendly partition.

(If not, a vertex with more neighbors in its own set could be moved to the other set, increasing the number of cut edges.) The unfriendly partition conjecture is an unsolved problem asking whether every countable graph has an unfriendly partition into two subsets.

Robert H. Cowan and William R. Emerson, in unpublished work, conjectured that every infinite graph has an unfriendly partition into two subsets. However, Saharon Shelah and Eric Charles Milner disproved the conjecture, showing that uncountable graphs might not have two-subset unfriendly partitions. Nevertheless, they showed that an unfriendly partition into three subsets always exists.

Among countable graphs, the existence of a two-subset unfriendly partition is known for the following special cases: Graphs that have finitely many vertices of infinite degree Graphs in which all vertices have infinite degree, by an argument using the back-and-forth method Graphs with no end Graphs without a subdivision of an infinite clique The case for arbitrary countable graphs remains open.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362335070 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001362335070 · captured 1783058554.0 · version history

Cite this page as: encyclopegia.org, “Unfriendly partition”, snapshot enwiki-001362335070. https://encyclopegia.org/a/unfriendly-partition

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.