The cross-intersection product criterion for uniform families

About 8 years old · traced to

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

Aj(k):={A∈([n]k):1∈A}⊔{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):1∈B}∖{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 ∣A∣∣B∣|\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)∣<(n−1k−1)(n−1l−1)|\mathcal A_j^{(k)}||\mathcal B_j^{(l)}|<\binom{n-1}{k-1}\binom{n-1}{l-1} for all j≥0j\geq0, then

M(n,k,l)=(n−1k−1)(n−1l−1).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):i∈A}\mathcal A=\{A\in\binom{[n]}k:i\in A\} and B={B∈([n]l):i∈B}\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 n≥max⁡{2k,2l}n\geq\max\{2k,2l\}; its truth is intended to characterize when stars are optimal and unique.

References

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.