gpt pro 5.2 attempt on Math-5465

Erdos problem #159

1) FORMAL RESTATEMENT

Let $R(C_4,K_n)$ be the Ramsey number: the least $N$ such that every graph $G$ on $N$ vertices contains a copy of $C_4$ or an independent set of size $n$. Equivalently, $R(C_4,K_n)$ is the least $N$ such that every $C_4$-free graph on $N$ vertices has independence number at least $n$. The problem asks to show $R(C_4,K_n)$ is "on the order of" $n^2$.

2) QUICK LITERATURE/CONTEXT CHECK

The problem file gives no cited bounds here. I therefore provide only elementary bounds proved below.

3) ATTACK PLAN

Upper bound: bound the maximum number of edges in a $C_4$-free graph by counting common neighbors; then use a general independence number lower bound. Lower bound: exhibit explicit $C_4$-free graphs with small independence number (I only obtain a linear lower bound here).

4) WORK

Lemma 159.1 (edge bound for $C_4$-free graphs via common neighbors).

Let $G$ be a $C_4$-free graph on $N$ vertices with degree sequence $(d(v))_{v\in V}$. Then \[ \sum_{v\in V} \binom{d(v)}{2}\ \le\ \binom{N}{2}. \] Consequently, if $\bar d=\frac{1}{N}\sum_v d(v)$ is the average degree, then \[ \bar d(\bar d-1)\le N-1\quad\text{and hence}\quad \bar d\le \frac{1+\sqrt{4N-3}}{2}<\sqrt N+1. \] In particular, \[ |E(G)|=\frac{N\bar d}{2}\ <\ \frac{N^{3/2}}{2}+\frac{N}{2}. \]

Proof. For any unordered pair of distinct vertices $\{x,y\}$, let $c(x,y)$ be the number of common neighbors of $x$ and $y$. If $c(x,y)\ge 2$, pick two distinct common neighbors $u\neq v$; then $x-u-y-v-x$ is a $4$-cycle, contradicting that $G$ is $C_4$-free. Thus $c(x,y)\le 1$ for all $\{x,y\}$.

Now count (unordered) length-$2$ paths by their middle vertex: vertex $v$ contributes $\binom{d(v)}{2}$ unordered pairs of distinct neighbors, i.e. $\binom{d(v)}{2}$ unordered endpoint pairs $\{x,y\}$ with $v$ a common neighbor. Summing over $v$ gives $\sum_v \binom{d(v)}{2} = \sum_{\{x,y\}} c(x,y)\le \binom{N}{2}$.

By convexity (Jensen), $\sum_v \binom{d(v)}{2}\ge N\binom{\bar d}{2}=\frac{N\bar d(\bar d-1)}{2}$, so $\frac{N\bar d(\bar d-1)}{2}\le \frac{N(N-1)}{2}$, i.e. $\bar d(\bar d-1)\le N-1$. Solving the quadratic gives the stated bound on $\bar d$ and hence on $|E(G)|=N\bar d/2$. $\square$

Lemma 159.2 (a simple independence lower bound from edge count).

For any graph $G$ on $N$ vertices with $e=|E(G)|$, \[ \alpha(G)\ \ge\ \frac{N^2}{2e+N}. \]

Proof. Let $d_1,\dots,d_N$ be the degrees. A standard bound (a one-line form of the Caro--Wei inequality) is \[ \alpha(G)\ge \sum_{i=1}^N \frac{1}{d_i+1}. \] Using Cauchy--Schwarz, \[ \sum_{i=1}^N \frac{1}{d_i+1}\ \ge\ \frac{\left(\sum_{i=1}^N 1\right)^2}{\sum_{i=1}^N (d_i+1)} \ =\ \frac{N^2}{\sum_i d_i + N}\ =\ \frac{N^2}{2e+N}. \] $\square$

Corollary 159.3 (an $O(n^2)$ upper bound on $R(C_4,K_n)$).

There is an absolute constant $C$ such that $R(C_4,K_n)\le C n^2$ for all $n$. For instance, $C=16$ works.

Proof. Let $G$ be any $C_4$-free graph on $N$ vertices. By Lemma 159.1, $e<\frac12 N^{3/2}+\frac12 N$. Then Lemma 159.2 gives \[ \alpha(G)\ge \frac{N^2}{2e+N}\ >\ \frac{N^2}{N^{3/2}+2N}\ =\ \frac{\sqrt N}{1+2/\sqrt N}. \] If $N\ge 16 n^2$ then $\sqrt N\ge 4n$ and $1+2/\sqrt N\le 1+1/(2n)\le 2$, hence $\alpha(G)\ge 2n>n$. So every $C_4$-free graph on $N\ge 16n^2$ vertices has an independent set of size $n$, i.e. $R(C_4,K_n)\le 16n^2$. $\square$

Lemma 159.4 (a linear lower bound construction).

For every $n\ge 2$, \[ R(C_4,K_n)\ge 3(n-1)+1. \]

Proof. Let $G$ be the disjoint union of $n-1$ triangles ($K_3$'s). Then $G$ is $C_4$-free (it has no cycle of length $4$). Any independent set can contain at most one vertex from each triangle, so $\alpha(G)=n-1$. Thus on $N=3(n-1)$ vertices there exists a $C_4$-free graph with no independent set of size $n$, so $R(C_4,K_n)>3(n-1)$, i.e. $R(C_4,K_n)\ge 3(n-1)+1$. $\square$

FAST REALITY CHECK (computed exact value for $n=3$).

By brute force over all graphs on $N\le 7$ vertices, I found: \[ R(C_4,K_3)=7. \] (Equivalently: there exists a $C_4$-free graph on $6$ vertices with independence number $2$, but none on $7$ vertices.)

5) VERIFICATION

• Lemma 159.1: the "two common neighbors imply a $C_4$" implication is checked explicitly.
• Lemma 159.2: uses only Caro--Wei and Cauchy--Schwarz.
• Corollary 159.3: constants tracked; not optimized.
• Computation of $R(C_4,K_3)$: verified by exhaustive enumeration.

6) FINAL

UNRESOLVED

1. (i) Strongest fully proved partial result obtained here. I proved an explicit quadratic upper bound $R(C_4,K_n)\le 16n^2$ (Corollary 159.3) and a linear lower bound $R(C_4,K_n)\ge 3n-2$ (Lemma 159.4).

2. (ii) Exact first gap. Provide a matching quadratic lower bound: construct, for infinitely many $n$, a $C_4$-free graph on $\Omega(n^2)$ vertices whose independence number is $<n$.

3. (iii) Top 3 next moves (concrete targets).
   1. Find/construct explicit families of $C_4$-free graphs with edge density $\Theta(N^{3/2})$ and prove their independence number is $O(\sqrt N)$.
   2. Improve the linear lower bound using better $C_4$-free building blocks with smaller independence ratio than disjoint triangles.
   3. Extend computations to larger $n$ for small $K_n$ (e.g. compute $R(C_4,K_4)$ if feasible via SAT/ILP) to guess the correct constant/factor.

4. (iv) Minimal counterexample structure (if the claimed order $n^2$ is false). If $R(C_4,K_n)$ were $o(n^2)$, then every $C_4$-free graph on $N=o(n^2)$ vertices would already force an independent set of size $n$. That would require a stronger universal lower bound $\alpha(G)\gg \sqrt N$ for $C_4$-free graphs than what is obtained from the general edge bound alone.