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
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references