The cross-intersection product criterion for uniform families

Let n,k,ln,k,l be positive integers with k+l<n<max{2k,2l}k+l<n<\max\{2k,2l\}. For each j0j\geq 0, let

Aj(k):={A([n]k):1A}{A([n]k):A[j+2]=[j+2]{1}},\mathcal A_j^{(k)}:=\{A\in\binom{[n]}k:1\in A\}\sqcup\{A\in\binom{[n]}k:A\cap[j+2]=[j+2]\setminus\{1\}\},

and

Bj(l):={B([n]l):1B}{B([n]l):B[j+2]={1}}.\mathcal B_j^{(l)}:=\{B\in\binom{[n]}l:1\in B\}\setminus\{B\in\binom{[n]}l:B\cap[j+2]=\{1\}\}.

Let M(n,k,l)M(n,k,l) be the maximum of AB|\mathcal A||\mathcal B| over cross-intersecting families A([n]k)\mathcal A\subset\binom{[n]}k and B([n]l)\mathcal B\subset\binom{[n]}l. The cross-intersection product criterion. If Aj(k)Bj(l)<(n1k1)(n1l1)|\mathcal A_j^{(k)}||\mathcal B_j^{(l)}|<\binom{n-1}{k-1}\binom{n-1}{l-1} for all j0j\geq0, then

M(n,k,l)=(n1k1)(n1l1).M(n,k,l)=\binom{n-1}{k-1}\binom{n-1}{l-1}.

Moreover, every pair of cross-intersecting families attaining this maximum is a pair of common stars: there is some i[n]i\in[n] such that A={A([n]k):iA}\mathcal A=\{A\in\binom{[n]}k:i\in A\} and B={B([n]l):iB}\mathcal B=\{B\in\binom{[n]}l:i\in B\}. The criterion addresses the unresolved range k+l<n<max{2k,2l}k+l<n<\max\{2k,2l\}, extending the known star-product result beyond the cases nmax{2k,2l}n\geq\max\{2k,2l\}; its truth is intended to characterize when stars are optimal and unique.

Sources & referencesView supporting material

Primary source

Norihide Tokushige, “When are stars the largest cross intersecting families?”, arXiv:1810.06820 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.