Erdős Problem #552

Erdős Problem 552 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/552.tex.

REUSED SOURCE 1

Determine the Ramsey number $R(C_4,S_n)$ where $S_n$ is the star with $n$ leaves.

Parsons [Pa75] proved that \[ n+\sqrt{n}-6n^{11/40}\leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1 \] and also showed that $R(C_4,S_{q^2+1})=q^2+q+2$ if $q$ is a prime power.

If $q$ is a prime power and $n=q^2$ then it follows from Parsons' results that $R(C_4,S_{q^2})=q^2+q+1$.

Is it true for any $c>0$ that infinitely many $n$ satisfy \[ R(C_4,S_n)\leq n+\sqrt{n}-c? \]

1) “FORMAL RESTATEMENT”

Let $S_n$ be the star with $n$ leaves (so $|V(S_n)|=n+1$ and $|E(S_n)|=n$). The Ramsey number $R(C_4,S_n)$ is the smallest $N$ such that every red/blue colouring of $E(K_N)$ contains either a red 4-cycle $C_4$ or a blue copy of $S_n$.

The tasks are: $1$ Determine $R(C_4,S_n)$ exactly. $2$ Decide whether for every fixed $c>0$ there are infinitely many $n$ with $R(C_4,S_n)\le n+\sqrt n - c$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem file states (Parsons [Pa75]): \[ n+\sqrt{n}-6n^{11/40}\leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1. \] It also states the exact values \[ R(C_4,S_{q^2})=q^2+q+1\quad\text{and}\quad R(C_4,S_{q^2+1})=q^2+q+2 \] when $q$ is a prime power.

Below I prove an elementary upper bound close to the stated one (and matching it for non-square $n$), give a simple general lower bound construction, and compute small cases.

3) “ATTACK PLAN”

Translate the Ramsey condition into a statement about $C_4$-free graphs with constrained minimum/maximum degree: if a colouring has no blue $S_n$, then every vertex has blue degree at most $n-1$, hence red degree at least $N-n$. If also there is no red $C_4$, the red graph is $C_4$-free with minimum degree at least $N-n$. So we need upper bounds on the minimum degree of $C_4$-free graphs.

For lower bounds, construct explicit $C_4$-free graphs with controlled minimum degree and colour their edges red.

For sanity, brute-force compute $R(C_4,S_n)$ for the smallest $n$.

4) “WORK”

Lemma 1 (A $C_4$-free graph has at most one common neighbour per vertex pair). If $H$ is $C_4$-free, then for any distinct vertices $u\neq v$, the set of common neighbours $N(u)\cap N(v)$ has size at most $1$.

Proof. If $u$ and $v$ had two distinct common neighbours $x\neq y$, then the edges $ux,xv,vy,yu$ would form a 4-cycle $u-x-v-y-u$ in $H$, contradicting that $H$ is $C_4$-free. $\square$

Lemma 2 (Minimum-degree bound for $C_4$-free graphs). If $H$ is $C_4$-free on $N$ vertices with minimum degree $\delta(H)=\delta$, then \[ \delta(\delta-1)\le N-1. \]

Proof. Fix a vertex $w$. The number of (unordered) pairs of distinct neighbours of $w$ equals $\binom{d(w)}{2}$. Summing over all vertices gives \[ \sum_{w\in V(H)} \binom{d(w)}{2}. \] On the other hand, by Lemma 1, for each unordered pair $\{u,v\}$ of distinct vertices, there is at most one vertex $w$ which is a common neighbour of $u$ and $v$. Equivalently, the number of length-2 paths $u-w-v$ with fixed endpoints $u,v$ is at most $1$. Therefore \[ \sum_{w\in V(H)} \binom{d(w)}{2} \le \binom{N}{2}. \] Using $d(w)\ge \delta$ for all $w$ gives \[ N\binom{\delta}{2} \le \binom{N}{2}. \] Multiplying by $2/N$ yields $\delta(\delta-1)\le N-1$. $\square$

Lemma 3 (Elementary upper bound for $R(C_4,S_n)$; sharp for non-squares). Let $n\ge 2$ and set $s:=\lceil\sqrt{n}\rceil$. Then \[ R(C_4,S_n)\le n+s+2. \] Moreover, if $n$ is not a perfect square then the stronger bound \[ R(C_4,S_n)\le n+s+1 \] holds.

