gpt pro 5.2 attempt on Math-5401, version 2

Round 2: extending the structural method from $P_3$ to $P_4$

1) ROUND-2 OBJECTIVE

Path (A): proof-direction. The Round-1 output proved the Erdős--Hajnal conclusion for the special case $H=P_3$ by a full structural characterization (induced-$P_3$-free graphs are disjoint unions of cliques) plus a clique--independent product bound.

In Round 2 I push the same mechanism one notch further: I prove the conjectured polynomial conclusion for the next natural induced-path obstruction \[H=P_4,\] namely for induced-$P_4$-free graphs (cographs). This is a genuine strengthening beyond Round 1, and it stays aligned with the "structural decomposition $\Rightarrow$ product bound" strategy.

2) ROUND-1 FOUNDATION USED

I rely on the following vetted Round-1 items (no reproving):

• Round-1 Lemma 1: induced-$P_3$-free graphs are disjoint unions of cliques.
• Round-1 Lemma 2: for a disjoint union of cliques on $n$ vertices, $\alpha(G)\,\omega(G)\ge n$, hence $\max\{\alpha(G),\omega(G)\}\ge \sqrt n$.
• Round-1 "next moves" suggestion: treat induced-$P_4$-free graphs (cographs) via a structural characterization.

3) NEW INSIGHT / TOOL (ROUND-2)

The new ingredient is the cograph (induced-$P_4$-free) decomposition:

Every induced-$P_4$-free graph is obtained from $K_1$ by repeatedly taking disjoint unions and joins.

Equivalently (Seinsche's theorem), every induced-$P_4$-free graph on at least two vertices is either disconnected, or its complement is disconnected.

The second new ingredient is a strengthening of Round-1 Lemma 2:

The product inequality $\alpha(G)\,\omega(G)\ge |V(G)|$ holds for all cographs, not just for disjoint unions of cliques.

The proof uses that this inequality is preserved by both disjoint union and join.

4) ATTACK PLAN (ROUND-2)

Round-1 gap addressed: Round 1 solved only $H=P_3$.

Claims to prove in Round 2:

1. (Structure) If $G$ is induced-$P_4$-free and connected with $|V(G)|\ge 2$, then $\overline G$ is disconnected. Equivalently, every induced-$P_4$-free graph is disconnected or co-disconnected.
2. (Closure + recursion) Induced-$P_4$-free graphs are exactly those built from $K_1$ by disjoint unions and joins.
3. (Quantitative bound) For every induced-$P_4$-free $G$ on $n$ vertices, $\alpha(G)\omega(G)\ge n$, hence $\max\{\alpha(G),\omega(G)\}\ge \sqrt n$. In particular, Erdős--Hajnal holds for $H=P_4$ with exponent $c(P_4)=\tfrac12$.

5) WORK (ROUND-2)

Notation.

$P_k$ denotes the path on $k$ vertices. A graph is $P_4$-free if it has no induced subgraph isomorphic to $P_4$. Write $G=G_1\uplus G_2$ for a disjoint union (no edges between parts) and $G=G_1*G_2$ for the join (add all edges between the parts).

Fact 0 (self-complementarity of $P_4$).

The complement of $P_4$ is isomorphic to $P_4$. Consequently, $G$ is $P_4$-free iff $\overline G$ is $P_4$-free.

Justification. Label $P_4$ as $1$--$2$--$3$--$4$. In $\overline{P_4}$ the edges are $13,14,24$, which form the path $3$--$1$--$4$--$2$. $\square$

Lemma 1 (Seinsche-type decomposition for $P_4$-free graphs).

Let $G$ be a connected $P_4$-free graph on $n\ge 2$ vertices. Then there exists a nontrivial partition $V(G)=A\cup B$ with $A,B\neq\emptyset$ such that every vertex of $A$ is adjacent to every vertex of $B$. In particular, $\overline G$ is disconnected.

Proof (induction on $n$). For $n\le 3$ this is a direct check: $K_2$, $P_3$, and $K_3$ each admit a nontrivial partition $A,B$ with all edges between $A$ and $B$.

