gpt pro 5.2 attempt on Math-5401

For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either a complete graph or independent set on $\geq n^c$ vertices? Conjectured by Erdős and Hajnal [ErHa89], who proved that a complete graph or independent set must exist on\[\geq \exp(c_H\sqrt{\log n})\]many vertices, where $c_H>0$ is some constant. This was improved by Bucić, Nguyen, Scott, and Seymour [BNSS23] to\[\geq \exp(c_H\sqrt{\log n\log\log n}).\]See also the entry in the graphs problem collection . References [BNSS23] BuciĆ, M. and Nguyen, T. and Scott, A. and Seymour, P., A loglog step towards Erdos-Hajnal . arXiv:2301.10147 $2023$. [ErHa89] Erdős, P. and Hajnal, A., Ramsey-type theorems . Discrete Appl. Math. $1989$, 37-52.

FORMAL RESTATEMENT

Fix a finite simple graph $H$. A graph $G$ is induced-$H$-free if no subset of vertices of $G$ induces a subgraph isomorphic to $H$. Let $\omega(G)$ denote the clique number and $\alpha(G)$ the independence number.

Erdős--Hajnal conjecture: For every fixed $H$ there exists a constant $c(H)>0$ such that for all $n\in\mathbb{N}$, any induced-$H$-free graph $G$ on $n$ vertices satisfies \[ \max\{\omega(G),\alpha(G)\}\ge n^{c(H)}. \]

QUICK LITERATURE/CONTEXT CHECK

Only what is explicitly stated in the problem statement is treated as context: Erdős and Hajnal proved the weaker bound $\max\{\omega,\alpha\}\ge \exp(c_H\sqrt{\log n})$ for some $c_H>0$, and a 2023 result of Bucić--Nguyen--Scott--Seymour improves this to $\exp(c_H\sqrt{\log n\log\log n})$. No other external results are assumed.

ATTACK PLAN

• Since the full conjecture is open, aim for fully proved nontrivial special cases (specific $H$) that illustrate the mechanism.
• For a small $H$, try to characterize induced-$H$-free graphs structurally and then bound $\alpha$ or $\omega$.
• Do tiny $n$ computations for the chosen $H$ as sanity checks.

I work out a complete proof for the special case $H=P_3$ (the 3-vertex path).

WORK

Let $P_3$ be the path on 3 vertices (two edges in a row).

Lemma 1 (Induced-$P_3$-free graphs are disjoint unions of cliques). If a graph $G$ has no induced subgraph isomorphic to $P_3$, then every connected component of $G$ is a clique. Equivalently, $G$ is a disjoint union of complete graphs.

Proof. Assume for contradiction that some connected component $C$ of $G$ is not a clique. Then there exist vertices $u,w\in V(C)$ that are not adjacent. Because $C$ is connected, there exists a $u$--$w$ path in $C$. Choose a shortest such path and write it as $u=v_0,v_1,\dots,v_t=w$. Since $u$ and $w$ are nonadjacent, $t\ge 2$. Now consider the three vertices $v_0,v_1,v_2$. By construction, $v_0v_1$ and $v_1v_2$ are edges. Because the path is shortest, $v_0v_2$ cannot be an edge (otherwise $u=v_0,v_2,\dots,w$ would be a shorter $u$--$w$ path). Thus the induced subgraph on $\{v_0,v_1,v_2\}$ is exactly $P_3$, contradicting that $G$ is induced-$P_3$-free. Therefore each component is a clique. $\square$

Lemma 2 (Clique--independent product bound for disjoint unions of cliques). Let $G$ be a disjoint union of cliques with component sizes $s_1,\dots,s_t$ (so $\sum_i s_i=n$). Then \[ \alpha(G)=t,\qquad \omega(G)=\max_i s_i,\qquad \text{and hence }\alpha(G)\,\omega(G)\ge n. \] In particular, $\max\{\alpha(G),\omega(G)\}\ge \sqrt{n}$.

Proof. Picking one vertex from each component gives an independent set of size $t$, and no larger independent set exists (because within a clique no two vertices are independent), so $\alpha(G)=t$. The largest clique is exactly the largest component, so $\omega(G)=\max_i s_i$. Then \[ \alpha(G)\,\omega(G)=t\cdot\max_i s_i\ge \sum_{i=1}^t s_i = n, \] since $\max_i s_i\ge s_i$ for each $i$. Finally, by AM--GM, $\max\{\alpha,\omega\}\ge \sqrt{\alpha\omega}\ge \sqrt{n}$. $\square$

Proved special case. For $H=P_3$, the Erdős--Hajnal conclusion holds with exponent $c(H)=1/2$: any induced-$P_3$-free graph on $n$ vertices has a clique or independent set of size at least $\sqrt{n}$.

FAST REALITY CHECK (small $n$). For induced-$P_3$-free graphs, Lemma 1 gives a complete characterization, so no brute force is needed. As a spot-check: for $n=7$, the "most balanced" disjoint union of cliques is $K_3\cup K_2\cup K_2$, giving $\omega=3$, $\alpha=3$, and $\sqrt{7}\approx 2.65$, consistent with Lemma 2.

VERIFICATION

• Lemma 1 hinges on the fact that a shortest path has no chord skipping an intermediate vertex; that implication was used only for the first three vertices and is correct.
• Lemma 2 uses only definitions of $\alpha$ and $\omega$ in a disjoint union of cliques.
• The proved special case does not extend to general $H$; it is presented explicitly as a special case.

FINAL

UNRESOLVED

(i) Strongest proved partial result here: for $H=P_3$, the conjectured polynomial bound holds with $c(P_3)=1/2$ (via Lemmas 1--2).

(ii) First gap: for a general fixed $H$, produce a mechanism (structural decomposition, regularity, or other) that forces $\max\{\alpha(G),\omega(G)\}\ge n^{c(H)}$ in every induced-$H$-free graph $G$.

(iii) Top 3 next moves:

• Prove additional special cases by structural characterization for other small $H$ (e.g., induced-$P_4$-free graphs (cographs), induced-$C_5$-free, etc.), aiming for explicit exponents.
• Attempt to formalize how induced-$H$-free forces large "homogeneous" vertex subsets using density increment or regularity-type partitions.
• Computationally search for small $H$ and moderate $n$ to estimate the best possible exponent $c(H)$ and identify extremal constructions.

(iv) Minimal counterexample structure (if the conjecture were false for some $H$): a family of induced-$H$-free graphs $G_n$ with $\omega(G_n),\alpha(G_n)\le n^{o(1)}$, i.e., both clique and independent numbers subpolynomial, while still avoiding $H$ as an induced subgraph.