On the ratio of maximum and minimum degree in maximal intersecting families

NEW

Problem: Let $[n]=\{1,\dots,n\}$. For $\mathcal F\subseteq\binom{[n]}r$, write

Assume $\bigcup\mathcal F=[n]$, so $\delta(\mathcal F)>0$. The family is maximal intersecting if it is intersecting and every $r$-set outside $\mathcal F$ is disjoint from some member of $\mathcal F$. Define

over all such maximal intersecting $\mathcal F\subseteq\binom{[n]}r$.

The conjecture states that for every sequence $r=r(n)=o(n)$, one has $M(n,r)=\Theta(n)$.

Result: The conjecture is false.

For $r\ge2$ and $n\ge2r$, set

Define

Then $\mathcal F\subseteq\binom{[n]}r$, $\bigcup\mathcal F=[n]$, and $\mathcal F$ is intersecting: any two $r$-subsets of $U$, with $|U|=2r-1$, intersect; $\{1\}\cup C$ and every $C\cup\{i\}$ meet all members through $C$, except possibly $D$, which was excluded.

Maximality: let $T\in\binom{[n]}r\setminus\mathcal F$. If $T\subseteq[2r]$, then either $T=D$, disjoint from $\{1\}\cup C$, or $1\in T\neq\{1\}\cup C$, in which case $[2r]\setminus T\in\binom Ur\setminus\{D\}$ is disjoint from $T$.

If $T$ uses outside vertices, let $P=T\cap[2r]$, so $|P|\le r-1$. If no member of $\binom Ur\setminus\{D\}\cup\{\{1\}\cup C\}$ is disjoint from $P$, then $P$ is a transversal of that core family. The only such transversal of size at most $r-1$ is $C$: otherwise $U\setminus P$ contains an $r$-set different from $D$, disjoint from $P$. Hence $P=C$ and $T=C\cup\{i\}\in\mathcal F$, contradiction. Thus some member of $\mathcal F$ is disjoint from $T$. So $\mathcal F$ is maximal.

Degrees satisfy

while for every $c\in C$,

Thus

Choose $n=2^r$. Then $r=o(n)$, but

So $M(n,r)$ is not $O(n)$ along a sequence with $r=o(n)$. Hence the conjectured $\Theta(n)$ bound is false.

Citation: Definitions and conjecture: Z. L. Nagy, L. Özkahya, B. Patkós, M. Vizer, “On the ratio of maximum and minimum degree in maximal intersecting families,” Discrete Mathematics 313 (2013), 207–211; arXiv:1109.1079, Conjecture 2.3. The counterexample above is self-contained.