Forbidden intersection problems for families of linear maps

David Ellis ; Guy Kindler ; Noam Lifshitz

Discrete analysis (2023)

Résumé

We study an analogue of the Erdős-Sós forbidden intersection problem, for families of linear maps. If $V$ and $W$ are vector spaces over the same field, we say a family $\mathcal{F}$ of linear maps from $V$ to $W$ is \emph{$(t-1)$-intersection-free} if for any two linear maps $σ_1,σ_2 \in \mathcal{F}$, $\dim(\{v \in V:\ σ_1(v)=σ_2(v)\}) \neq t-1$. We prove that if $n$ is sufficiently large depending on $t$, $q$ is any prime power, $V$ is an $n$-dimensional vector space over $\mathbb{F}_q$, and $\mathcal{F} \subset \textrm{GL}(V)$ is $(t-1)$-intersection-free, then $|\mathcal{F}| \leq \prod_{i=1}^{n-t}(q^n - q^{i+t-1})$. Equality holds only if there exists a $t$-dimensional subspace of $V$ on which all elements of $\mathcal{F}$ agree, or a $t$-dimensional subspace of $V^*$ on which all elements of $\{σ^*:\ σ\in \mathcal{F}\}$ agree. Our main tool is a `junta approximation' result for families of linear maps with a forbidden intersection: namely, that if $V$ and $W$ are finite-dimensional vector spaces over the same finite field, then any $(t-1)$-intersection-free family of linear maps from $V$ to $W$ is essentially contained in a $t$-intersecting \emph{junta} (meaning, a family $\mathcal{J}$ of linear maps from $V$ to $W$ such that the membership of $σ$ in $\mathcal{J}$ is determined by $σ(v_1),\ldots,σ(v_M),σ^*(a_1),\ldots,σ^*(a_N)$, where $v_1,\ldots,v_M \in V$, $a_1,\ldots,a_N \in W^*$ and $M+N$ is bounded). The proof of this in turn relies on a variant of the `junta method' (originally introduced by Dinur and Friedgut, and powefully extended by Keller and the last author), together with spectral techniques and a hypercontractive inequality.

Détail

Publié le : 2023-12-12