Intersection theorems for $\{0,\pm 1\}$-vectors and $s$-cross-intersecting families

Abstract

In this paper we study two directions of extending the classical Erd\H os-Ko-Rado theorem which states that any family of $k$-element subsets of the set $[n]=\{1,\dots ,n\}$ in which any two sets intersect, has cardinality at most $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$. In the first part of the paper we study the families of $\{0,\pm 1\}$-vectors. Denote by ${\mathcal{L}}_k$ the family of all vectors $\mathbf{v}$ from $\{0,\pm 1{\}}^n$ such that $⟨\mathbf{v},\mathbf{v}⟩=k$. For any $k$, most $l$ and sufficiently large $n$ we determine the maximal size of the family $\mathcal{V}\subset {\mathcal{L}}_k$ such that for any $\mathbf{v},\mathbf{w}\in \mathcal{V}$ we have $⟨\mathbf{v},\mathbf{w}⟩\ge l$. We find some exact values of this function for all $n$ for small values of $k$. In the second part of the paper we study cross-intersecting pairs of families. We say that two families are $\mathcal{A},\mathcal{B}$ are \textit{$s$-cross-intersecting}, if for any $A\in \mathcal{A},B\in \mathcal{B}$ we have $|A\cap B|\ge s$. We also say that a set family $\mathcal{A}$ is {\it $t$-intersecting}, if for any $A_1,A_2\in \mathcal{A}$ we have $|A_1\cap A_2|\ge t$. For a pair of nonempty $s$-cross-intersecting $t$-intersecting families $\mathcal{A},\mathcal{B}$ of $k$-sets, we determine the maximal value of $|\mathcal{A}|+|\mathcal{B}|$ for $n$ sufficiently large.

This version contains a correction of an error, kindly pointed out to us by Danila Cherkashin and Sergei Kiselev. Notably, the statement of Theorem 5 part 2 is different

References in corpus (1)

• Erd\H os-Ko-Rado theorem for $\{0,\pm 1\}$-vectors