Erdős–Dushnik–Miller theorem explained

Erdős–Dushnik–Miller theorem should not be confused with Dushnik–Miller theorem.

In the mathematical theory of infinite graphs, the Erdős–Dushnik–Miller theorem is a form of Ramsey's theorem stating that every infinite graph contains either a countably infinite independent set, or a clique with the same cardinality as the whole graph.

The theorem was first published by, in both the form stated above and an equivalent complementary form: every infinite graph contains either a countably infinite clique or an independent set with equal cardinality to the whole graph. In their paper, they credited Paul Erdős with assistance in its proof. They applied these results to the comparability graphs of partially ordered sets to show that each partial order contains either a countably infinite antichain or a chain of cardinality equal to the whole order, and that each partial order contains either a countably infinite chain or an antichain of cardinality equal to the whole order.

The same theorem can also be stated as a result in set theory, using the arrow notation of, as

	2
\kappa → (\kappa,\alef
	0)

. This means that, for every set

of cardinality

\kappa

, and every partition of the ordered pairs of elements of

into two subsets

P₁

and

P₂

, there exists either a subset

S_1\subsetS

of cardinality

\kappa

or a subset

S_2\subsetS

of cardinality

\alef₀

, such that all pairs of elements of

S_i

belong to

P_i

. Here,

P₁

can be interpreted as the edges of a graph having

as its vertex set, in which

S₁

(if it exists) is a clique of cardinality

\kappa

, and

S₂

(if it exists) is a countably infinite independent set.

is taken to be the cardinal number

\kappa

itself, the theorem can be formulated in terms of ordinal numbers with the notation

\kappa → (\kappa,\omega)²

, meaning that

S₂

(when it exists) has order type

\omega

. For uncountable regular cardinals

\kappa

(and some other cardinals) this can be strengthened to

\kappa → (\kappa,\omega+1)²

; however, it is consistent that this strengthening does not hold for the cardinality of the continuum.

The Erdős–Dushnik–Miller theorem has been called the first "unbalanced" generalization of Ramsey's theorem, and Paul Erdős's first significant result in set theory.