Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2512.17544 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915737502744576 |
|---|---|
| author | Iarovikova, Elizaveta Noskov, Fedor Sokolov, Georgy Terekhov, Nikolai |
| author_facet | Iarovikova, Elizaveta Noskov, Fedor Sokolov, Georgy Terekhov, Nikolai |
| contents | In this paper, we study the famous Erdős--Sós forbidden intersection problem for words over an alphabet of size $m$: what is the maximal size of a subfamily $\mathcal{F}$ of $[m]^n$ that does not contain two vectors $x, y$ coinciding on exactly $t - 1$ coordinates? We answer this question provided $m \ge \operatorname{poly}(t)$ and $n \ge \operatorname{poly}(t)$ for some polynomial function $\operatorname{poly}(\cdot)$ 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 by Keevash, Keller, Lifshitz, Long, Marcus and Minzer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_17544 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Forbidding just one intersection for short integer sequences Iarovikova, Elizaveta Noskov, Fedor Sokolov, Georgy Terekhov, Nikolai Combinatorics In this paper, we study the famous Erdős--Sós forbidden intersection problem for words over an alphabet of size $m$: what is the maximal size of a subfamily $\mathcal{F}$ of $[m]^n$ that does not contain two vectors $x, y$ coinciding on exactly $t - 1$ coordinates? We answer this question provided $m \ge \operatorname{poly}(t)$ and $n \ge \operatorname{poly}(t)$ for some polynomial function $\operatorname{poly}(\cdot)$ 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 by Keevash, Keller, Lifshitz, Long, Marcus and Minzer. |
| title | Forbidding just one intersection for short integer sequences |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.17544 |