Proof. Let $N$ be any integer and consider a red/blue colouring of $K_N$ with no blue $S_n$. Then every vertex has blue degree at most $n-1$, hence red degree at least $N-1-(n-1)=N-n$. Let $H$ be the red graph; then $\delta(H)\ge N-n$.

If $H$ is $C_4$-free, Lemma 2 gives \[ (N-n)(N-n-1) \le N-1. \] Write $x:=N-n$. Then the inequality becomes \[ x(x-1) \le n+x-1. \] Rearranging gives $(x-1)^2\le n$. Therefore $x\le 1+\sqrt{n}$.

Now take $s=\lceil\sqrt{n}\rceil$. - If $n$ is not a square, then $s>\sqrt{n}$, so $s+1>1+\sqrt{n}$. Thus any colouring with no blue $S_n$ cannot have a $C_4$-free red graph when $x=N-n\ge s+1$. Equivalently, for $N=n+s+1$ every colouring has either a blue $S_n$ or a red $C_4$, giving $R(C_4,S_n)\le n+s+1$.

- If $n$ is a square, then $s=\sqrt n$ and the above argument only rules out $x\ge s+2$, i.e. it yields $R(C_4,S_n)\le n+s+2$.

This proves the stated bounds. $\square$

Lemma 4 (A general lower bound via cycles). For every $n\ge 3$, \[ R(C_4,S_n)\ge n+3. \]

Proof. Let $N:=n+2\ge 5$. Colour the edges of a Hamilton cycle $C_N$ red and colour all remaining edges blue. - The red graph is a single cycle of length $N$, hence contains no 4-cycle. - Each vertex has red degree $2$, hence blue degree $(N-1)-2 = n-1$, so no vertex has blue degree $\ge n$ and thus there is no blue $S_n$. Therefore this is a colouring of $K_{n+2}$ with neither a red $C_4$ nor a blue $S_n$, so $R(C_4,S_n)>n+2$, i.e. $R(C_4,S_n)\ge n+3$. $\square$

5) “VERIFICATION”

Fast reality checks:

$1$ Exhaustive computation for small $n$ (by enumerating all colourings of $K_N$ for the relevant $N$): - $R(C_4,S_2)=4$. - $R(C_4,S_3)=6$. - $R(C_4,S_4)=7$. These agree with the stated upper bound $n+\lceil\sqrt n\rceil+1$ for $n=3,4$, and (for $n=4$) with Parsons' stated exact value at $n=q^2$ with $q=2$.

$2$ For $n=5$ (which is $q^2+1$ with $q=2$), Parsons' stated exact value gives $R(C_4,S_5)=8$. The lower-bound construction in Lemma 4 gives a colouring on $7$ vertices avoiding both red $C_4$ and blue $S_5$, consistent with $R=8$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Lemmas 1–3 give an elementary proof of an upper bound $R(C_4,S_n)\le n+\lceil\sqrt n\rceil+2$ for all $n$ and $R(C_4,S_n)\le n+\lceil\sqrt n\rceil+1$ for non-square $n$. Lemma 4 gives a general lower bound $R(C_4,S_n)\ge n+3$ for all $n\ge 3$. The problem file states much stronger bounds and exact values at $n=q^2$ and $n=q^2+1$ for prime powers $q$.

(ii) First gap (crisp): Determine $R(C_4,S_n)$ for all $n$ (in particular, close the remaining gap between the best known lower bounds and the stated upper bound $n+\lceil\sqrt n\rceil+1$), and decide whether $R(C_4,S_n)\le n+\sqrt n - c$ holds for infinitely many $n$ for each fixed $c>0$.

(iii) Top 3 next moves: 1. Square-case sharpening: Improve Lemma 3 in the square case by ruling out $C_4$-free red graphs with minimum degree exactly $\sqrt n +1$ at the critical order $N=n+\sqrt n +1$. 2. Constructions: Build explicit $C_4$-free graphs on $N$ vertices with minimum degree close to $\sqrt N$ (or use known finite-geometry constructions if allowed) to improve lower bounds and test the second question about $n+\sqrt n-c$. 3. Computation: For moderate $n$ (say $n\le 20$), use SAT/backtracking to compute $R(C_4,S_n)$ exactly to look for patterns beyond the prime-power cases.

(iv) Minimal counterexample structure: A counterexample to the claimed upper behaviour at a given $n$ would be a red/blue colouring of $K_{N}$ (with $N$ just below the conjectured value) whose red graph is $C_4$-free and has minimum degree at least $N-n$, equivalently whose blue graph has maximum degree at most $n-1$.

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Determine the Ramsey number $R(C_4,S_n)$ where $S_n$ is the star with $n$ leaves.

