gpt pro 5.2 attempt on Math-867

Let $G$ be a graph on at most $\aleph_1$ vertices which contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite graph with $\aleph_0$ vertices in each class). Is it true that\[\omega_1^2 \to (\omega_1\omega, G)^2?\] What about finite $G$? Erdős and Hajnal proved that $\omega_1^2 \to (\omega_1\omega,3)^2$. Erdős originally asked this with just the assumption that $G$ is $K_4$-free, but Baumgartner proved that $\omega_1^2 \not\to (\omega_1\omega, K_{\aleph_0,\aleph_0})^2$.

1) FORMAL RESTATEMENT

We interpret $\omega_1$ as the first uncountable ordinal and $\omega_1^2$ as the ordinal product $\omega_1\cdot\omega_1$. Likewise $\omega_1\omega$ denotes $\omega_1\cdot\omega$.

Fix a (simple, undirected) graph $G=(V(G),E(G))$ with $|V(G)|\le\aleph_1$ such that $G$ has no subgraph isomorphic to $K_4$ and no subgraph isomorphic to $K_{\aleph_0,\aleph_0}$.

For ordinals $\alpha,\beta$ and a graph $G$, we take \[ \alpha\to(\beta,G)^2 \] to mean: for every graph $H=(\alpha,E_H)$ on vertex set $\alpha$, either

• there exists an independent set $I\subseteq\alpha$ such that $H[I]$ has no edges and the order type of $I$ (with the inherited well-order) is exactly $\beta$, or
• there exists an injection $f:V(G)\to\alpha$ such that for every edge $\{u,v\}\in E(G)$ we have $\{f(u),f(v)\}\in E_H$ (so $H$ contains a subgraph isomorphic to $G$).

Ambiguity note. If one instead requires an induced copy of $G$ in the second bullet, then even a clique of size $|V(G)|$ would not necessarily contain $G$. The surrounding discussion ("contains no $K_4$") strongly suggests "subgraph" rather than "induced subgraph", and we adopt "subgraph".

Stress points: the order types $\omega_1^2$ and $\omega_1\omega$; the forbidden subgraphs $K_4$ and $K_{\aleph_0,\aleph_0}$; and whether $G$ is finite vs size $\aleph_1$.

2) QUICK LITERATURE/CONTEXT CHECK

To comply with the integrity rule (no external literature claims beyond what is in the problem statement), we record only what is stated above: Erdős--Hajnal proved $\omega_1^2\to(\omega_1\omega,3)^2$, and Baumgartner proved $\omega_1^2\not\to(\omega_1\omega,K_{\aleph_0,\aleph_0})^2$.

3) ATTACK PLAN

• Proof-track idea: attempt to extend the Erdős--Hajnal argument for "3" (a triangle) to larger target graphs under the additional hypothesis that $G$ itself omits $K_4$ and $K_{\aleph_0,\aleph_0}$. In particular, try to show that any counterexample graph $H$ must encode either a $K_4$ or a $K_{\aleph_0,\aleph_0}$ inside $G$.
• Disproof-track idea: try to adapt Baumgartner-type colourings of $[\omega_1^2]^2$ that kill $\omega_1\omega$-independent sets while avoiding a prescribed $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$.

I did not find a full proof or counterexample; the WORK below gives reductions and small sanity checks.

4) WORK

Fast reality check (tiny finite $G$). If $|V(G)|\le 1$ then any graph contains $G$ trivially, so the relation holds. If $|V(G)|=2$ then any graph with at least one edge contains $K_2$ and any graph with no edges has large independent sets; in the partition statement the interesting case is $|V(G)|\ge 3$.

Lemma 597.1 (monotonicity in the target graph).
Let $\alpha,\beta$ be ordinals and let $G,H$ be graphs. If $G$ is a subgraph of $H$ and $\alpha\to(\beta,H)^2$ holds, then $\alpha\to(\beta,G)^2$ holds.

