Geodesic
Forbidden sparse intersections
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e99

Voir la notice de l'article provenant de la source Cambridge University Press

Let n be a positive integer, let $0, and let $\ell \leqslant pn$ be a nonnegative integer. We prove that if $\mathcal {F},\mathcal {G}\subseteq \{0,1\}^n$ are two families whose cross intersections forbid $\ell $—that is, they satisfy $|A\cap B|\neq \ell $ for every $A\in \mathcal {F}$ and every $B\in \mathcal {G}$ – then, setting $t:= \min \{\ell ,pn-\ell \}$, we have the subgaussian bound $$\begin{align*}\mu_p(\mathcal{F})\, \mu_{p'}(\mathcal{G}) \leqslant 2\exp\Big( - \frac{t^2}{58^2\,pn}\Big), \end{align*}$$where $\mu _p$ and $\mu _{p'}$ denote the p-biased and $p'$-biased measures on $\{0,1\}^n$, respectively. 
Karamanlis, Miltiadis; Dodos, Pandelis. Forbidden sparse intersections. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e99. doi: 10.1017/fms.2025.10067
@article{10_1017_fms_2025_10067,
     author = {Karamanlis, Miltiadis and Dodos, Pandelis},
     title = {Forbidden sparse intersections},
     journal = {Forum of Mathematics, Sigma},
     pages = {e99},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.10067},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10067/}
}
TY  - JOUR
AU  - Karamanlis, Miltiadis
AU  - Dodos, Pandelis
TI  - Forbidden sparse intersections
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e99
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10067/
DO  - 10.1017/fms.2025.10067
ID  - 10_1017_fms_2025_10067
ER  - 
%0 Journal Article
%A Karamanlis, Miltiadis
%A Dodos, Pandelis
%T Forbidden sparse intersections
%J Forum of Mathematics, Sigma
%D 2025
%P e99
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.10067/
%R 10.1017/fms.2025.10067
%F 10_1017_fms_2025_10067

[AK97] Ahlswede, R. and Khachatrian, L. H., ‘The complete intersection theorem for systems of finite sets’, European J. Combin. 18 (1997), 125–136.10.1006/eujc.1995.0092 Google Scholar | DOI

[AK99] Ahlswede, R. and Khachatrian, L. H., ‘A pushing-pulling method: new proofs of intersection theorems’, Combinatorica 19 (1999), 1–15.10.1007/s004930050042 Google Scholar | DOI

[AS16] Alon, N. and Spencer, J. H., The Probabilistic Method (Wiley-Interscience Series in Discrete Mathematics and Optimization) (John Wiley & Sons, 2016). Google Scholar

[Ash65] Ash, R. B., Information Theory (John Wiley & Sons, 1965). Google Scholar

[BHT06] Bobkov, S. G., Houdré, C. and Tetali, P., ‘The subgaussian constant and concentration inequalities’, Israel J. Math. 156 (2006), 255–283.10.1007/BF02773835 Google Scholar | DOI

[BL91] Bollobás, B. and Leader, I., ‘Isoperimetric inequalities and fractional set systems’, J. Combin. Theory Ser. A 56 (1991), 63–74.10.1016/0097-3165(91)90022-9 Google Scholar | DOI

[BCW99] Buhrman, H., Cleve, R. and Wigderson, A., ‘Quantum vs. classical communication and computation’, in STOC ’98 (Dallas, TX) (ACM, New York, 1999), 63–68. Google Scholar

[El22] Ellis, D., ‘Intersection problems in extremal combinatorics: theorems, techniques and questions old and new’, in Surveys in Combinatorics 2022 (London Math. Soc. Lecture Note Series) vol. 481 (2022), 115–173. Google Scholar

[EKL24] Ellis, D., Keller, N. and Lifshitz, N., ‘Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós’, J. Eur. Math. Soc. 26 (2024), 1611–1654.10.4171/jems/1441 Google Scholar | DOI

[Erd75] Erdős, P., ‘Problems and results in graph theory and combinatorial analysis’, in Proc. 5th British Combinatorial Conference (1975), 169–192. Google Scholar