Parsons [Pa75] proved that \[ n+\sqrt{n}-6n^{11/40}\leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1 \] and also showed that $R(C_4,S_{q^2+1})=q^2+q+2$ if $q$ is a prime power.

If $q$ is a prime power and $n=q^2$ then it follows from Parsons' results that $R(C_4,S_{q^2})=q^2+q+1$.

Is it true for any $c>0$ that infinitely many $n$ satisfy \[ R(C_4,S_n)\leq n+\sqrt{n}-c? \]

1) “FORMAL RESTATEMENT”

Let $S_n$ be the star with $n$ leaves (so $|V(S_n)|=n+1$ and $|E(S_n)|=n$). The Ramsey number $R(C_4,S_n)$ is the smallest $N$ such that every red/blue colouring of $E(K_N)$ contains either a red 4-cycle $C_4$ or a blue copy of $S_n$.

The tasks are: $1$ Determine $R(C_4,S_n)$ exactly. $2$ Decide whether for every fixed $c>0$ there are infinitely many $n$ with $R(C_4,S_n)\le n+\sqrt n - c$.

2) “QUICK LITERATURE/CONTEXT CHECK”

The problem file states (Parsons [Pa75]): \[ n+\sqrt{n}-6n^{11/40}\leq R(C_4,S_n)\leq n+\lceil\sqrt{n}\rceil+1. \] It also states the exact values \[ R(C_4,S_{q^2})=q^2+q+1\quad\text{and}\quad R(C_4,S_{q^2+1})=q^2+q+2 \] when $q$ is a prime power.

Below I prove an elementary upper bound close to the stated one (and matching it for non-square $n$), give a simple general lower bound construction, and compute small cases.

3) “ATTACK PLAN”

Translate the Ramsey condition into a statement about $C_4$-free graphs with constrained minimum/maximum degree: if a colouring has no blue $S_n$, then every vertex has blue degree at most $n-1$, hence red degree at least $N-n$. If also there is no red $C_4$, the red graph is $C_4$-free with minimum degree at least $N-n$. So we need upper bounds on the minimum degree of $C_4$-free graphs.

For lower bounds, construct explicit $C_4$-free graphs with controlled minimum degree and colour their edges red.

For sanity, brute-force compute $R(C_4,S_n)$ for the smallest $n$.

4) “WORK”

Lemma 1 (A $C_4$-free graph has at most one common neighbour per vertex pair). If $H$ is $C_4$-free, then for any distinct vertices $u\neq v$, the set of common neighbours $N(u)\cap N(v)$ has size at most $1$.

Proof. If $u$ and $v$ had two distinct common neighbours $x\neq y$, then the edges $ux,xv,vy,yu$ would form a 4-cycle $u-x-v-y-u$ in $H$, contradicting that $H$ is $C_4$-free. $\square$

Lemma 2 (Minimum-degree bound for $C_4$-free graphs). If $H$ is $C_4$-free on $N$ vertices with minimum degree $\delta(H)=\delta$, then \[ \delta(\delta-1)\le N-1. \]

Proof. Fix a vertex $w$. The number of (unordered) pairs of distinct neighbours of $w$ equals $\binom{d(w)}{2}$. Summing over all vertices gives \[ \sum_{w\in V(H)} \binom{d(w)}{2}. \] On the other hand, by Lemma 1, for each unordered pair $\{u,v\}$ of distinct vertices, there is at most one vertex $w$ which is a common neighbour of $u$ and $v$. Equivalently, the number of length-2 paths $u-w-v$ with fixed endpoints $u,v$ is at most $1$. Therefore \[ \sum_{w\in V(H)} \binom{d(w)}{2} \le \binom{N}{2}. \] Using $d(w)\ge \delta$ for all $w$ gives \[ N\binom{\delta}{2} \le \binom{N}{2}. \] Multiplying by $2/N$ yields $\delta(\delta-1)\le N-1$. $\square$

Lemma 3 (Elementary upper bound for $R(C_4,S_n)$; sharp for non-squares). Let $n\ge 2$ and set $s:=\lceil\sqrt{n}\rceil$. Then \[ R(C_4,S_n)\le n+s+2. \] Moreover, if $n$ is not a perfect square then the stronger bound \[ R(C_4,S_n)\le n+s+1 \] holds.

