gpt pro 5.2 attempt on Math-5373, version 2

Problem 20 (Sunflowers): Round 2 --- continuation & gap-closure

1) ROUND-2 OBJECTIVE

Path (A) --- full proof in a nontrivial special slice.

Round 1 fully treated the case $(n,k)=(2,3)$ by translating to graphs and obtaining the exact value $f(2,3)=7$ (Lemma 20.3). In this round I close the entire $n=2$ slice by determining the exact value of $f(2,k)$ for every $k\ge 2$. This is the most promising gap-closure direction because (i) it strictly extends Round 1's exact computation, (ii) it produces an infinite family of exact values and extremal constructions, and (iii) it rules out any counterexample strategy based on $2$-uniform families.

2) ROUND-1 FOUNDATION USED

I rely only on the following Round 1 items:

• The definition of $k$-sunflower and $f(n,k)$ (Round 1 §1).
• The graph translation idea from Lemma 20.3 for $n=2$ (2-sets as edges; a $3$-sunflower is either a $K_{1,3}$ or a matching of size $3$).

No other Round 1 lemma is reused.

3) NEW INSIGHT / TOOL (ROUND-2)

New tool: exact extremal theorem for graphs with bounded matching and bounded maximum degree.

I upgrade the Round 1 translation from $(n,k)=(2,3)$ to general $(n,k)=(2,k)$, and then invoke the sharp extremal theorem of Abbott--Hanson--Sauer $1972$, stated as Theorem 3.2 in [Kupavskii2025]. This yields an exact formula (and extremal structure) for the maximum size of a $k$-sunflower-free $2$-uniform family.

4) ATTACK PLAN (ROUND-2)

Round 1 gap addressed: Round 1 computed $f(2,3)$ exactly but did not treat $f(2,k)$ for general $k$.

Claims to prove now:

1. (General translation) A $k$-sunflower of $2$-sets is equivalent to either a star $K_{1,k}$ or a matching of size $k$.
2. (Exact extremal value) The maximum number of edges in a graph with no $K_{1,k}$ and no matching of size $k$ is \[ \operatorname{ex}_\Delta(k):= \begin{cases} k(k-1), & k\ \text{odd},\\ \Big\lfloor \dfrac{(k-1)(2k-1)}{2}\Big\rfloor, & k\ \text{even}, \end{cases} \] with explicit extremal constructions.

Why this closes the gap: Once $1$ holds, the $n=2$ sunflower problem becomes a graph extremal problem. Theorem 3.2 of [Kupavskii2025] solves that extremal problem exactly, yielding $f(2,k)=\operatorname{ex}_\Delta(k)+1$.

5) WORK (ROUND-2)

Lemma 20.4 (Sunflowers of 2-sets are stars or matchings).

Fix $k\ge 3$. Let $\mathcal F$ be a family of $2$-element sets, and let $G$ be the simple graph with edge set $E(G)=\mathcal F$. Then $\mathcal F$ contains a $k$-sunflower if and only if $G$ contains either

1. a matching of size $k$ (i.e., $k$ pairwise-disjoint edges), or
2. a star $K_{1,k}$ (i.e., a vertex of degree at least $k$).

Proof. If $\{e_1,\dots,e_k\}\subseteq E(G)$ is a $k$-sunflower, then each $e_i$ has size $2$, so the common pairwise intersection (the core) has size either $0$ or $1$.

• If the core is empty, then $e_i\cap e_j=\varnothing$ for $i\neq j$, so the edges are pairwise disjoint: a matching of size $k$.
• If the core has size $1$, then there is a vertex $v$ with $v\in e_i$ for every $i$, and since $e_i\cap e_j=\{v\}$, the other endpoints are all distinct. Thus $\{e_1,\dots,e_k\}$ is exactly the edge set of a $K_{1,k}$ centered at $v$.

Conversely, a matching of size $k$ is a $k$-sunflower with core $\varnothing$, and a $K_{1,k}$ is a $k$-sunflower with core equal to its center vertex. $\square$

Definition.

Let \[ M(k):=\max\{|E(G)|:\ \Delta(G)\le k-1\ \text{and}\ \nu(G)\le k-1\}, \] where $\Delta(G)$ is maximum degree and $\nu(G)$ is maximum matching size. By Lemma 20.4, \begin{equation} f(2,k)=M(k)+1. \tag{5.1} \end{equation}

Theorem 20.5 (Exact value of $f(2,k)$ for all $k$).

For every integer $k\ge 2$, \[ f(2,k)= \begin{cases} k(k-1)+1, & k\ \text{odd},\\[4pt] \Big\lfloor \dfrac{(k-1)(2k-1)}{2}\Big\rfloor + 1, & k\ \text{even}. \end{cases} \] Moreover, the lower bounds are attained by explicit $k$-sunflower-free graphs described below.

Proof. We split into lower bounds (constructions) and the matching upper bound.

Step 1: Lower bounds (explicit constructions).

Case 1: $k$ odd. Let $G$ be the disjoint union of two cliques $K_k\cup K_k$. Then $\Delta(G)=k-1$, and \[ |E(G)|=2\binom{k}{2}=k(k-1). \] Each $K_k$ (with $k$ odd) has matching number $(k-1)/2$, hence \[ \nu(G)=2\cdot\frac{k-1}{2}=k-1, \] so $G$ has no matching of size $k$. Also $\Delta(G)=k-1$ rules out $K_{1,k}$. By Lemma 20.4, this graph is $k$-sunflower-free, so \begin{equation} M(k)\ge k(k-1)\qquad (k\ \text{odd}). \tag{5.2} \end{equation}

