alphaFeedback
PDF

WorksMathematics

On supersaturation in the Erdős–Sós problem

Publication details
License
CC BY 4.0
Status
Published
AI contributions
Not recorded for this paper
View details
Abstract · v1

The following classical question in extremal set theory is due to Erdős and Sós: what is the size of the largest family F⊂([n]k)\mathcal F\subset {[n]\choose k} with no two sets F1,F2∈FF_1,F_2\in \mathcal F such that ∣F1∩F2∣=t|F_1\cap F_2| = t? In this paper, we address a supersaturation question for this extremal function. For a family F⊂([n]k)\mathcal F\subset {[n]\choose k} of a fixed size ℓ\ell, what is the smallest number of pairs F1,F2∈FF_1,F_2\in \mathcal F with ∣F1∩F2∣=t|F_1\cap F_2|=t it may induce? For fixed kk and n→∞n\to \infty, we find the exact threshold when the minimum number of pairs matches the expected number of pairs in a random ℓ\ell-element family up to a constant factor. We also find an exact answer for ℓ\ell slightly above the extremal function.

Review conversation

Reviews are not available for this work yet.