Forbidden intersection problems for families of linear maps

David C Ellis, Guy Kindler, Noam Lifshitz

Research output: Contribution to journalArticle (Academic Journal)peer-review

Abstract

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.
Original languageEnglish
Number of pages32
JournalDiscrete Analysis
Volume19
DOIs
Publication statusPublished - 12 Dec 2023

Fingerprint

Dive into the research topics of 'Forbidden intersection problems for families of linear maps'. Together they form a unique fingerprint.

Cite this