Proof. Assume $\alpha\to(\beta,H)^2$. Take an arbitrary graph $F=(\alpha,E_F)$. By $\alpha\to(\beta,H)^2$, either (a) $F$ has an independent set of order type $\beta$, in which case $\alpha\to(\beta,G)^2$ is satisfied, or (b) $F$ contains a subgraph isomorphic to $H$. In case (b), since $G$ is a subgraph of $H$, any copy of $H$ in $F$ contains a copy of $G$ (compose the inclusion map $G\hookrightarrow H$ with the embedding of $H$ into $F$). Thus $F$ contains $G$. Since $F$ was arbitrary, $\alpha\to(\beta,G)^2$ holds. $\square$

Lemma 597.2 (finite reduction to cliques).
Let $n\in\mathbb{N}$ and let $G$ be any graph with $|V(G)|\le n$. If $\alpha\to(\beta,n)^2$ (i.e., $\alpha\to(\beta,K_n)^2$) holds, then $\alpha\to(\beta,G)^2$ holds.

Proof. Assume $\alpha\to(\beta,K_n)^2$. Let $F=(\alpha,E_F)$ be an arbitrary graph. If $F$ has an independent set of order type $\beta$ we are done. Otherwise, by $\alpha\to(\beta,K_n)^2$, $F$ contains a copy of $K_n$ as a subgraph. Any graph $G$ on at most $n$ vertices is a subgraph of $K_n$: fix an injection from $V(G)$ into $V(K_n)$ and note that every edge of $G$ maps to an edge of $K_n$. Therefore the copy of $K_n$ in $F$ contains a copy of $G$. Hence $F$ contains $G$, as required. $\square$

Corollary 597.3 (all graphs on at most three vertices).
For every graph $G$ with $|V(G)|\le 3$, we have \[ \omega_1^2\to(\omega_1\omega,G)^2. \]

Proof. The given statement includes $\omega_1^2\to(\omega_1\omega,3)^2$, i.e., $\omega_1^2\to(\omega_1\omega,K_3)^2$. Apply Lemma 597.2 with $n=3$ and $\alpha=\omega_1^2$, $\beta=\omega_1\omega$. $\square$

5) VERIFICATION

• Lemma 597.2 crucially uses the "subgraph" (not "induced subgraph") reading of "contains $G$". Under an induced-copy reading, the lemma is false unless $G$ itself is complete.
• The corollary for $|V(G)|\le 3$ uses only the stated Erdős--Hajnal fact and Lemma 597.2.
• Edge cases: if $|V(G)|<3$, the statement is even easier (any graph contains $K_1$; graphs with edges contain $K_2$; otherwise independent sets exist).

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. For every graph $G$ with $|V(G)|\le 3$, one has $\omega_1^2\to(\omega_1\omega,G)^2$ (Corollary 597.3). More generally, if $\omega_1^2\to(\omega_1\omega,K_n)^2$ held for some finite $n$, then the same relation would hold for every $n$-vertex graph $G$ (Lemma 597.2).

(ii) First gap (crisp). Decide (prove or refute) $\omega_1^2\to(\omega_1\omega,K_4)^2$ or even $\omega_1^2\to(\omega_1\omega,G)^2$ for a single explicit $4$-vertex graph $G$ (e.g., $C_4$) under the additional hypothesis that $G$ is $K_4$-free and $K_{\aleph_0,\aleph_0}$-free.

(iii) Top 3 next moves.

1. Try to prove a "triangle-amplification" lemma: under the hypothesis that $H$ has no independent set of order type $\omega_1\omega$, show that $H$ must contain many edge-disjoint triangles arranged to embed a fixed finite $K_4$-free graph.
2. Attempt to explicitly adapt Baumgartner-type colourings on $[\omega_1^2]^2$ to avoid a given $K_4$-free, $K_{\aleph_0,\aleph_0}$-free $G$ while still killing $\omega_1\omega$-independent sets.
3. As a computational sanity check for the finite-$G$ subcase, isolate the smallest finite $G$ (by number of vertices/edges) for which existing methods fail, and try to force a copy from weaker partition relations (e.g., reductions to $n=4$ cliques).

(iv) What a minimal counterexample would look like. A counterexample would be a graph $H$ on vertex set $\omega_1^2$ such that (a) $H$ contains no independent set of order type $\omega_1\omega$, and (b) $H$ avoids a fixed $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$ as a subgraph.