Erdős-Kakutani phenomena for paths (Q2036602)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Erdős-Kakutani phenomena for paths |
scientific article |
Statements
Erdős-Kakutani phenomena for paths (English)
0 references
29 June 2021
0 references
\textit{P. Erdős} and \textit{S. Kakutani} [Bull. Am. Math. Soc. 49, 457--461 (1943; Zbl 0063.01275)] proved that a complete graph can be decomposed into countably many trees (acyclic subgraphs) if and only if the vertex set has cardinality at most \(\aleph_1\).\par The author shows that the same bound is obtained if one wants to decompose a complete graph into countably many graphs with no infinite paths, in particular: every colouring \(c:[\omega_2]^2\to\omega\) is constant on the set of edges of an infinite path. It is, naturally, harder to make the homogeneous paths increasing with respect to the natural order on the ordinal in question: if \(\alpha<\mathfrak{c}^+\) then there is a colouring \(c[\alpha]^2\to\omega\) such that every increasing path with at least two edges uses at least two colours. The final result shows that in the Cohen model every countable colouring of the complete graph on \(\omega_2\) has an infinite path that takes on at most two colours.
0 references
path
0 references
colouring
0 references
Cohen model
0 references