gpt pro 5.2 attempt on Math-5910

# Erdős Problem #805 — Research Analysis

1) FORMAL RESTATEMENT

Problem statement (precise form)

Let $n\ge 1$ be an integer. Define \[ m_n(r) :=\min\left\{m:\ \exists\text{ a graph }G\text{ on }n\text{ vertices such that } \forall S\subseteq V(G),\ |S|=m,\ \omega(G[S])\ge r\ \text{and}\ \alpha(G[S])\ge r \right\}. \]

Here:

* graphs are finite, simple, undirected; * (G[S]) denotes the induced subgraph on (S); * $\omega(\cdot)$ is clique number, $\alpha(\cdot)$ independence number; * logarithms are natural.

Erdős–Hajnal ask:

(EH-805) Is it true that \[ m_n(\lceil\log n\rceil)\le (\log n)^3 \quad\text{for all sufficiently large }n? \]

Equivalently: does there exist, for large (n), a graph on (n) vertices such that every induced subgraph on $(\log n)^3$ vertices contains both

* a clique of size at least $\log n$, and * an independent set of size at least $\log n$?

Erdős and Hajnal conjectured the answer is no.

---

2) QUICK LITERATURE / CONTEXT CHECK

Known results (chronological):

* Alon–Sudakov $2007$ proved a non-existence result when \[ m \le c,\frac{(\log n)^3}{\log\log n}, \] showing that graphs with the required property cannot exist at that scale.

* Alon–Bucić–Sudakov $2021$ constructed graphs showing \[ m_n(\log n)\ \le\ 2^{2^{(\log\log n)^{1/2+o(1)}}}. \]

Thus the current gap is \[ \frac{(\log n)^3}{\log\log n} \ \lesssim\ m_n(\log n) \ \lesssim\ 2^{2^{(\log\log n)^{1/2+o(1)}}}, \] and the specific threshold $m=(\log n)^3$ remains open.

---

3) ATTACK PLAN

Two possible routes:

(A) Disproof route (Erdős–Hajnal conjecture true)

Strengthen the Alon–Sudakov lower-bound mechanism to eliminate the remaining $\log\log n$ gap, showing that $(\log n)^3$ is still too small.

(B) Construction route (Erdős–Hajnal conjecture false)

Improve the ABS21 construction dramatically, compressing the current double-exponential bound down to polylogarithmic scale.

The only route where a fully rigorous result can currently be completed is (A), up to the known $(\log n)^3/\log\log n$ barrier.

---

4) WORK (Complete Rigorous Partial Result)

Key auxiliary parameter

For integers $n>s>t\ge2$, define (f(n,s,t)) to be the minimum possible independence number of an (n)-vertex graph (H) satisfying:

every induced subgraph of (H) on (s) vertices contains an independent set of size at least (t).

---

Lemma 1 (Alon–Sudakov reduction lemma)

Let (n) be large and $n/2 > s > t \ge 2$. If \[ f(\lfloor n/2\rfloor,s,t) > \frac{s}{t-1}, \] then no graph (G) on (n) vertices has the property that every induced subgraph on (s) vertices contains both

* a clique of size at least (t), and * an independent set of size at least (t).

Proof

Assume such a graph (G) exists.

Let $F := f(\lfloor n/2\rfloor,s,t)$. Every induced subgraph of (G) on $\lfloor n/2\rfloor$ vertices must contain an independent set of size at least (F).

Iteratively remove such independent sets $I_1,I_2,\dots$. After at most $t-1$ steps, the union \[ U := I_1\cup\cdots\cup I_{t-1} \] satisfies \[ |U| \ge \min{\lfloor n/2\rfloor,(t-1)F} > s. \]

But (G[U]) is $(t-1)$-colorable, hence contains no clique of size (t). Choosing any (s)-subset of (U) contradicts the defining property of (G). ∎

---

Theorem 2 (Alon–Sudakov lower bound)

There exists an absolute constant $c_0>0$ such that for all sufficiently large (n), \[ m_n(\lceil\log n\rceil) \ \ge c_0,\frac{(\log n)^3}{\log\log n}. \]

Proof

Let \[ t=\lceil\log n\rceil, \qquad s=\left\lfloor c_0\frac{(\log n)^3}{\log\log n}\right\rfloor, \qquad n'=\lfloor n/2\rfloor. \]

Alon–Sudakov proved that for $2t\le s<n'/2$, \[ f(n',s,t) \ \ge C,t\frac{\log(n'/s)}{\log(s/t)} \] for an absolute constant $C>0$.

Elementary estimates give: \[ \log(n'/s)\ge \tfrac12\log n, \qquad \log(s/t)\le 3\log\log n, \] hence \[ f(n',s,t) \ \ge \frac{C}{6}\frac{(\log n)^2}{\log\log n}. \]

Meanwhile, \[ \frac{s}{t-1} \le 2c_0\frac{(\log n)^2}{\log\log n}. \]

Choosing $c_0<C/12$ ensures \[ f(n',s,t)>\frac{s}{t-1}, \] so Lemma 1 applies, proving non-existence at this scale. ∎

---

5) VERIFICATION

* All inheritance steps are valid for induced subgraphs. * Parameter constraints $2t\le s\ll n$ are satisfied. * Floors/ceilings affect constants only. * The argument explicitly shows where the $\log\log n$ loss occurs.

No hidden assumptions are used.

---

6) FINAL: UNRESOLVED

Summary

* It is rigorously proved that \[ m_n(\log n)\ \ge\ c,\frac{(\log n)^3}{\log\log n}. \] * It remains open whether this lower bound can be pushed to $(\log n)^3$, or whether a construction exists at that scale. * The precise obstacle is that current bounds on the auxiliary function (f(n,s,t)) lose a factor of $\log\log n$, and no method is known to recover it using both the clique and independence requirements simultaneously.

Minimal next gap

Prove or refute: \[ f(n,\log^3 n,\log n)\ \gg\ (\log n)^2 \] under the two-sided Erdős–Hajnal hypothesis.

This is exactly the missing step separating the conjecture from resolution.

If you want, next we can:

* isolate the obstruction combinatorially (why $\log\log n$ appears), * attempt a strengthening of the Alon–Sudakov inequality, * or analyze why the ABS21 construction fundamentally stalls far above polylogarithmic scale.