Uniform Set Systems with Uniform Witnesses

Abstract

Frankl--Pach and Erdős conjectured that any $(d+1)$-uniform set family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{d+1}\right)$ with VC-dimension at most $d$ has size at most $\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)$ when $n$ is sufficiently large. Ahlswede and Khachatrian showed that the conjecture is false by giving a counterexample of size $\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)+\left(\genfrac{}{}{0ex}{}{n-4}{d-2}\right)$. For a set family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{d+1}\right)$, the condition that its VC-dimension is at most $d$ can be reformulated as follows: for any $F\in \mathcal{F}$, there exists a set $B_F\subseteq F$ such that $F\cap F^{\prime }\ne B_F$ for all $F^{\prime }\in \mathcal{F}$. In this direction, the first author, Xu, Yip, and Zhang conjectured that the bound $\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)$ holds if we further assume that $|B_F|=s$ for every $F\in \mathcal{F}$ and for some fixed $0\le s\le d$. The case $s=0$ is exactly the Erdős--Ko--Rado theorem, and the cases $s\in \{1,d\}$ were proved in the paper by the first author, Xu, Yip, and Zhang. In this short note, we show that the conjecture holds when $s\le d/2$, and the maximal constructions are stars. Moreover, we construct non-star set families of size $\left(\genfrac{}{}{0ex}{}{n-1}{d}\right)$ satisfying the condition for $d/2<s\le d-1$, which suggests that the problem is substantially different in these cases.

11 pages, included new example