Forbidden intersection problems for families of linear maps

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 $k<n/2$, then equality is attained if and only if there is some $i$ such that the family consists of all subsets that contain the element $i$. (If $k>n/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<2k$). Ahlswede and Khachatrian showed that every $t$-intersecting family of maximal size is given by one of these more general examples.

The study of $s$-intersection-free systems is harder than that of $t$-intersecting families, because the condition is not monotone, which rules out many approaches. Some impressive results have nevertheless been obtained, with the help of a wide variety of methods, including dimension arguments, Fourier analysis, and purely combinatorial techniques.
Of course, a $t$-intersecting family is necessarily $(t-1)$-intersection free, so the maximum size of a $(t-1)$-intersection-free family is necessarily at least the maximum size of a $t$-intersecting family. A heuristic meta-conjecture is that in many cases these maxima are in fact equal: that is, the best way to ensure that a set system does not have any intersections of size $t-1$ is to ensure that all intersections are of size at least $t$.

In this paper the authors consider an analogue of the problem for linear maps between vector spaces. If $V$ and $W$ are finite-dimensional vector spaces over the field $\mathbb F_q$ for some prime power $q$, and if $\alpha$ and $\beta$ are linear maps from $V$ to $W$, then the analogue of the intersection that they consider is the dimension of the kernel of $\alpha-\beta$ – that is, the dimension of the subspace of $V$ on which $\alpha$ and $\beta$ agree. Thus, a family $\mathcal F$ of linear maps from $V$ to $W$ is $t$-intersecting if $\dim\ker(\alpha-\beta)\geq t$ for every $\alpha,\beta\in\mathcal F$, and it is $s$-intersection free if it is not possible to find $\alpha,\beta\in\mathcal F$ with $\dim\ker(\alpha-\beta)=s$.

Suppose one wishes to find a large $t$-intersecting collection of linear maps from $V$ to $W$. As with families of sets, there is an obvious example: simply fix a $t$-dimensional subspace $U$ of $V$ and take all linear maps $\alpha$ such that $U\subset\ker\alpha$. Slightly more generally, one can take a translate of this example: that is, one can fix some linear map $\alpha_0$ and take all linear maps $\alpha$ such that $U\subset\ker(\alpha-\alpha_0)$, or in other words, a maximal family of linear maps that all agree on $U$.

Unlike with the sets case, there is a second natural example, only slightly less obvious than the first. Since the rank of a linear map is equal to the rank of its adjoint (or in matrix terms, row-rank equals column-rank), we can pick a $t$-dimensional subspace $Y^*$ of $W^*$ and take a maximal family of linear maps $\alpha$ such that the adjoint maps $\alpha^*$ all agree on $Y^*$.

The precise problem considered by the authors concerns invertible maps, in which case we may as well take $V$ and $W$ to be equal. They show that if $n$ is sufficiently large, and if $\mathcal F$ is a $(t-1)$-intersection-free family of invertible linear maps from $V$ to $V$ of maximal size, then either there must exist a subspace $U\subset V$ of dimension $t$ such that all the maps in $\mathcal F$ agree on $U$, or there must be a subspace $U^*\subset V^*$ of dimension $t$ such that all the adjoints of the maps in $\mathcal F$ agree on $U^*$.

This considerably strengthens a recent result of Ernst and Schmidt, who proved the same result for $t$-intersecting families, but without characterizing the equality cases and with a more complicated proof.

The proof follows a similar structure to that of a result of two of the authors concerning intersecting families of permutations (where the “intersection” of two permutations is taken to be the set on which they agree). However, in this context an additional ingredient is required, namely a difficult new hypercontractivity inequality for functions defined on $L(V,W)$, the space of linear maps from $V$ to $W$. In its strongest form, the inequality can be found in another paper by the same authors, but here a weaker version with a simpler proof, given in the paper, suffices. This is used to show that a $(t-1)$-intersection-free family is approximately contained in a $t$-intersecting “junta”, which is roughly speaking a family $\mathcal F$ of linear maps such that whether or not $\alpha$ belongs to $\mathcal F$ depends only on a few values of $\alpha$ and $\alpha^*$.