Erdős-Kakutani phenomena for paths
type: Item
instance of: scholarly article
title: Erdős-Kakutani phenomena for paths
zbMATH Open document ID: 1488.05202
published in: Acta Mathematica Hungarica
publication date: 2021-06-29T00:00:00Z
review text: \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.
reviewed by: K. P. Hart
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 03E02
zbMATH DE Number: 7364760
zbMATH Keywords: path
zbMATH Keywords: colouring
zbMATH Keywords: Cohen model
author: Stevo Todorčević
MaRDI profile type: Publication
full work available at URL: s10474-020-01044-3
OpenAlex ID: W3028510799
cites work: Q4083659
cites work: On non-denumerable graphs
cites work: Infinite monochromatic paths and a theorem of Erdős-Hajnal-Rado
cites work: Partitioning Euclidean space
cites work: A partition relation for partially ordered sets
cites work: Q3240242
cites work: Q3739118
cites work: Walks on ordinals and their characteristics
DOI: 10.1007/S10474-020-01044-3
description: scientific article; zbMATH DE number 7364760