Case 2: $k$ even. Set $N:=2k-1$ and label vertices by $\mathbb Z/N\mathbb Z$. Let $H$ be the circulant graph on $\mathbb Z/N\mathbb Z$ with step set \[ S:=\{\pm 1,\pm 2,\dots,\pm (k/2-1)\},\] so every vertex has degree $k-2$ in $H$. Consider the cycle $C$ whose edges are the "step $k/2$" edges \[ \{\{x,x+k/2\}: x\in\mathbb Z/N\mathbb Z\}. \] Since $\gcd(k/2,N)=1$, these edges form a single cycle of length $N$. Let $M$ be a maximum matching in this cycle $C$, so $|M|=\lfloor N/2\rfloor = k-1$ and exactly one vertex (say $0$) is uncovered. Define $G:=H\cup M$. Then in $G$, every vertex covered by $M$ has degree $(k-2)+1=k-1$, while the uncovered vertex has degree $k-2$. Hence $\Delta(G)=k-1$. The number of edges is \[ |E(G)|=|E(H)|+|M|=\frac{N(k-2)}{2}+(k-1)=\frac{k(2k-3)}{2}=\Big\lfloor\frac{(k-1)(2k-1)}{2}\Big\rfloor. \] Because $|V(G)|=2k-1<2k$, $G$ cannot contain a matching of size $k$. Also $\Delta(G)=k-1$ rules out $K_{1,k}$. Thus $G$ is $k$-sunflower-free, and \begin{equation} M(k)\ge \Big\lfloor\frac{(k-1)(2k-1)}{2}\Big\rfloor\qquad (k\ \text{even}). \tag{5.3} \end{equation}

Step 2: Matching upper bounds (Abbott--Hanson--Sauer).

We now invoke the following sharp extremal result.

Theorem 20.6 (Abbott--Hanson--Sauer, 1972; as stated in [Kupavskii2025, Thm. 3.2]). Let $s\ge 2$ and let $G$ be a graph with no matching of size $s$ and no vertex of degree $s$. Then \[ |E(G)|\le \begin{cases} s(s-1), & s\ \text{odd},\\ (s-1)^2+\dfrac{s-2}{2}, & s\ \text{even}. \end{cases} \]

Applying Theorem 20.6 with $s=k$: The conditions "no vertex of degree $k$" and "no matching of size $k$" are exactly \[ \Delta(G)\le k-1\qquad\text{and}\qquad \nu(G)\le k-1. \] Hence for every $k\ge 2$, \begin{equation} M(k)\le \begin{cases} k(k-1), & k\ \text{odd},\\ (k-1)^2+\dfrac{k-2}{2}=\Big\lfloor\dfrac{(k-1)(2k-1)}{2}\Big\rfloor, & k\ \text{even}. \end{cases} \tag{5.4} \end{equation}

Step 3: Conclude $M(k)$ and hence $f(2,k)$. Combining the lower bounds $5.2$--$5.3$ with the upper bounds $5.4$ shows equality holds in both parity cases, i.e., $M(k)$ equals the stated quantity. Finally, $5.1$ gives the displayed formula for $f(2,k)$. $\square$

6) ADVERSARIAL VERIFICATION

(i) Core-size check for Lemma 20.4. For $2$-sets, the core of a sunflower can only have size $0$ or $1$; there is no hidden third case. The proof explicitly splits by $|C|\in\{0,1\}$.

(ii) Boundary cases.

• $k=2$: any two distinct edges form a $2$-sunflower with core their intersection, so $f(2,2)=2$. Theorem 20.5 gives $\lfloor(1\cdot 3)/2\rfloor+1=2$.
• $k=3$: Theorem 20.5 gives $3\cdot 2+1=7$, matching Round 1 Lemma 20.3.
• $k=4$: Theorem 20.5 gives $\lfloor 3\cdot 7/2\rfloor+1=11$; the explicit construction in Step 1 (cycle-plus-matching augmentation) recovers the $10$-edge example on $7$ vertices.

(iii) Construction correctness for even $k$. The only subtle point is that the "step $k/2$" edges form a single odd cycle, so a maximum matching has size $k-1$ and leaves exactly one uncovered vertex. The gcd computation \[\gcd(k/2,2k-1)=1\] is valid because any common divisor divides both $k$ and $2k-1$, hence divides $1$. Also, the added matching edges are not already present in $H$ because the step $k/2$ exceeds the maximum step $(k/2-1)$ used in $H$.

(iv) Dependence on external theorem. The only externally imported fact is Theorem 20.6, used solely to upper-bound $M(k)$. All hypotheses are verified explicitly for $s=k$.

7) FINAL (EXACTLY ONE)

UNRESOLVED (BUT STRICTLY ADVANCED).

The original sunflower conjecture question (existence of $c_k$ with $f(n,k)\le c_k^n$ for all $n$) remains open. However, Round 2 strictly advances the investigation by closing an infinite family of exact cases: the entire $n=2$ slice is solved exactly, yielding an explicit formula for $f(2,k)$ for every $k\ge 2$.

8) COMPLETION ESTIMATE

COMPLETION: 30%

9) REFERENCES

References

• [Kupavskii2025] A. Kupavskii, Erdős's forbidden sunflower problem, arXiv:2511.17142 $2025$. (Theorem 3.2 is used here.)