Proof. Let $N$ be any integer and consider a red/blue colouring of $K_N$ with no blue $S_n$. Then every vertex has blue degree at most $n-1$, hence red degree at least $N-1-(n-1)=N-n$. Let $H$ be the red graph; then $\delta(H)\ge N-n$.

If $H$ is $C_4$-free, Lemma 2 gives \[ (N-n)(N-n-1) \le N-1. \] Write $x:=N-n$. Then the inequality becomes \[ x(x-1) \le n+x-1. \] Rearranging gives $(x-1)^2\le n$. Therefore $x\le 1+\sqrt{n}$.

Now take $s=\lceil\sqrt{n}\rceil$. - If $n$ is not a square, then $s>\sqrt{n}$, so $s+1>1+\sqrt{n}$. Thus any colouring with no blue $S_n$ cannot have a $C_4$-free red graph when $x=N-n\ge s+1$. Equivalently, for $N=n+s+1$ every colouring has either a blue $S_n$ or a red $C_4$, giving $R(C_4,S_n)\le n+s+1$.

- If $n$ is a square, then $s=\sqrt n$ and the above argument only rules out $x\ge s+2$, i.e. it yields $R(C_4,S_n)\le n+s+2$.

This proves the stated bounds. $\square$

Lemma 4 (A general lower bound via cycles). For every $n\ge 3$, \[ R(C_4,S_n)\ge n+3. \]

Proof. Let $N:=n+2\ge 5$. Colour the edges of a Hamilton cycle $C_N$ red and colour all remaining edges blue. - The red graph is a single cycle of length $N$, hence contains no 4-cycle. - Each vertex has red degree $2$, hence blue degree $(N-1)-2 = n-1$, so no vertex has blue degree $\ge n$ and thus there is no blue $S_n$. Therefore this is a colouring of $K_{n+2}$ with neither a red $C_4$ nor a blue $S_n$, so $R(C_4,S_n)>n+2$, i.e. $R(C_4,S_n)\ge n+3$. $\square$

5) “VERIFICATION”

Fast reality checks:

$1$ Exhaustive computation for small $n$ (by enumerating all colourings of $K_N$ for the relevant $N$): - $R(C_4,S_2)=4$. - $R(C_4,S_3)=6$. - $R(C_4,S_4)=7$. These agree with the stated upper bound $n+\lceil\sqrt n\rceil+1$ for $n=3,4$, and (for $n=4$) with Parsons' stated exact value at $n=q^2$ with $q=2$.

$2$ For $n=5$ (which is $q^2+1$ with $q=2$), Parsons' stated exact value gives $R(C_4,S_5)=8$. The lower-bound construction in Lemma 4 gives a colouring on $7$ vertices avoiding both red $C_4$ and blue $S_5$, consistent with $R=8$.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result: Lemmas 1–3 give an elementary proof of an upper bound $R(C_4,S_n)\le n+\lceil\sqrt n\rceil+2$ for all $n$ and $R(C_4,S_n)\le n+\lceil\sqrt n\rceil+1$ for non-square $n$. Lemma 4 gives a general lower bound $R(C_4,S_n)\ge n+3$ for all $n\ge 3$. The problem file states much stronger bounds and exact values at $n=q^2$ and $n=q^2+1$ for prime powers $q$.

(ii) First gap (crisp): Determine $R(C_4,S_n)$ for all $n$ (in particular, close the remaining gap between the best known lower bounds and the stated upper bound $n+\lceil\sqrt n\rceil+1$), and decide whether $R(C_4,S_n)\le n+\sqrt n - c$ holds for infinitely many $n$ for each fixed $c>0$.

(iii) Top 3 next moves: 1. Square-case sharpening: Improve Lemma 3 in the square case by ruling out $C_4$-free red graphs with minimum degree exactly $\sqrt n +1$ at the critical order $N=n+\sqrt n +1$. 2. Constructions: Build explicit $C_4$-free graphs on $N$ vertices with minimum degree close to $\sqrt N$ (or use known finite-geometry constructions if allowed) to improve lower bounds and test the second question about $n+\sqrt n-c$. 3. Computation: For moderate $n$ (say $n\le 20$), use SAT/backtracking to compute $R(C_4,S_n)$ exactly to look for patterns beyond the prime-power cases.

(iv) Minimal counterexample structure: A counterexample to the claimed upper behaviour at a given $n$ would be a red/blue colouring of $K_{N}$ (with $N$ just below the conjectured value) whose red graph is $C_4$-free and has minimum degree at least $N-n$, equivalently whose blue graph has maximum degree at most $n-1$.