TY - JOUR

T1 - Forbidden intersection problems for families of linear maps

AU - Ellis, David C

AU - Kindler, Guy

AU - Lifshitz, Noam

PY - 2023/12/12

Y1 - 2023/12/12

N2 - 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 F of linear maps from V to W is \emph{(t−1)-intersection-free} if for any two linear maps σ1,σ2∈F, dim({v∈V: σ1(v)=σ2(v)})≠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 Fq, and F⊂GL(V) is (t−1)-intersection-free, then |F|≤∏n−ti=1(qn−qi+t−1). Equality holds only if there exists a t-dimensional subspace of V on which all elements of F agree, or a t-dimensional subspace of V∗ on which all elements of {σ∗: σ∈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 J of linear maps from V to W such that the membership of σ in J is determined by σ(v1),…,σ(vM),σ∗(a1),…,σ∗(aN), where v1,…,vM∈V, a1,…,aN∈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.

AB - 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 F of linear maps from V to W is \emph{(t−1)-intersection-free} if for any two linear maps σ1,σ2∈F, dim({v∈V: σ1(v)=σ2(v)})≠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 Fq, and F⊂GL(V) is (t−1)-intersection-free, then |F|≤∏n−ti=1(qn−qi+t−1). Equality holds only if there exists a t-dimensional subspace of V on which all elements of F agree, or a t-dimensional subspace of V∗ on which all elements of {σ∗: σ∈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 J of linear maps from V to W such that the membership of σ in J is determined by σ(v1),…,σ(vM),σ∗(a1),…,σ∗(aN), where v1,…,vM∈V, a1,…,aN∈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.

U2 - 10.48550/arXiv.2208.04674

DO - 10.48550/arXiv.2208.04674

M3 - Article (Academic Journal)

SN - 2397-3129

VL - 19

JO - Discrete Analysis

JF - Discrete Analysis

ER -