Assume $n\ge 4$ and the statement holds for smaller connected $P_4$-free graphs. Fix a spanning tree $T$ of $G$, and let $x$ be a leaf of $T$ with neighbor $u$ in $T$. Then $G-x$ is connected. Since $G$ is $P_4$-free, so is the induced subgraph $G-x$. By the induction hypothesis applied to $G-x$, there is a partition \[V(G)\setminus\{x\}=A\cup B,\qquad A,B\neq\emptyset,\qquad \text{and } A\text{ is complete to }B.\] Without loss of generality, $u\in A$.

If $x$ is adjacent to every vertex of $B$, then $(A\cup\{x\},B)$ is the desired complete-join partition. So assume instead that $x$ has a non-neighbor $z\in B$. Define \[A_1:=A\cap N(x),\qquad A_0:=A\setminus A_1.\] Note that $u\in A_1$, hence $A_1\neq\emptyset$. If $A_0=\emptyset$, then $x$ is adjacent to all of $A$, and $(A,B\cup\{x\})$ is a complete-join partition. So assume $A_0\neq\emptyset$.

We claim that $A_1$ is complete to $A_0$. Indeed, take any $y\in A_1$ and any $w\in A_0$. We have

• $x$ is adjacent to $y$ (by definition of $A_1$),
• $y$ is adjacent to $z$ (since $y\in A$ and $z\in B$ and $A$ is complete to $B$),
• $z$ is adjacent to $w$ (since $w\in A$ and again $A$ is complete to $B$),
• $x$ is nonadjacent to $z$ (choice of $z\in B\setminus N(x)$),
• $x$ is nonadjacent to $w$ (since $w\in A_0=A\setminus N(x)$).

Thus, if $y$ were nonadjacent to $w$, the induced subgraph on $\{x,y,z,w\}$ would be exactly the path \[x-y-z-w,\] contradicting that $G$ is $P_4$-free. Hence $y$ must be adjacent to $w$ for all such choices, so $A_1$ is complete to $A_0$.

Now observe that every vertex of $A_1$ is adjacent to: (i) $x$ (by definition of $A_1$), (ii) $A_0$ (as just proved), and (iii) $B$ (since $A$ is complete to $B$). Therefore $A_1$ is complete to $V(G)\setminus A_1$. Taking the partition $(A_1,\,V(G)\setminus A_1)$ proves the lemma. $\square$

Corollary 2 (recursive description of $P_4$-free graphs).

A graph $G$ is $P_4$-free if and only if it can be generated from $K_1$ by repeatedly applying disjoint union $\uplus$ and join $*$.

Proof. The "if" direction: $P_4$-freeness is preserved under induced subgraphs, under disjoint union, and under join (a $P_4$ cannot use vertices from both sides of a join because that would create a vertex of degree $3$ in the induced subgraph). Also $K_1$ is $P_4$-free.

For the "only if" direction, proceed by induction on $n=|V(G)|$. If $n=1$, $G=K_1$. If $n\ge 2$ and $G$ is disconnected, write $G=G_1\uplus G_2$ with both parts nonempty (partition the components into two nonempty groups) and apply induction to each $G_i$. If $G$ is connected, apply Lemma 1 to obtain a nontrivial partition $V(G)=A\cup B$ such that $A$ is complete to $B$, i.e. $G=G[A]*G[B]$. Both induced subgraphs $G[A],G[B]$ are $P_4$-free and smaller, so induction applies. $\square$

Lemma 3 (clique/independence under $\uplus$ and $*$).

Let $G_1,G_2$ be graphs.

1. If $G=G_1\uplus G_2$, then \[\alpha(G)=\alpha(G_1)+\alpha(G_2),\qquad \omega(G)=\max\{\omega(G_1),\omega(G_2)\}.\]
2. If $G=G_1*G_2$, then \[\alpha(G)=\max\{\alpha(G_1),\alpha(G_2)\},\qquad \omega(G)=\omega(G_1)+\omega(G_2).\]

Proof. $1$ In a disjoint union, an independent set may be chosen independently in each component, while a clique must lie entirely within one component.

$2$ In a join, every vertex of $G_1$ is adjacent to every vertex of $G_2$, so cliques add across parts; an independent set cannot use vertices from both parts. $\square$

Lemma 4 (product bound for cographs).

If $G$ is $P_4$-free on $n$ vertices, then \[\alpha(G)\,\omega(G)\ge n.\] Consequently, $\max\{\alpha(G),\omega(G)\}\ge \sqrt n$.

