TY - GEN

T1 - On symmetric intersecting families

AU - Ellis, David

AU - Kalai, Gil

AU - Narayanan, Bhargav

PY - 2020/2/18

Y1 - 2020/2/18

N2 - A family of sets is said to be \emph{symmetric} if its automorphism group is transitive, and \emph{intersecting} if any two sets in the family have nonempty intersection. Our purpose here is to study the following question: for $n, k\in \mathbb{N}$ with $k \le n/2$, how large can a symmetric intersecting family of $k$-element subsets of $\{1,2,\ldots,n\}$ be? As a first step towards a complete answer, we prove that such a family has size at most \[\exp\left(-\frac{c(n-2k)\log n}{k( \log n - \log k)} \right) \binom{n}{k},\ ] where $c > 0$ is a universal constant. We also describe various combinatorial and algebraic approaches to constructing such families.

AB - A family of sets is said to be \emph{symmetric} if its automorphism group is transitive, and \emph{intersecting} if any two sets in the family have nonempty intersection. Our purpose here is to study the following question: for $n, k\in \mathbb{N}$ with $k \le n/2$, how large can a symmetric intersecting family of $k$-element subsets of $\{1,2,\ldots,n\}$ be? As a first step towards a complete answer, we prove that such a family has size at most \[\exp\left(-\frac{c(n-2k)\log n}{k( \log n - \log k)} \right) \binom{n}{k},\ ] where $c > 0$ is a universal constant. We also describe various combinatorial and algebraic approaches to constructing such families.

UR - https://arxiv.org/abs/1702.02607

M3 - Other contribution

T3 - European Journal of Combinatorics

CY - European Journal of Combinatorics

ER -