codex 5.2 extra high attempt on Math-5910

1) FORMAL RESTATEMENT.

Let $n\ge 2$ and let $g=g(n)$ satisfy \[ n>g\ge (\log n)^2. \] Fix $s:=\lceil \log_2 n\rceil$ (any other fixed log base changes $s$ by a constant factor; the problem statement uses $\log n$ without specifying base). We ask for which functions $g(n)$ there exists a graph $G$ on vertex set $[n]$ such that for every subset $S\subseteq [n]$ with $|S|=g(n)$, the induced subgraph $G[S]$ contains

• a clique of size at least $s$, and
• an independent set of size at least $s$.

Equivalently, each $g(n)$-vertex induced subgraph has both $\omega(G[S])\ge s$ and $\alpha(G[S])\ge s$.

2) QUICK LITERATURE/CONTEXT CHECK.

The problem text states (without proofs) that Erdős--Hajnal suspected nonexistence for $g(n)=(\log n)^3$, that Alon--Sudakov rule out graphs for $g(n)=\frac{c}{\log\log n}(\log n)^3$ for some $c>0$, and that Alon--Bucić--Sudakov construct examples for extremely large $g(n)$ (doubly exponential in a power of $\log\log n$). I do not use any additional external results.

3) ATTACK PLAN.

Proof/existence strategies.

• Construct graphs with many vertex-disjoint "certificates" (disjoint $K_s$'s and disjoint independent $s$-sets) so that any large induced subgraph must contain one of each.
• Explore randomized constructions where every $g$-set typically contains many $K_s$ and many independent $s$-sets, then attempt a union bound (or stronger tail estimate) over all $\binom{n}{g}$ subsets.

Disproof/nonexistence strategies.

• Try to show that for $g$ as small as $(\log n)^3$, one can always find a $g$-subset whose induced graph is "too Ramsey" to contain both a $K_s$ and an independent $s$-set.
• Search for a general obstruction: e.g. if $g$ is too small, show some induced subgraph must have either clique number or independence number $<s$.

I did not resolve the main range $(\log n)^2\le g(n)\ll n$; below are two elementary, fully proved bounds (one necessary, one sufficient in a very large-$g$ regime) and basic sanity checks.

4) WORK.

Lemma 805.1 (a necessary size condition from set intersection). Let $H$ be any graph on $g$ vertices. If $H$ contains both a clique of size $s\ge 2$ and an independent set of size $s$, then \[ g\ge 2s-1. \]

Proof. Let $C$ be a clique of size $s$ and $I$ be an independent set of size $s$ in $H$. If $|C\cap I|\ge 2$, pick two distinct vertices $x,y\in C\cap I$. Since $x,y\in C$, they are adjacent; since $x,y\in I$, they are nonadjacent. This is a contradiction. Hence $|C\cap I|\le 1$, and therefore \[ g\;\ge\;|C\cup I|\;=\;|C|+|I|-|C\cap I|\;\ge\; s+s-1\;=\;2s-1. \] $\square$

Lemma 805.2 (a simple construction when $g$ is very close to $n$). Let $n\ge 2$ and $s:=\lceil\log_2 n\rceil$. Let $B:=\left\lfloor \frac{n}{2s}\right\rfloor$ and assume $B\ge 1$. There exists a graph $G$ on $n$ vertices such that for every $g$ with \[ g\ge n-B+1, \] every induced subgraph of $G$ on $g$ vertices contains both a clique of size at least $s$ and an independent set of size at least $s$.

Proof. Partition the vertex set into $2B$ disjoint blocks \[ C_1,\dots,C_B,\; I_1,\dots,I_B \] with $|C_i|=|I_j|=s$ for all $i,j$, plus a leftover set $L$ of remaining vertices (possibly empty) of size $|L|=n-2Bs<2s$. Define $G$ by:

