Soukup 2015 trees ladders graphs

../

problem_6_4: Soukup's closing open problem asks whether every uncountably chromatic, or omega_1-chromatic, graph contains an omega-connected subset; by Theorem 3.5 such a set can only be countable in some cases.

theorem_3_5: Soukup's main theorem, proved in ZFC: for a stationary costationary S in omega_1 the comparability graph of the tree T(S) has a subgraph of chromatic number omega_1 with no uncountable omega-connected subset.

theorem_4_3: Soukup's strengthening of Theorem 3.5: G(T(S)) has a subgraph of chromatic number omega_1 in which any two incomparable points of the tree are separated by a finite set, so every uncountable vertex set contains two such points.

theorem_5_5: For stationary S in omega_1, the comparability graph of T(S) has a subgraph of chromatic number omega_1 with no special cycles, hence triangle-free and with no copy of H_{omega,omega+2}; this removes CH from a result of Hajnal and Komjath.

---

Soukup, Dániel T., Trees, ladders and graphs. J. Combin. Theory Ser. B 115 (2015), 96--116. DOI 10.1016/j.jctb.2015.05.004. The copy read for this card is arXiv:1409.2922v1. The arXiv record names arXiv's non-exclusive distribution license (arXiv:1409.2922), every other right reserved.

Labels and pages below are those of arXiv v1 (23 pages); the journal pagination was not compared.

Soukup introduces a construction of uncountably chromatic graphs from non-special trees equipped with ladder systems, and uses it to answer negatively the 1985 Erdos-Hajnal question of whether every graph of chromatic number omega_1 contains an uncountably chromatic omega-connected subgraph. Theorem 3.5 (p. 6) gives, for any stationary costationary S in omega_1 and T = T(S), a subgraph X of G(T) with chromatic number omega_1 containing no uncountable omega-connected subsets; the proof is in plain ZFC with no extra axioms or forcing, unlike Komjath's earlier forcing example. Theorem 4.3 (p. 10) strengthens this: X can be arranged so that any two <T-incomparable vertices are separated by a finite set, hence every uncountable vertex set contains two points joined by only finitely many disjoint paths. Theorem 5.5 (p. 17) gives a second application: for any stationary S, an uncountably chromatic subgraph of G(T(S)) with no special cycles, so in particular triangle-free and containing no copy of H{omega, omega+2}, which removes the Continuum Hypothesis from a result of Hajnal and Komjath. Corollary 2.4 (p. 4) records the starting observation: for a non-special tree T without uncountable chains, G(T) is uncountably chromatic, yet every uncountable vertex set can be separated by a countable set. The paper closes with Problem 6.4 (p. 22), whether every uncountably chromatic (or omega_1-chromatic) graph contains an omega-connected subset, and notes that by Theorem 3.5 such a set can in some cases only be countable, while excluding countable omega-connected subsets seems very hard.

Source: https://arxiv.org/abs/1409.2922.

Read status. Claims checked: Theorems 3.5, 4.3 and 5.5, Problem 6.4 and the definitions and lemmas their pages cite were read clause by clause on the printed pages of arXiv v1. The proofs were not checked.

Bears on. #1067: Theorem 3.5 answers it negatively in ZFC, since its omega_1-chromatic X has no uncountable, hence no uncountably chromatic, omega-connected subgraph; Theorem 4.3 gives a second such example. #1068: the paper does not settle it. Its open Problem 6.4 asks for an omega-connected subset of any size; a positive answer to #1068 would answer the omega_1-chromatic form of Problem 6.4 positively, and for the graph of Theorem 3.5, whose omega-connected subsets are all countable, the two questions coincide.

Results. Theorem 3.5 (p. 6), the ZFC graph of chromatic number omega_1 with no uncountable omega-connected subset; Theorem 4.3 (p. 10), the variant in which incomparable points are separated by finite sets; Theorem 5.5 (p. 17), the omega_1-chromatic graph with no special cycles; Problem 6.4 (p. 22), the open question on omega-connected subsets. Corollary 2.4 (p. 4) is recorded in the digest above.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.