Forbidden intersection problems for families of linear maps

• Published in: Discrete analysis 2023-12
• Main Authors: David Ellis, Guy Kindler, Noam Lifshitz
• Format: Article
• Language: English
• ISSN: 2397-3129
• DOI: 10.19086/da.90718

Forbidden intersection problems for families of linear maps, Discrete Analysis 2023:19, 32 pp. A central problem in extremal combinatorics is to determine the maximal size of a set system given constraints on the sizes of the sets in the system and on the sizes of their intersections. For example, a special case of the famous Erdős-Ko-Rado theorem states that the largest family of subsets of $\{1,2,\dots,n\}$ of size $k$ such that any two members of the family have a non-empty intersection is, provided that $k\leq n/2$, $\binom{n-1}{k-1}$, and that if $kn/2$, then the question is trivial since any two sets of size $k$ intersect, and if $k=n/2$ one can take as an alternative best possible construction all sets of size greater than $n/2$ together with exactly one of $A$ and $A^c$ for each set $A$ of size $n/2$.) A family is called $t$-_intersecting_ if any two sets in the family intersect in a set of size at least $t$, and $s$-_intersection free_ if no two sets in the family have an intersection of size exactly $s$. The general form of the Erdős-Ko-Rado theorem is that for sufficiently large $n$, a maximal-sized $t$-intersecting family of sets of size $k$ must consist of all sets of size $k$ that contain some given set of size $t$. A remarkable theorem of Ahlswede and Khachatrian, which solved a long-standing open problem, answers the question of what happens when we drop the condition that $n$ is sufficiently large. The obvious way to force two sets to have an intersection of size at least $t$ is to insist that the contains some given set of size $t$, but a more general way is to insist that they each intersect a given set of size $r$ in at least $(t+r)/2$ elements, and sometimes this leads to larger families (as indeed it did in the trivial case mentioned above, which corresponds to taking $t=1$ and $r=n$ with $n