gpt pro 5.2 attempt on Math-866

For which graphs $G_1,G_2$ is it true that {UL} {LI} for every $n\geq 1$ there is a graph $H$ without a $G_1$ but if the edges of $H$ are $n$-coloured then there is a monochromatic copy of $G_2$, and yet{/LI} {LI} for every graph $H$ without a $G_1$ there is an $\aleph_0$-colouring of the edges of $H$ without a monochromatic $G_2$. {/UL} Erdős and Hajnal originally conjectured that there are no such $G_1,G_2$, but in fact $G_1=C_4$ and $G_2=C_6$ is an example. Indeed, for this pair Nešetřil and Rödl established the first property and Erdős and Hajnal the second (in fact every $C_4$-free graph is a countable union of trees). Whether this is true for $G_1=K_4$ and $G_2=K_3$ is the content of [595] .

FORMAL RESTATEMENT

Fix finite graphs $G_1,G_2$. Consider the two properties:

1. $P1$ For every integer $n\ge 1$, there exists a graph $H$ which is $G_1$-free (contains no copy of $G_1$) such that for every edge-colouring $\kappa:E(H)\to[n]$ there exists a monochromatic copy of $G_2$ in $H$.
2. $P2$ For every $G_1$-free graph $H$, there exists an edge-colouring $\kappa:E(H)\to\omega$ such that $H$ has no monochromatic copy of $G_2$.

Problem: classify the pairs $(G_1,G_2)$ for which both $P1$ and $P2$ hold. The statement notes that $(G_1,G_2)=(C_4,C_6)$ is such a pair.

QUICK LITERATURE/CONTEXT CHECK

I will not import external results beyond what is explicitly stated in the problem text. The text asserts that $(C_4,C_6)$ satisfies $P1$ (due to Nešetřil--Rödl) and $P2$ (due to Erdős--Hajnal), and even notes a strengthening: every $C_4$-free graph is a countable union of trees. The general classification problem is open-ended.

ATTACK PLAN

Understanding $P2$. Rewrite $P2$ as a countable decomposition problem: a countable edge-colouring avoiding monochromatic $G_2$ is the same as writing $E(H)$ as a countable union of $G_2$-free subgraphs. Seek structural reasons why $G_1$-freeness might force such a decomposition (as for $C_4$-free graphs being a countable union of trees).

Understanding $P1$. $P1$ is a "Folkman-type" property: for each finite $n$, some $G_1$-free graph is edge-Ramsey for $G_2$ under $n$ colours. Try to understand which $(G_1,G_2)$ admit such finite-colour Ramsey obstructions.

I did not obtain a classification. I provide a few rigorous equivalences and structural lemmas relevant to the stated example $(C_4,C_6)$.

WORK

FAST REALITY CHECK (the example $(C_4,C_6)$ for $n=1$)

For $n=1$, property $P1$ for $(C_4,C_6)$ asks for a $C_4$-free graph $H$ such that any 1-colouring (i.e. no colouring choice) contains a monochromatic $C_6$, i.e. simply $H$ contains a $C_6$. Taking $H=C_6$ works and is $C_4$-free. For $n\ge 2$ the existence of such $H$ is nontrivial and is attributed in the problem text to Nešetřil--Rödl.

Lemma 1 (reformulating $P2$ as a decomposition). Fix graphs $G_1,G_2$. For a $G_1$-free graph $H=(V,E)$, the following are equivalent:

1. There exists an edge-colouring $\kappa:E\to\omega$ with no monochromatic copy of $G_2$.
2. The edge-set $E$ can be written as a countable union $E=\bigcup_{n<\omega} E_n$ such that each subgraph $(V,E_n)$ is $G_2$-free.

Proof. $1$$\Rightarrow$$2$: Let $E_n:=\kappa^{-1}(\{n\})$. Then $E=\bigcup_n E_n$. If some $(V,E_n)$ contained a copy of $G_2$, that copy would be monochromatic of colour $n$, contradicting $1$.