[EKR61] Erdős, P., Ko, C. and Rado, R., ‘Intersection theorems for systems of finite sets’, Quart. J. Math. 12 (1961), 313–320.10.1093/qmath/12.1.313 Google Scholar | DOI

[Fi13] Filmus, Y., Spectral Methods in Extremal Combinatorics, Ph.D. dissertation, University of Toronto, 2013. Google Scholar

[Fi17] Filmus, Y., ‘The weighted complete intersection theorem’, J. Combin. Theory Ser. A 151 (2017), 84–101.10.1016/j.jcta.2017.04.008 Google Scholar | DOI

[FF85] Frankl, P. and Füredi, Z., ‘Forbidding just one intersection’, J. Combin. Theory Ser. A 39 (1985), 160–176.10.1016/0097-3165(85)90035-4 Google Scholar | DOI

[FT18] Frankl, P. and Tokushige, N., Extremal Problems for Finite Sets (Student Mathematical Library) vol. 86 (American Mathematical Society, Providence, RI, 2018).10.1090/stml/086 Google Scholar | DOI

[FR87] Frankl, P. and Rödl, V., ‘Forbidden intersections’, Trans. Amer. Math. Soc. 300 (1987), 259–286.10.1090/S0002-9947-1987-0871675-6 Google Scholar | DOI

[FR90] Frankl, P. and Rödl, V., ‘A partition property of simplices in Euclidean space’, J. Amer. Math. Soc. 3 (1990), 1–7.10.1090/S0894-0347-1990-1020148-2 Google Scholar | DOI

[FW81] Frankl, P. and Wilson, R. M., ‘Intersection theorems with geometric consequences’, Combinatorica 1 (1981), 357–368.10.1007/BF02579457 Google Scholar | DOI

[JS68] Jogdeo, K. and Samuels, S. M., ‘Monotone convergence of binomial probabilities and a generalization of Ramanujan’s equation’, Ann. Math. Statist. 39 (1968), 1191–1195.10.1214/aoms/1177698243 Google Scholar | DOI

[KLLM23] Keevash, P., Lifshitz, N., Long, E. and Minzer, D., ‘Forbidden intersections for codes’, J. Lond. Math. Soc. 108 (2023), 2037–2083.10.1112/jlms.12801 Google Scholar | DOI

[KLo16] Keevash, P. and Long, E., ‘Frankl–Rödl-type theorems for codes and permutations’, Trans. Amer. Math. Soc. 369 (2016), 1147–1162.10.1090/tran/7015 Google Scholar | DOI

[KLo20] Keevash, P. and Long, E., ‘Forbidden vector-valued intersections’, Proc. Lond. Math. Soc. 121 (2020), 702–742.10.1112/plms.12338 Google Scholar | DOI

[KLi21] Keller, N. and Lifshitz, N., ‘The junta method for hypergraphs and the Erdős–Chvátal simplex conjecture’, Adv. Math. 392 (2021), Article ID 107991, 95 p.10.1016/j.aim.2021.107991 Google Scholar | DOI

[KSZ22] Kupavskii, A., Sagdeev, A. and Zakharov, D., ‘Cutting corners’, Preprint, 2022, . Google Scholar | arXiv

[KZ24] Kupavskii, A. and Zaharov, D., ‘Spread approximations for forbidden intersections problems’, Adv. Math. 445 (2024), Article ID 109653, 29 p.10.1016/j.aim.2024.109653 Google Scholar | DOI

[Ro55] Robbins, H., ‘A remark on Stirling’s formula’, Amer. Math. Monthly 62 (1955), 26–29. Google Scholar

[S99] Sgall, J., ‘Bounds on pairs of families with restricted intersections’, Combinatorica 19 (1999), 555–566.10.1007/s004939970007 Google Scholar | DOI

[Ta89] Talagrand, M., ‘Isoperimetry and integrability of the sum of independent Banach-space valued random variables’, Ann. Probab. 17 (1989), 1546–1570.10.1214/aop/1176991174 Google Scholar | DOI

Cité par Sources :