The reviewed record of science sign in
Pith

arxiv: 2004.08714 · v3 · pith:45ZMMXHS · submitted 2020-04-18 · math.CO · cs.DM

Almost intersecting families

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:45ZMMXHSrecord.jsonopen to challenge →

classification math.CO cs.DM
keywords mathcalintersectingalmostchoosecalledemptysetfamiliesfamily
0
0 comments X
read the original abstract

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 \emptyset$ 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' = \emptyset$. Gerbner et al. proved that if $n \geq 2k + 2$ then $|\mathcal F| \leq {n - 1\choose k - 1}$ holds for almost intersecting families. The main result implies the considerably stronger and best possible bound $|\mathcal F| \leq {n - 1\choose k - 1} - {n - k - 1\choose k - 1} + 2$ for $n > (2 + o(1))k$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.