An Erdős--Ko--Rado theorem for cross-intersecting families in the Euclidean inner product

Jiang-Chao Wan; Yi Wang

paper

An Erdős--Ko--Rado theorem for cross-intersecting families in the Euclidean inner product

arXiv:2608.17219

Abstract

Let $(k [ n ])$ be the set of all $k$ -element subsets of the set ${1, \dots, n}$ and let $A, B \subseteq (k [ n ])$ be two cross-intersecting families, that is, $A \cap B \neq = \emptyset$ for any $A \in A$ and $B \in B$ . The classical cross-intersecting version of the Erdős--Ko--Rado theorem, due to Pyber and Matsumoto--Tokushige, states that if $n \geq 2 k$ , then $∣ A ∣∣ B ∣ \leq (k - 1 n - 1)^{2},$ where the equality holds for $n > 2 k$ if and only if $A = B$ is a star. In the present paper, we first give a stability result of this theorem by using Filmus's FKN theorem on the slice and linear algebra method as follows: There exists a constant $C > 1$ such that if $n \geq 2.07 k$ and $∣ A ∣∣ B ∣ \geq (1 - ε) (k - 1 n - 1)^{2}$ , where $ε \leq \frac{k ^{2}}{C ^{2} n ^{2}}$ , then there is a star $S$ such that $∣ S Δ A ∣ \leq C ε (k n)$ and $∣ S Δ B ∣ \leq C ε (k n) .$ Moreover, based on this stability result and the eigenvalues of the matrices of the Johnson scheme, we present an Erdős--Ko--Rado theorem for cross-intersecting families in the Euclidean inner product showing that if $n \geq 2 k$ and $k \geq d \geq 0$ , then $⟨ v_{d} (A), v_{d} (B) ⟩ \leq \frac{( d k ) ( d k - 1 )}{( d n - 1 )} (k - 1 n - 1)^{2} + (d - 1 k - 1) (k - d n - d - 1) (k - 1 n - 1),$ together with uniqueness and a corresponding stability result, where $v_{d} (A) \in R^{(d [ n ])}$ is the $d$ -degree vector of $A$ whose $U$ -entry is the number of members in $A$ containing $U$ .