Pith. sign in

Sunflowers and Ramsey problems for restricted intersections

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
abstract

Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 years. In this paper, we study the following Ramsey version of these problems. Given a set $L\subseteq \{0,\dots,k-1\}$ and a family $\mathcal{F}$ of $k$-element sets which does not contain a sunflower with $m$ petals whose kernel size is in $L$, how large a subfamily of $\mathcal{F}$ can we find in which no pair has intersection size in $L$? We give matching upper and lower bounds, determining the dependence on $m$ for all $k$ and $L$. This problem also finds applications in quantum computing. As an application of our techniques, we also obtain a variant of F\"uredi's celebrated semilattice lemma, which is a key tool in the powerful delta-system method. We prove that one cannot remove the double-exponential dependency on the uniformity in F\"uredi's result, however, we provide an alternative with significantly better, single-exponential dependency on the parameters, which is still strong enough for most applications of the delta-system method.

fields

math.CO 1

years

2025 1

verdicts

CONDITIONAL 1

representative citing papers

Delta-system method: a survey

math.CO · 2025-08-26 · conditional · novelty 3.0

A survey of the Delta-system (sunflower) method in extremal set theory, with proofs of key theorems and a broad literature review.

citing papers explorer

Showing 1 of 1 citing paper.

  • Delta-system method: a survey math.CO · 2025-08-26 · conditional · none · ref 76 · internal anchor

    A survey of the Delta-system (sunflower) method in extremal set theory, with proofs of key theorems and a broad literature review.