Forbidding just one intersection for short integer sequences

2025/12/19 by Iarovikova, Elizaveta, Noskov, Fedor, Sokolov, Georgy +1
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2512.17544

Abstract

In this paper, we study the famous Erdős--Sós forbidden intersection problem for words over alphabet of size m: what is the maximal size of a subfamily F of [m]ⁿ that does not contain two vectors x, y that coincide on exactly t - 1 coordinates? We answer this question provided m ≥ poly(t), n ≥ poly(t) for some polynomial function poly(⋅) of t, greatly extending the recent result of Keevash, Lifshitz, Long and Minzer. Our proof combines some of the recently developed methods in extremal combinatorics, including the spread approximation technique of Kupavskii and Zakharov, and the hypercontractivity approach developed in a series of works of Keevash, Keller, Lifshitz, Long, Marcus and Minzer.

Citations

• The Forbidden Cross Intersection Problem for Permutations
• Intersecting Families of Spanning Trees
• A Survey of the Holroyd-Talbot Conjecture
• Linear dependencies, polynomial factors in the Duke--Erd\H os forbidden sunflower problem
• Completing the proof of the Liebeck--Nikolov--Shalev conjecture
• Initiating the proof of the Liebeck--Nikolov--Shalev conjecture
• On set systems without singleton intersections
• On intersecting families of subgraphs of perfect matchings
• Intersection theorems for uniform subfamilies of hereditary families
• Sharp Hypercontractivity for Global Functions
• On t-Intersecting Families of Permutations
• On the Holroyd-Talbot Conjecture for Sparse Graphs
• Spread approximations for forbidden intersections problems
• Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New
• Forbidden intersections for codes
• Global hypercontractivity and its applications
• Hypercontractivity on the symmetric group
• Approximation by juntas in the symmetric group, and forbidden intersection problems
• Improved bounds for the sunflower lemma
• On set systems without a simplex-cluster and the Junta method
• Stability versions of Erdős-Ko-Rado type theorems, via isoperimetry
• Forbidding just one intersection, for permutations
• An Erdős--Ko--Rado theorem for matchings in the complete graph
• Analysis of Boolean Functions
• Intersecting Families of Permutations
• Quantum vs. Classical Communication and Computation
• A complete t-intersection theorem for families of spanning trees
• An almost complete t-intersection theorem for permutations

Related

• Forbidden intersections for codes
• Intersection Problems in Extremal Combinatorics: Theorems, Techniques and Questions Old and New
• Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós
• On the minimum size of maximal k-wise intersecting families
• The Forbidden Cross Intersection Problem for Permutations