Article in press
Authors:
Title:
The number of disjoint pairs in families of $k$-element subsets
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-05-24 , Revised: 2024-11-07 , Accepted: 2024-11-07 , Available online: 2024-11-27 , https://doi.org/10.7151/dmgt.2571
Abstract:
We call a family $\mathcal{F}$ of subsets of $[n]$ intersecting if for every
$A, B \in \mathcal{F}$ it holds that $A \cap B \neq \emptyset$.
The famous theorem of Erdős-Ko-Rado states that the maximal size of an
intersecting family of $k$-element subsets of $[n]$ is $\binom{n-1}{k-1}$, if
$k \leqslant \frac{n}{2}$. In this paper, we study the number of disjoint pairs
of sets in a family of size greater than this. We provide a bound on the number
of disjoint pairs depending on the size of minimum vertex cover of the graph
representation of the family. Moreover, we obtained a new, elementary proof for
a special case of a theorem of Dan, Gas and Sudakov, which claims that the
minimal number of disjoint pairs of sets in set systems of size greater than
$\binom{n-1}{k-1}$ can be obtained by considering families consisting of the
initial segment of lexicographical order. We prove it only for very small
families of size $\binom{n-1}{k-1}+r$, where $r \leqslant \frac{1}{3k!}n^{k-1}$.
Keywords:
family of subsets, Erdős-Ko-Rado theorem, disjoint pairs
References:
- R. Ahlswede and G.O.H. Katona, Graphs with maximal number of adjacent pairs of edges, Acta Math. Acad. Sci. Hungar. 32 (1978) 97–120.
https://doi.org/10.1007/BF01902206 - S. Das, W. Gan and B. Sudakov, The minimum number of disjoint pairs in set systems and related problems, Combinatorica 36 (2016) 623–660.
https://doi.org/10.1007/s00493-014-3133-0 - P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, Q. J. Math. Oxford Ser. 2 12 (1961) 313–320.
https://doi.org/10.1093/qmath/12.1.313 - A. Hilton and E.C. Milner, Some intersection theorems for systems of finite sets, Q. J. Math. Oxford Ser. 2 18 (1967) 369–384.
https://doi.org/10.1093/qmath/18.1.369 - G.O.H. Katona, G.Y. Katona and Zs. Katona, Most probably intersecting families of subsets, Combin. Probab. Comput. 21 (2012) 219–227.
https://doi.org/10.1017/S0963548311000587
Close