$2$$\Rightarrow$$1$: Given $E=\bigcup_n E_n$ with each $(V,E_n)$ $G_2$-free, define a colouring $\kappa$ by $\kappa(e)=\min\{n:e\in E_n\}$. Then for each $n$, the colour class $\kappa^{-1}(\{n\})$ is a subgraph of $(V,E_n)$ and hence is $G_2$-free. Therefore there is no monochromatic copy of $G_2$.$\square$

Lemma 2 (countable union of trees suffices to avoid monochromatic cycles). Let $H=(V,E)$ be a graph. If $E$ is a countable union of edge-sets each of which forms a forest (in particular a tree), then $H$ has an $\aleph_0$-edge-colouring with no monochromatic cycle. In particular, it has an $\aleph_0$-edge-colouring with no monochromatic $C_6$.

Proof. Assume $E=\bigcup_{n<\omega}E_n$ where each $(V,E_n)$ is a forest. Colour every edge $e\in E_n$ with colour $n$ using the "least index" rule to make it a genuine colouring (as in Lemma lem:P2_decomp). For each $n$, the colour class is a subgraph of a forest, hence is a forest, hence contains no cycles of any length. Therefore no cycle (and in particular no $6$-cycle) can be monochromatic.$\square$

Lemma 3 (a basic structural property of $C_4$-free graphs). If a graph $H$ is $C_4$-free, then any two distinct vertices have at most one common neighbour.

Proof. Let $u\neq v$ be vertices. Suppose, for contradiction, that $u$ and $v$ have two distinct common neighbours $x\neq y$. Then the four distinct vertices $u,x,v,y$ form a 4-cycle \[ u-x-v-y-u \] because the edges $ux,xv,vy,yu$ all exist by "common neighbour". This is a copy of $C_4$ in $H$, contradicting that $H$ is $C_4$-free. Therefore $u$ and $v$ have at most one common neighbour.$\square$

VERIFICATION

• Lemma lem:P2_decomp is purely about re-encoding a cover as a colouring (and conversely). It matches the formulation of $P2$.
• Lemma lem:trees_avoid_cycles correctly implies the $C_4,C_6$ example's $P2$ provided we accept the problem-text claim "every $C_4$-free graph is a countable union of trees".
• Lemma lem:C4_codegree checks the standard implication from two common neighbours to a (not-necessarily-induced) 4-cycle.

FINAL

UNRESOLVED

(i) Strongest proved partial result. Property $P2$ for a pair $(G_1,G_2)$ is equivalent to: every $G_1$-free graph is a countable union of $G_2$-free subgraphs (Lemma lem:P2_decomp). In the example $(C_4,C_6)$, the further sufficient condition "countable union of trees" indeed implies $P2$ (Lemma lem:trees_avoid_cycles).

(ii) First gap (crisp). Give a structural characterization of pairs $(G_1,G_2)$ for which both $P1$ and $P2$ hold. Even for specific natural pairs beyond $(C_4,C_6)$ (e.g. $(K_4,K_3)$, which is Problem 595), no classification is established here.

(iii) Top 3 next moves.

1. Systematically analyze $P2$ as an "arboricity-type" condition: for which $G_1$ does $G_1$-freeness force countable decomposition into $G_2$-free graphs? Try first when $G_2$ is a cycle.
2. For $P1$, attempt to identify which $G_2$ admit $n$-colour edge-Ramsey obstructions inside $G_1$-free graphs (a generalization of Folkman-type existence).
3. Explore whether $P2$ can ever hold when $G_2$ is a clique (e.g. $K_3$) and $G_1$ is also a clique (e.g. $K_4$), by seeking either a decomposition theorem or a transfinite counterexample.

(iv) Minimal counterexample structure. To refute a proposed classification, one would need either: (a) a pair $(G_1,G_2)$ where for every $n$ there exists a $G_1$-free graph $H$ that is edge-Ramsey for $G_2$ under $n$ colours, but some $G_1$-free graph admits no countable decomposition into $G_2$-free subgraphs; or (b) a pair where $P2$ always holds but $P1$ fails for some $n$. For clique pairs like $(K_4,K_3)$, any counterexample must be uncountable and have triangles spread so that every countable edge-colouring traps a monochromatic triangle.