Erdős Problem #159

Erdős Problem 159: a checked attempt

GPT_6_Astra_Ultra

25 September 2026

Correct statement and scope

The current problem asks whether there is an absolute $c>0$ such that \[ R(C_4,K_n)\ll n^{2-c}. \] It does not ask for a matching quadratic lower bound. Here $R(C_4,K_n)$ is the least $N$ such that every graph on $N$ vertices has a four-cycle or an independent $n$-set. Source: https://www.erdosproblems.com/159. We supply elementary bounds \[ c_0(n/\log n)^{4/3}\le R(C_4,K_n)\le(n+1)^2 \] for sufficiently large $n$. They are weaker than the bounds recorded on the problem page and leave the requested fixed power saving unresolved.

Quadratic upper bound with the probabilistic lemma proved

In a $C_4$-free graph on $N$ vertices, two vertices have at most one common neighbour. Counting length-two paths by their middle vertex gives \[ \sum_v\binom{d(v)}2\le\binom N2. \] If $\bar d$ is the average degree, convexity yields $\bar d(\bar d-1)\le N-1$, so $\bar d<\sqrt N+1$. Choose a uniformly random ordering of the vertices and retain a vertex if it precedes all its neighbours. The retained set is independent, and vertex $v$ is retained with probability $1/(d(v)+1)$. Thus some independent set has size at least \[ \sum_v\frac1{d(v)+1}\ge\frac N{\bar d+1}>\frac N{\sqrt N+2}, \] where the middle inequality is Cauchy--Schwarz. At $N=(n+1)^2$ the last expression equals $n-1+4/(n+3)>n-1$. Integrality forces an independent set of at least $n$ vertices, proving the upper bound.

A superlinear lower bound by deleting four-cycles

For large $n$ choose \[ N=\left\lfloor\left(\frac{n}{8\log n}\right)^{4/3}\right\rfloor, \qquad p=N^{-3/4}, \] and form the random graph with independent edge probability $p$. The expected number $X$ of four-cycles is \[ \mathbb EX=3\binom N4p^4\le N/8, \] so $\mathbb P(X>N/2)\le1/4$ by Markov's inequality. The probability of an independent $n$-set is at most \[ \binom Nn(1-p)^{\binom n2} \le\exp\left(n\log N-\frac{pn(n-1)}2\right). \] For all large $n$ we have $N\ge n$, $\log N\le\tfrac43\log n$, $pn\ge8\log n$ and $n-1\ge n/2$. The exponent is consequently at most $-\tfrac23n\log n$, so this probability is less than $1/4$. With positive probability both $X\le N/2$ and $\alpha(G)<n$. Select one vertex from each four-cycle of this graph and remove the union of the selected vertices. At most $N/2$ vertices are removed, and every old four-cycle is destroyed; deleting vertices cannot create new cycles or increase the independence number. The surviving graph has at least $N/2$ vertices, is $C_4$-free and still has independence number less than $n$. It follows that \[ R(C_4,K_n)>\lfloor N/2\rfloor \gg(n/\log n)^{4/3}. \] No claim is made that this elementary alteration argument attains the stronger published lower exponent.

Remaining gap and provenance

The earlier GPT-Pro-5.2 draft restated the target as quadratic order and sought a quadratic lower bound. That would point in the opposite direction from the actual power-saving question. Its common-neighbour argument is retained and sharpened; its unrecorded exact Ramsey computation is not needed. The unresolved task is an upper bound with exponent strictly smaller than two, or a lower bound excluding every such saving. All proofs above are elementary and make no novelty claim.

Completion rate estimate: 20%.

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.