Spread approximations for forbidden intersections problems.(English)Zbl 1543.05182
This article develops a versatile new method of ‘spread approximations’ for extremal and structural results on hypergraphs. This approach was inspired by recent breakthroughs on the Erdős-Rado sunflower conjecture byA. Rao [Discrete Anal. 2020, Paper No. 2, 8 p. (2020;Zbl 1450.05092)] andR. Alweiss et al. [Ann. Math. (2) 194, No. 3, 795–815 (2021;Zbl 1479.05343)]. Two applications investigated here are to regular \(t\)-intersecting families, including the permutation setting, and new ranges for the Erdős-Sós problem, which asks to avoid intersection \(t-1\).
The main results are Theorems 1 and 2. The first of these is an impressive partial resolution of the Erdős-Sós problem for uniform set systems: Suppose \(\alpha>1\) and \(0<\beta<\frac{1}{2}\) satisfy \(\alpha>2\beta+1\). Then for all sufficiently large \(k\), letting \(n=\lceil k^\alpha \rceil\) and \(t=\lceil k^\beta \rceil\), a \(k\)-uniform family \(\mathcal{F} \subset 2^{[n]}\) which avoids intersection \(t-1\) satisfies the expected bound \(|\mathcal{F}| \le \binom{n-t}{k-t}\). The allowed rate of growth of \(t\) is noteworthy here.
Theorem 2 concerns families \(\mathcal{P}\) of permutations in the symmetric group on \(n\) symbols. It states: (i) if \(\mathcal{P}\) is \(t\)-intersecting and \(n>C_1 t \log^2 n\), then \(|\mathcal{P}| \le (n-t)!\); and (ii) if \(\mathcal{P}\) avoids intersection \(t-1\) and \(n>C_2 \max(t^2 \log^2 n,t^3 \log n)\) then again \(|\mathcal{P}| \le (n-t)!\). Explicit constants and structural results are given, but we omit the details in this review. Theorem 2 is nice in that it improves the previous work ofD. Ellis et al. [J. Am. Math. Soc. 24, No. 3, 649–682 (2011;Zbl 1285.05171)] on the \(t\)-intersecting and Erdős-Sós questions for permutations while bypassing representation theory and eigenvalue methods.
To understand the general method, a good starting point is [“The sunflower lemma via Shannon entropy”,https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/], a blog post byT. Tao, which explains (and slightly refines) the earlier work on sunflowers. Then, a good warm-up to this paper’s methodology is found in Section 3, specifically Theorem 8. More technical results necessary for the Erdős-Sós statements are given later, in Section 4. This is a nicely written paper that will likely prove useful for new settings in extremal combinatorics.
The main results are Theorems 1 and 2. The first of these is an impressive partial resolution of the Erdős-Sós problem for uniform set systems: Suppose \(\alpha>1\) and \(0<\beta<\frac{1}{2}\) satisfy \(\alpha>2\beta+1\). Then for all sufficiently large \(k\), letting \(n=\lceil k^\alpha \rceil\) and \(t=\lceil k^\beta \rceil\), a \(k\)-uniform family \(\mathcal{F} \subset 2^{[n]}\) which avoids intersection \(t-1\) satisfies the expected bound \(|\mathcal{F}| \le \binom{n-t}{k-t}\). The allowed rate of growth of \(t\) is noteworthy here.
Theorem 2 concerns families \(\mathcal{P}\) of permutations in the symmetric group on \(n\) symbols. It states: (i) if \(\mathcal{P}\) is \(t\)-intersecting and \(n>C_1 t \log^2 n\), then \(|\mathcal{P}| \le (n-t)!\); and (ii) if \(\mathcal{P}\) avoids intersection \(t-1\) and \(n>C_2 \max(t^2 \log^2 n,t^3 \log n)\) then again \(|\mathcal{P}| \le (n-t)!\). Explicit constants and structural results are given, but we omit the details in this review. Theorem 2 is nice in that it improves the previous work ofD. Ellis et al. [J. Am. Math. Soc. 24, No. 3, 649–682 (2011;Zbl 1285.05171)] on the \(t\)-intersecting and Erdős-Sós questions for permutations while bypassing representation theory and eigenvalue methods.
To understand the general method, a good starting point is [“The sunflower lemma via Shannon entropy”,https://terrytao.wordpress.com/2020/07/20/the-sunflower-lemma-via-shannon-entropy/], a blog post byT. Tao, which explains (and slightly refines) the earlier work on sunflowers. Then, a good warm-up to this paper’s methodology is found in Section 3, specifically Theorem 8. More technical results necessary for the Erdős-Sós statements are given later, in Section 4. This is a nicely written paper that will likely prove useful for new settings in extremal combinatorics.
Reviewer: Peter Dukes (Victoria)
Cite
References:
| [1] | Ahlswede, R.; Khachatrian, L. H., The complete intersection theorem for systems of finite sets, Eur. J. Comb., 18, 125-136, 1997 ·Zbl 0869.05066 |
| [2] | Alweiss, R.; Lovett, S.; Wu, K.; Zhang, J., Improved bounds for the sunflower lemma, 2019 |
| [3] | Bell, T.; Chueluecha, S.; Warnke, L., Note on sunflowers, Discrete Math., 344, N7, Article 112367 pp., 2021 ·Zbl 1466.05204 |
| [4] | Bollobás, B.; Thomason, A. G., Threshold functions, Combinatorica, 7, 35-38, 1987 ·Zbl 0648.05048 |
| [5] | Cameron, P.; Ku, C. Y., Intersecting families of permutations, Eur. J. Comb., 24, 881-890, 2003 ·Zbl 1026.05001 |
| [6] | Deza, M.; Frankl, P., On the maximum number of permutations with given maximal or minimal distance, J. Comb. Theory, Ser. A, 22, 352-360, 1977 ·Zbl 0352.05003 |
| [7] | Dinur, I.; Safra, S., On the hardness of approximating minimum vertex cover, Ann. Math., 162, 439-485, 2005 ·Zbl 1084.68051 |
| [8] | Ellis, D.; Friedgut, E.; Pilpel, H., Intersecting families of permutations, J. Am. Math. Soc., 24, 649-682, 2011 ·Zbl 1285.05171 |
| [9] | Ellis, D.; Kalai, G.; Narayanan, B., On symmetric intersecting families, Eur. J. Comb., 86, Article 103094 pp., 2020 ·Zbl 1437.05229 |
| [10] | Ellis, D.; Keller, N.; Lifshitz, N., Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós, 2016 |
| [11] | Ellis, D.; Lifshitz, N., Approximation by juntas in the symmetric group, and forbidden intersection problems, Duke Math. J., 171, 7, 1417-1467, 2022 ·Zbl 1490.05262 |
| [12] | Erdős, P., Problems and Results in Graph Theory and Combinatorial Analysis, Proc. 5th British Combinatorial Conference, 169-192, 1975 ·Zbl 0335.05002 |
| [13] | Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Q. J. Math., 12, N1, 313-320, 1961 ·Zbl 0100.01902 |
| [14] | Erdős, P.; Rado, R., Intersection theorems for systems of sets, J. Lond. Math. Soc., 35, N1, 85-90, 1960 ·Zbl 0103.27901 |
| [15] | Fischer, E.; Kindler, G.; Ron, D.; Safra, S.; Samorodnitsky, A., Testing juntas, J. Comput. Syst. Sci., 68, 753-787, 2004 ·Zbl 1076.68112 |
| [16] | Frankl, P., The Erdős-Ko-Rado theorem is true for n=ckt, (Combinatorics, Proc. Fifth Hungarian Colloq., vol. I. Combinatorics, Proc. Fifth Hungarian Colloq., vol. I, Keszthely, 1976. Combinatorics, Proc. Fifth Hungarian Colloq., vol. I. Combinatorics, Proc. Fifth Hungarian Colloq., vol. I, Keszthely, 1976, Colloq. Math. Soc. János Bolyai, vol. 18, 1978, North-Holland), 365-375 ·Zbl 0401.05001 |
| [17] | Frankl, P., On intersecting families of finite sets, Bull. Aust. Math. Soc., 21, 363-372, 1980 ·Zbl 0425.05002 |
| [18] | Frankl, P., Erdos-Ko-Rado theorem with conditions on the maximal degree, J. Comb. Theory, Ser. A, 46, N2, 252-263, 1987 ·Zbl 0661.05002 |
| [19] | Frankl, P.; Füredi, Z., Forbidding just one intersection, J. Comb. Theory, Ser. A, 39, 160-176, 1985 ·Zbl 0573.05001 |
| [20] | Frankl, P.; Füredi, Z., Exact solution of some Turán-type problems, J. Comb. Theory, Ser. A, 45, 226-262, 1987 ·Zbl 0661.05003 |
| [21] | Frankl, P.; Füredi, Z., Beyond the Erdos-Ko-Rado theorem, J. Comb. Theory, Ser. A, 56, N2, 182-194, 1991 ·Zbl 0742.05080 |
| [22] | Frankl, P.; Rödl, V., Forbidden intersections, Trans. Am. Math. Soc., 300, 259-286, 1987 ·Zbl 0611.05002 |
| [23] | Frankl, P.; Rödl, V., A partition property of simplices in Euclidean space, J. Am. Math. Soc., 3, N1, 1-7, 1990 ·Zbl 0696.05014 |
| [24] | Frankl, P.; Wilson, R., Intersection theorems with geometric consequences, Combinatorica, 1, 357-368, 1981 ·Zbl 0498.05048 |
| [25] | Frankston, K.; Kahn, J.; Narayanan, B.; Park, J., Thresholds versus fractional expectation-thresholds, Ann. Math., 194, 475-495, 2021 ·Zbl 1472.05132 |
| [26] | Ihringer, F.; Kupavskii, A., Regular intersecting families, Discrete Appl. Math., 270, 142-152, 2019 ·Zbl 1426.05172 |
| [27] | Keller, N.; Lifshitz, N., The junta method for hypergraphs and Chvátal’s simplex conjecture, 2017 |
| [28] | Keevash, P.; Lifshitz, N.; Long, E.; Minzer, D., Hypercontractivity for global functions and sharp thresholds, 2019 |
| [29] | Keevash, P.; Lifshitz, N.; Long, E.; Minzer, D., Global hypercontractivity and its applications, 2021 |
| [30] | Keevash, P.; Long, E., Frankl-Rödl-type theorems for codes and permutations, Trans. Am. Math. Soc., 369, 1147-1162, 2016 ·Zbl 1350.05170 |
| [31] | Larose, B.; Malvenuto, C., Stable sets of maximal size in Kneser-type graphs, Eur. J. Comb., 25, N5, 657-673, 2004 ·Zbl 1048.05078 |
| [32] | Raigorodskii, A. M., Borsuk’s problem and the chromatic numbers of some metric spaces, Russ. Math. Surv., 56, N1, 103-139, 2001 ·Zbl 1008.54018 |
| [33] | Razborov, A.; Vereshchagin, N., One property of cross-intersecting families, (Proc. of Erdős Memorial Conference. Proc. of Erdős Memorial Conference, Hungary, 1999), TR99-014 |
| [34] | Talagrand, M., Are many small sets explicitly small?, (Proceedings of the 2010 ACM International Symposium on Theory of Computing, 2010), 13-35 ·Zbl 1293.60014 |
| [35] | Tao, T., The sunflower lemma via Shannon entropy |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