• For each $i\le B$, make $G[C_i]$ a complete graph (a clique on $s$ vertices).
• For each $j\le B$, make $G[I_j]$ an empty graph (an independent set of size $s$).
• Put no edges between distinct blocks and no edges incident to $L$ (edges in these places can be chosen arbitrarily; choosing none only strengthens the independent-set presence).

Now take any subset $S$ of vertices with $|S|=g$, and write $k:=n-g$ for the number of deleted vertices. Assume $g\ge n-B+1$, i.e. $k\le B-1$.

To destroy a clique block $C_i$ (i.e. to make $S\cap C_i\ne C_i$), we must delete at least one vertex from $C_i$. Since at most $k\le B-1$ vertices are deleted total, at most $B-1$ of the $B$ clique blocks can be destroyed. Therefore there exists some $i$ with $C_i\subseteq S$, and then $G[S]$ contains $K_s$.

The same argument applies to the independent blocks $I_1,\dots,I_B$: deleting at most $B-1$ vertices cannot hit all $B$ blocks, so some $I_j\subseteq S$, and then $G[S]$ contains an independent set of size $s$.

Thus every induced subgraph on $g\ge n-B+1$ vertices contains both required structures. $\square$

FAST REALITY CHECK (scale sanity). The specific question $g(n)=(\log n)^3$ only becomes nontrivial once $(\log n)^3<n$. Using base-$2$ logs, the inequality $(\log_2 n)^3<n$ first holds at $n=1024$ (since $(\log_2 1024)^3=10^3=1000<1024$), and fails at $n=512$ (since $9^3=729>512$). So brute-force search is not meaningful even for moderately small $n$.

5) VERIFICATION.

• Lemma 805.1: the key check is that a clique and an independent set cannot share two vertices, since that would force an edge and a non-edge simultaneously.
• Lemma 805.2: verified that deleting $k\le B-1$ vertices can intersect at most $k$ of the $B$ blocks of a given type, so at least one full block survives.
• The construction indeed produces both an $s$-clique and an $s$-independent set inside $G[S]$ because the edges between blocks were chosen empty, so the induced subgraph on a full block is exactly as required.

6) FINAL. UNRESOLVED.

1. (i) Strongest proved partial result here: a necessary condition for any $g$-vertex induced subgraph to contain both a clique and independent set of size $s$ is $g\ge 2s-1$ (Lemma 805.1). A (very weak) sufficient regime is $g\ge n-\left\lfloor \frac{n}{2s}\right\rfloor+1$, for which an explicit construction works (Lemma 805.2).
2. (ii) First gap (crisp): decide whether there exists, for all sufficiently large $n$, a graph $G$ on $n$ vertices such that every induced subgraph on $g(n)=(\log n)^3$ vertices contains both a clique of size at least $\log n$ and an independent set of size at least $\log n$.
3. (iii) Top 3 next moves:
   1. Attempt a probabilistic construction and prove a tail bound strong enough to union bound over all $\binom{n}{g}$ subsets (second moment seems too weak; one would need a stronger "no $K_s$" estimate).
   2. Try to prove a universal obstruction for $g(n)=(\log n)^3$ by finding, in any $n$-vertex graph, a $g$-subset whose induced subgraph is close to a Ramsey graph on $g$ vertices with both $\omega$ and $\alpha$ less than $\log n$.
   3. Do computational search at the smallest nontrivial $n$ (around $n\approx 1024$) for heuristic constructions (e.g. algebraic/pseudorandom graphs), checking the property on random samples of $g$-subsets.
4. (iv) What a minimal counterexample would likely look like: if nonexistence holds at $g(n)=(\log n)^3$, then for every $n$ and every $G$ one should be able to find a $g$-subset $S$ such that $G[S]$ is simultaneously $K_s$-free and $\overline{G[S]}$ is $K_s$-free (i.e. $\omega(G[S])<s$ and $\alpha(G[S])<s$), so $G[S]$ behaves like a $(s,s)$-Ramsey graph on $g$ vertices with $s\approx \log n$.