Erdős Problem #597

Erdős Problem 597 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/597

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/597.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/597.tex.

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.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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.