Sunflowers and Ramsey problems for restricted intersections

Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 year. 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üredi'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üredi'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.

Publication Details

Journal
ArXiv.org
Published
2025-04-21
Primary Topic
Limits and Structures in Graph Theory
Type
article
Field-Weighted Citation Impact
0.00

Funders

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Sunflowers and Ramsey problems for restricted intersections

ArXiv.org
Limits and Structures in Graph Theory
article

Sunflowers and Ramsey problems for restricted intersections

article en

Abstract

Extremal problems on set systems with restricted intersections have been an important part of combinatorics in the last 70 year. 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üredi'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üredi'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.

ArXiv.org
National Science Foundation, École Polytechnique Fédérale de Lausanne, Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung
Openalex Percentile: Top 43%
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.