gpt pro 5.2 attempt on Math-847

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$.