The Erdős-Ko-Rado Theorem in ${\ell }_2$-Norm

Abstract

The codegree squared sum ${\mathrm{co}}_2(\mathcal{F})$ of a family (hypergraph) $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ is defined to be the sum of codegrees squared $d(E{)}^2$ over all $E\in \left(\genfrac{}{}{0ex}{}{[n]}{k-1}\right)$, where $d(E)=|\{F\in \mathcal{F}:\mathcal{E}\subseteq \mathcal{F}\}|$. Given a family of $k$-uniform families $\mathcal{H}$, Balogh, Clemen and Lidický recently introduced the problem to determine the maximum codegree squared sum ${\mathrm{co}}_2(\mathcal{F})$ over all $\mathcal{H}$-free $\mathcal{F}$. In the present paper, we consider the families which has as forbidden configurations all pairs of sets with intersection sizes less than $t$, that is, the well-known $t$-intersecting families. We prove the following Erdős-Ko-Rado Theorem in ${\ell }_2$-norm, which confirms a conjecture of Brooks and Linz. Let $t,k,n$ be positive integers such that $t\le k\le n$. If a family $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{k}\right)$ is $t$-intersecting, then for $n\ge (t+1)(k-t+1)$, we have \[{\rm co}_2(\cal F)\le {\binom{n-t}{k-t}}(t+(n-k+1)(k-t)),\] equality holds if and only if $\mathcal{F}=\{F\in (\genfrac{}{}{0ex}{}{[n]}{k}):T\subset F\}$ for some $t$-subset $T$ of $[n]$. In addition, we prove a Frankl-Hilton-Milner Theorem in ${\ell }_2$-norm for $t\ge 2$, and a generalized Turán result, i.e., we determine the maximum number of copies of tight path of length 2 in $t$-intersecting families.

20 pages

References in corpus (1)

• Solving Turán's Tetrahedron Problem for the ${\ell }_2$-Norm