Forbidding just one intersection for short integer sequences

Elizaveta Iarovikova, Fedor Noskov, Georgy Sokolov, Nikolai Terekhov · 2025

Read Forbidding just one intersection for short integer sequences by Elizaveta Iarovikova, Fedor Noskov, Georgy Sokolov, Nikolai Terekhov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17544.txt.

Introduction

Elizaveta Iarovikova and three co-authors crack a forbidden-pattern problem about strings of symbols. Take all strings of length n over an alphabet. How large a family can you pick if no two strings are allowed to agree in exactly t minus 1 positions? Agreements in any other number of spots are fine; only that one count is banned. The puzzle descends from a famous Erdős-Sós question.

The team finds the exact maximum family size whenever the alphabet and the length both grow at least polynomially in t. That range reaches far past a recent result by Keevash and co-authors. The proof mixes two modern weapons of extremal combinatorics, spread approximation and hypercontractivity. Such sharp bounds matter wherever near-matching codes must be kept apart.

Catalog record

CREATORElizaveta Iarovikova, Fedor Noskov, Georgy Sokolov, Nikolai Terekhov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE128 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-17544

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Forbidding just one intersection for short integer sequences Elizaveta Iarovikova, Fedor Noskov, Georgy Sokolov, Nikolai Terekhov Abstract In this paper, we study the famous Erdős–Sós forbidden intersection problem for words over alphabet of size m m : what is the maximal size of a subfamily ℱ \mathcal{F} of [ m ] n [m]^{n} that does not contain two vectors x , y x,y that coincide on exactly t − 1 t-1 coordinates? We answer this question provided m ⩾ poly ⁡ ( t ) m\geqslant\poly(t) , n ⩾ poly ⁡ ( t ) n\geqslant\poly(t) for some polynomial function poly ⁡ ( ⋅ ) \poly(\cdot) of t 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. 1 Introduction Let \binom{[n]}{k} be a family of k -subsets of [n]=\{1,\ldots,n\} . In 1971, Erdős and Sós (see [ 19 ] ) considered the following problem. Probem 1 . Fix n\geqslant k\geqslant t\geqslant 1 . What is the maximal size of a family \mathcal{F}\subset\binom{[n]}{k} such that for any F_{1},F_{2}\in\mathcal{F} we have |F_{1}\cap F_{2}|\neq t-1 ? Problem 1 is a harder version of the following question raised by Erdős, Ko and Rado [ 18 ] ten years earlier. Probem 2 . Fix n\geqslant k\geqslant t\geqslant 1 . What is the maximal size of a family \mathcal{F}\subset\binom{[n]}{k} such that for any F_{1},F_{2}\in\mathcal{F} we have |F_{1}\cap F_{2}|\geqslant t ? Erdős, Ko and Rado settled it for n\geqslant n_{0}(k) in the famous Erdős–Ko–Rado theorem [ 18 ] . While Problem 2 was completely solved by Ahlswede and Khachatrian [ 1 ] after several improvements due to Frankl [ 33 ] , Wilson [ 62 ] and Frankl and Füredi [ 24 ] , Problem 1 remains open. Erdős and Sós conjectured 1 1 1 The original conjecture of Erdős and Sós is for families avoiding intersection size 1 , the general case is due to Erdős. that any extremal solution of Problem 1 has the following form: \displaystyle\mathcal{F}_{T}=\left\{F\in\binom{[n]}{k}\;:\;T\subset F\right\} for some set T of size t , provided k\geqslant 2t and n\geqslant n_{0}(k) . 2 2 2 Note that \mathcal{F}_{T} is the unique up to an isomorphism extremal example for Problem 2 if n\geqslant(t+1)(k-t+1) [ 33 , 62 ] . The conjecture was verified by Frankl and Füredi in the seminal paper [ 23 ] . However, the other regimes of parameters, when t and k grow with n , are also important and found numerous applications in discrete geometry [ 28 , 39 ] , communication complexity [ 61 ] and quantum computing [ 6 ] . Great progress on the problem was made by Keller and Lifshitz who solved Problem 1 when n is linear in k [ 48 ] , i.e. n\geqslant f(t)k for some function f(\cdot) . Later, Ellis, Keller and Lifshitz [ 14 ] extended the previous result to the regime when k\leqslant(1/2-\varepsilon)n for any small enough \varepsilon provided n\geqslant n_{0}(t,\varepsilon) . Recently, Kupavskii and Zakharov [ 51 ] managed to solve Problem 1 under the polynomial dependencies between n,k,t , e.g. when n=k^{\alpha} , t=k^{\beta} with 0<\beta<1/2 and \alpha>1+2\beta , provided k\geqslant k_{0}(\alpha,\beta) . Partial results were obtained by Cherkashin [ 8 ] and Keevash, Mubayi and Wilson [ 44 ] . It is also worth mentioning the celebrated Frankl and Wilson result [ 31 ] that bounds the size of \mathcal{F} in Problem 1 by \binom{n}{k-t} provided k\geqslant 2t-1 and k-t+1 is a prime power. In recent decades, a rich and active direction of research has emerged: extending results from extremal set theory to families of various mathematical objects. The aforementioned Erdős–Ko–Rado theorem [ 18 ] has received numerous extensions to families of permutations [ 21 , 7 , 55 , 12 , 51 , 46 , 54 ] , finite vector spaces [ 32 ] , integer sequences [ 2 , 29 ] , matchings [ 40 , 34 ] , independent sets of a graph [ 4 , 5 , 36 , 63 , 26 ] (see also the survey [ 37 ] ) and many other objects [ 9 , 25 , 60 , 38 , 52 , 53 ] (see also the survey [ 17 ] ). In contrast, there are much fewer works on generalization of Problem 1 to other domains, mostly due to its hardness even in the \binom{[n]}{k} case. There are some results for permutations [ 16 , 15 , 43 ] , vector spaces [ 11 ] and integer sequences [ 42 ] . Significant progress in this direction was made by Kupavskii and Zakharov [ 51 ] . In particular, they present results for subfamilies of [m]^{n},\binom{[n]}{k}^{w} , permutations and (n,k,w) -designs. However, assumptions of their theory turn out to be quite restrictive in our setup, which we discuss next. In this paper, we focus on Problem 1 adapted to subfamilies of [m]^{n} for some integers m,n . For two vectors x,y\in[m]^{n} , we define their agreement \operatorname{agr}(x,y) by \displaystyle\operatorname{agr}(x,y)=|\{i\in[n]\;:\;x_{i}=y_{i}\}|. Then, the question we study in this paper is as follows. Probem 3 . Let m,n,t be integers such that m\geqslant 2 and n\geqslant t\geqslant 1 . What is the maximal size of a subfamily \mathcal{F}\subset[m]^{n} such that for any x,y\in\mathcal{F} we have \operatorname{agr}(x,y)\neq t-1 ? We will refer to such families \mathcal{F} as (t-1) -avoiding . Note that for t=1 this problem was resolved independently by Frankl and Tokushige [ 30 ] and Ahlswede and Khachatrian [ 2 ] . A more general result was obtained by Keevash and coauthors [ 42 ] . Theorem 1 (Theorem 1.1 of [ 42 ] ) . Define families \displaystyle\mathcal{S}_{t,r}[m]^{n}=\{x\in[m]^{n}\;:\;|\{j\in[t+2r]\;:\;x_{j}=1\}|\geqslant t+r\}. Then, for any t\in\mathbb{N} there is n_{0} such that if \mathcal{F}\subset[m]^{n} is a (t-1) -avoiding family with m\geqslant 3 and n\geqslant n_{0} , then |\mathcal{F}|\leqslant\max_{r\geqslant 0}|\mathcal{S}_{t,r}[m]^{n}| with equality only if \mathcal{F} is isomorphic to \mathcal{S}_{t,r}[m]^{n} for some r\geqslant 0 . The function n_{0}(t) depends on t super-exponentially in their proof. Observe that when m>t the unique maximum in \max_{r}|\mathcal{S}_{t,r}[m]^{n}| is attained for r=0 . Thus, if m>t , then the only extremal families are t -stars \{x\in[m]^{n}\;:\;x_{T}=z\} for some T\subset[n] of size t and z\in[m]^{T} , provided n\geqslant n_{0}(t) . Another result was obtained by Kupavskii and Zakharov [ 51 ] . Theorem 2 (Proposition 23 of [ 51 ] ) . Suppose that integers m,n,t satisfy m\geqslant\max\{2^{15}\ln n,2^{17}q\ln q\}\text{ and }n\geqslant 2q for q=800t^{2}\ln m . If \mathcal{F}\subset[m]^{n} is a (t-1) -avoiding family and |\mathcal{F}|\geqslant 2/3\cdot m^{n-t} , then there exists a t -star \mathcal{S}_{(T,z)}=\{x\in[m]^{n}\;:\;x_{T}=z\} for some T\subset[n] of size t and z\in[m]^{T} such that |\mathcal{F}\setminus\mathcal{S}_{(T,z)}|\leqslant m^{-4t}|\mathcal{S}_{(T,z)}| . Despite the restrictions m\geqslant 2^{15}\ln n and n\geqslant 1600t^{2}\ln m , their finding suggests that the result of Theorem 1 can be potentially obtained when m,n depend polynomially on t . Thus, it is natural to conjecture that the conclusion of Theorem 1 holds when m\geqslant\poly(t) and n\geqslant\poly(t) , without logarithmic lower bounds on m and n . Here \poly(\cdot) hides some polynomial functions. Our main result confirms this conjecture. Theorem

Read the complete text