Proof (induction on $n$ using Corollary 2). For $n=1$, $\alpha=\omega=1$. Assume $n\ge 2$ and the claim holds for smaller $P_4$-free graphs. By Corollary 2, write $G$ as either a disjoint union $G_1\uplus G_2$ or a join $G_1*G_2$ of two nonempty $P_4$-free graphs on $n_1,n_2$ vertices. By induction, $\alpha(G_i)\,\omega(G_i)\ge n_i$.

Disjoint union case. Using Lemma 3$1$, let $\omega(G)=\max\{\omega_1,\omega_2\}$ and wlog $\omega_1\ge \omega_2$. Then \[ \alpha(G)\omega(G)=(\alpha_1+\alpha_2)\omega_1\ge \alpha_1\omega_1+\alpha_2\omega_2\ge n_1+n_2=n. \]

Join case. Using Lemma 3$2$, let $\alpha(G)=\max\{\alpha_1,\alpha_2\}$ and wlog $\alpha_1\ge \alpha_2$. Then \[ \alpha(G)\omega(G)=\alpha_1(\omega_1+\omega_2)\ge \alpha_1\omega_1+\alpha_2\omega_2\ge n_1+n_2=n. \]

Finally, $\max\{\alpha,\omega\}\ge \sqrt{\alpha\omega}\ge \sqrt n$. $\square$

Proved special case (new in Round 2): $H=P_4$.

For $H=P_4$, the Erdős--Hajnal conclusion holds with exponent $c(P_4)=\tfrac12$: any induced-$P_4$-free graph $G$ on $n$ vertices has a clique or independent set of size at least $\sqrt n$.

Tightness.

The exponent $\tfrac12$ is best possible (up to rounding) even within cographs: if $n=m^2$, take $G$ to be the disjoint union of $m$ cliques of size $m$. Then $G$ is $P_4$-free (already induced-$P_3$-free by Round-1 Lemma 1), and \[\omega(G)=m,\qquad \alpha(G)=m,\qquad \max\{\alpha(G),\omega(G)\}=\sqrt n.\]

6) ADVERSARIAL VERIFICATION

• Base cases in Lemma 1. For $n\le 3$, connected graphs are $K_2,P_3,K_3$, and each has an explicit nontrivial complete-join partition.
• Induction step in Lemma 1. The spanning-tree leaf $x$ ensures $G-x$ is connected. The dichotomy "$x$ adjacent to all of $B$" or not is exhaustive; in the "not" case, the construction of $\{x,y,z,w\}$ uses $z\in B\setminus N(x)$ and $w\in A\setminus N(x)$, both ensured by the corresponding branches.
• Inducedness of the $P_4$ in Lemma 1. The only potentially problematic extra edge in the candidate path $x-y-z-w$ is $yw$; forcing $yw$ to be present is exactly what prevents the induced $P_4$, and yields the final join partition.
• Corollary 2 closure under join. Any four-vertex induced subgraph meeting both sides of a join has a vertex adjacent to all vertices on the other side, forcing degree $\ge 3$ in the induced subgraph, hence cannot be $P_4$.
• Product inequality algebra. In Lemma 4, the key inequalities are monotonicity: if $\omega_1\ge\omega_2$ then $\alpha_2\omega_1\ge\alpha_2\omega_2$, and if $\alpha_1\ge\alpha_2$ then $\alpha_1\omega_2\ge\alpha_2\omega_2$.
• Consistency with Round 1. Disjoint unions of cliques are cographs, and Lemma 4 reduces to Round-1 Lemma 2 in that subfamily; thus Round 2 strictly extends the Round-1 quantitative mechanism.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Beyond the Round-1 special case $H=P_3$, Round 2 proves the Erdős--Hajnal polynomial conclusion for the larger obstruction $H=P_4$ (cographs), with an explicit sharp exponent $c(P_4)=\tfrac12$. The full Erdős--Hajnal conjecture for general fixed $H$ remains open.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 35%

9) REFERENCES

Only sources actually used/checked in Round 2:

• D. Seinsche, On a property of the class of $n$-colorable graphs, J. Combin. Theory Ser. B 16 $1974$, 191--193. (Classical source for the "$P_4$-free $\Rightarrow$ disconnected or co-disconnected" property.)
• M. G. S. Chung and D. B. West, Large $P_4$-free graphs with bounded degree, Journal of Graph Theory 17 $1993$, 109--116. (Contains a short inductive proof of Seinsche's property, used as a consistency check.)