On \(t\)-intersecting families of permutations.(English)Zbl 1536.05443
In this paper, the authors prove that there exists a constant \(c_0\) such that for any \(t\in \mathbb{N}\) and any \(n \geq c_{0}t\), if \(A \subset S_n\) is a \(t\)-intersecting family of permutations, then \(|A| \leq(n -t)!\). Furthermore, if \(|A| \geq 0.75(n-t)!\), then there exist \(i_1,\ldots, i_t\) and \(j_1,\ldots, j_t\) such that \(\sigma(i_1) =j_1, \ldots, \sigma(i_t) =j_t\) holds for any \(\sigma\in A\). The constant 0.75 was chosen for convenience of the proof and can be replaced with any constant larger than \(1-1/e\). This shows that the conjectures ofP. Frankl andM. Deza [J. Comb. Theory, Ser. A 22, 352–360 (1977;Zbl 0352.05003)] and ofP. J. Cameron [Lond. Math. Soc. Lect. Note Ser. 131, 39–53 (1988;Zbl 0709.05001)] on \(t\)-intersecting families of permutations hold for all \(t \leq c_{0}n\). Their proof method, based on hypercontractivity for global functions, does not use the specific structure of permutations and applies in general to \(t\)-intersecting sub-families of ‘pseudorandom’ families in \(\{1, 2, \ldots, n\}^{n}\), like \(S_{n}\). They showed that the assertion of the theorem holds for cross \(t\)-intersecting families in any ‘pseudorandom’ subfamily of a host space; the method is in the spirit of the Green and Tao philosophy [B. Green andT. Tao, Ann. Math. (2) 167, No. 2, 481–547 (2008;Zbl 1191.11025)] that large subsets of pseudorandom subsets of a space \(X\) behave like large subsets of \(X\). \(S_n\) was considered as a pseudorandom subset of the abelian group \((\mathbb{Z}/n\mathbb{Z})^n\). This allows to employ an analytical tool from the theory of product spaces known as hypercontractivity for global functions developed byP. Keevash et al. [J. Am. Math. Soc. 37, No. 1, 245–279 (2024;Zbl 07752245)].
Reviewer: Ioan Tomescu (Bucureşti)
MSC:
| 05D05 | Extremal set theory |
| 05A05 | Permutations, words, matrices |
| 05E16 | Combinatorial aspects of groups and algebras |
| 20B30 | Symmetric groups |
Keywords:
intersection problems;Erdős-Ko-Rado;permutations;hypercontractivity for global functions;Ahlswede-Khachatrian;forbidden intersection;\(t\)-intersectingCite
References:
| [1] | Ahlberg, D.; Broman, E.; Griffiths, S.; Morris, R., Noise sensitivity in continuum percolation, Isr. J. Math., 201, 2, 847-899, 2014 ·Zbl 1305.60100 |
| [2] | Ahlswede, R.; Khachatrian, L. H., The complete intersection theorem for systems of finite sets, Eur. J. Comb., 18, 2, 125-136, 1997 ·Zbl 0869.05066 |
| [3] | Alweiss, R.; Lovett, S.; Wu, K.; Zhang, J., Improved bounds for the sunflower lemma, Ann. Math. (2), 194, 3, 795-815, 2021 ·Zbl 1479.05343 |
| [4] | Cameron, P. J., Metric and geometric properties of sets of permutations, (Algebraic, Extremal and Metric Combinatorics, 1986. Algebraic, Extremal and Metric Combinatorics, 1986, Montreal, PQ, 1986. Algebraic, Extremal and Metric Combinatorics, 1986. Algebraic, Extremal and Metric Combinatorics, 1986, Montreal, PQ, 1986, London Math. Soc. Lecture Note Ser., vol. 131, 1988, Cambridge Univ. Press: Cambridge Univ. Press Cambridge), 39-53 ·Zbl 0709.05001 |
| [5] | Cameron, P. J.; Ku, C. Y., Intersecting families of permutations, Eur. J. Comb., 24, 7, 881-890, 2003 ·Zbl 1026.05001 |
| [6] | Dinur, I.; Safra, S., On the hardness of approximating minimum vertex cover, Ann. Math. (2), 162, 1, 439-485, 2005 ·Zbl 1084.68051 |
| [7] | Eberhard, S.; Kahn, J.; Narayanan, B.; Spirkl, S., On symmetric intersecting families of vectors, Comb. Probab. Comput., 30, 6, 899-904, 2021 ·Zbl 1510.05281 |
| [8] | Ellis, D., Stability for t-intersecting families of permutations, J. Comb. Theory, Ser. A, 118, 1, 208-227, 2011 ·Zbl 1234.05229 |
| [9] | Ellis, D.; Filmus, Y.; Friedgut, E., Triangle-intersecting families of graphs, J. Eur. Math. Soc., 14, 3, 841-885, 2012 ·Zbl 1238.05143 |
| [10] | Ellis, D.; Friedgut, E.; Pilpel, H., Intersecting families of permutations, J. Am. Math. Soc., 24, 3, 649-682, 2011 ·Zbl 1285.05171 |
| [11] | Ellis, D.; Kalai, G.; Narayanan, B., On symmetric intersecting families, Eur. J. Comb., 86, Article 103094 pp., 2020 ·Zbl 1437.05229 |
| [12] | Ellis, D.; Keller, N.; Lifshitz, N., Stability versions of Erdős-Ko-Rado type theorems via isoperimetry, J. Eur. Math. Soc., 21, 12, 3857-3902, 2019 ·Zbl 1429.05198 |
| [13] | Ellis, D.; Keller, N.; Lifshitz, N., Stability for the complete intersection theorem, and the forbidden intersection problem of Erdős and Sós, J. Eur. Math. Soc., 1-44, 2024 |
| [14] | Ellis, D.; Kindler, G.; Lifshitz, N., Forbidden intersection problems for families of linear maps, Discrete Anal., 19, 1-32, 2023 |
| [15] | 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 |
| [16] | Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Q. J. Math. Oxford Ser. (2), 12, 313-320, 1961 ·Zbl 0100.01902 |
| [17] | Erdős, P.; Rényi, A., On random matrices, Publ. Math. Inst. Hung. Acad. Sci., 8, 455-461, 1964 ·Zbl 0133.26003 |
| [18] | Filmus, Y., The weighted complete intersection theorem, J. Comb. Theory, Ser. A, 151, 84-101, 2017 ·Zbl 1366.05111 |
| [19] | Fortuin, C. M.; Kasteleyn, P. W.; Ginibre, J., Correlation inequalities on some partially ordered sets, Commun. Math. Phys., 22, 89-103, 1971 ·Zbl 0346.06011 |
| [20] | Frankl, P., The Erdős-Ko-Rado theorem is true for \(n = c k t\), (Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, vol. 18, 1978, North-Holland: North-Holland Amsterdam-New York), 365-375 ·Zbl 0401.05001 |
| [21] | Frankl, P., Erdős-Ko-Rado theorem with conditions on the maximal degree, J. Comb. Theory, Ser. A, 46, 2, 252-263, 1987 ·Zbl 0661.05002 |
| [22] | Frankl, P.; Deza, M., On the maximum number of permutations with given maximal or minimal distance, J. Comb. Theory, Ser. A, 22, 3, 352-360, 1977 ·Zbl 0352.05003 |
| [23] | Frankl, P.; Tokushige, N., Invitation to intersection problems for finite sets, J. Comb. Theory, Ser. A, 144, 157-211, 2016 ·Zbl 1343.05153 |
| [24] | Friedgut, E., Sharp thresholds of graph properties, and the k-sat problem, J. Am. Math. Soc., 12, 4, 1017-1054, 1999, With an appendix by Jean Bourgain ·Zbl 0932.05084 |
| [25] | Friedgut, E., On the measure of intersecting families, uniqueness and stability, Combinatorica, 28, 5, 503-528, 2008 ·Zbl 1199.05319 |
| [26] | Frieze, A.; Karoński, M., Introduction to Random Graphs, 2015, Cambridge University Press |
| [27] | Green, B.; Tao, T., The primes contain arbitrarily long arithmetic progressions, Ann. Math. (2), 167, 2, 481-547, 2008 ·Zbl 1191.11025 |
| [28] | Hilton, A. J.W.; Milner, E. C., Some intersection theorems for systems of finite sets, Q. J. Math. Oxford Ser. (2), 18, 369-384, 1967 ·Zbl 0168.26205 |
| [29] | Ihringer, F.; Kupavskii, A., Regular intersecting families, Discrete Appl. Math., 270, 142-152, 2019 ·Zbl 1426.05172 |
| [30] | Keevash, P.; Lifshitz, N.; Long, E.; Minzer, D., Hypercontractivity for global functions and sharp thresholds, J. Am. Math. Soc., 37, 245-279, 2024 ·Zbl 07752245 |
| [31] | Keevash, P.; Long, E., Frankl-Rödl-type theorems for codes and permutations, Trans. Am. Math. Soc., 369, 2, 1147-1162, 2017 ·Zbl 1350.05170 |
| [32] | Keller, N.; Lifshitz, N., The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture, Adv. Math., 392, 107991, 1-95, 2021 ·Zbl 1476.05146 |
| [33] | Keller, N.; Lifshitz, N.; Marcus, O., Sharp hypercontractivity for global functions, available at |
| [34] | N. Keller, N. Lifshitz, O. Sheinfeld, On families of permutations that avoid a single intersection, in preparation. |
| [35] | Kupavskii, A.; Zakharov, D., Spread approximations for forbidden intersections problems, available at ·Zbl 1543.05182 |
| [36] | Larose, B.; Malvenuto, C., Stable sets of maximal size in Kneser-type graphs, Eur. J. Comb., 25, 5, 657-673, 2004 ·Zbl 1048.05078 |
| [37] | Leader, I., Open Problems Session, British Combinatorial Conference, 2005 |
| [38] | Lifshitz, N., Hypergraph removal lemmas via robust sharp threshold theorems, Discrete Anal., 11, 1-46, 2020 ·Zbl 1450.05061 |
| [39] | Meagher, K.; Moura, L., Erdős-Ko-Rado theorems for uniform set-partition systems, Electron. J. Comb., 12, 40, 1-12, 2005 ·Zbl 1075.05086 |
| [40] | Wilson, R. M., The exact bound in the Erdős-Ko-Rado theorem, Combinatorica, 4, 2-3, 247-257, 1984 ·Zbl 0556.05039 |
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.
