Let $n > k > 1$ be integers, $[n] = \{1, \ldots, n\}$. Let $\mathcal F$ be a family of $k$-subsets of $[n]$. The family $\mathcal F$ is called intersecting if $F \cap F' \neq \varnothing$ for all $F, F' \in \mathcal F$. It is called almost intersecting if it is not intersecting but to every $F \in \mathcal F$ there is at most one $F'\in \mathcal F$ satisfying $F \cap F' = \varnothing$. Gerbner et al. proved that if $n \geq 2k + 2$ then $|\mathcal F| \leqslant {n - 1\choose k - 1}$ holds for almost intersecting families. Our main result implies the considerably stronger and best possible bound $|\mathcal F| \leqslant {n - 1\choose k - 1} - {n - k - 1\choose k - 1} + 2$ for $n > (2 + o(1))k$, $k\ge 3$.
@article{10_37236_9609,
author = {Peter Frankl and Andrey Kupavskii},
title = {Almost intersecting families},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {2},
doi = {10.37236/9609},
zbl = {1461.05231},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9609/}
}
TY - JOUR
AU - Peter Frankl
AU - Andrey Kupavskii
TI - Almost intersecting families
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/9609/
DO - 10.37236/9609
ID - 10_37236_9609
ER -
%0 Journal Article
%A Peter Frankl
%A Andrey Kupavskii
%T Almost intersecting families
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/9609/
%R 10.37236/9609
%F 10_37236_9609
Peter Frankl; Andrey Kupavskii. Almost intersecting families. The electronic journal of combinatorics, Tome 28 (2021) no. 2. doi: 10.37236/9609
