Thresholds versus fractional expectation-thresholds.(English)Zbl 1472.05132
Summary: Proving a conjecture ofM. Talagrand [in: Proceedings of the 42nd annual ACM symposium on theory of computing, STOC ’10. Cambridge, MA, USA, June 5–8, 2010. New York, NY: Association for Computing Machinery (ACM). 13–36 (2010;Zbl 1293.60014)], a fractional version of the “expectation-threshold” conjecture ofJ. Kahn andG. Kalai [Comb. Probab. Comput. 16, No. 3, 495–502 (2007;Zbl 1118.05093)], we show that \(p_c(\mathcal{F})=O(q_f(\mathcal{F})\log\ell(\mathcal{F}))\) for any increasing family \(\mathcal{F}\) on a finite set \(X\), where \(p_c(\mathcal{F})\) and \(q_f(\mathcal{F})\) are the threshold and “fractional expectation-threshold” of \(\mathcal{F}\), and \(\ell(\mathcal{F})\) is the maximum size of a minimal member of \(\mathcal{F}\). This easily implies several heretofore difficult results and conjectures in probabilistic combinatorics, including thresholds for perfect hypergraph matchings [A. Johansson et al., Random Struct. Algorithms 33, No. 1, 1–28 (2008;Zbl 1146.05040)], bounded degree spanning trees [R. Montgomery, Adv. Math. 356, Article ID 106793, 92 p. (2019;Zbl 1421.05080)], and bounded degree graphs (new). We also resolve (and vastly extend) the “axial” version of the random multi-dimensional assignment problem (earlier considered by Martin-Mézard-Rivoire andA. Frieze andG. B. Sorkin [Random Struct. Algorithms 46, No. 1, 160–196 (2015;Zbl 1347.60141)]). Our approach builds on a recent breakthrough ofR. Alweiss et al. [in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM). 624–630 (2020;Zbl 1553.05168)] on the Erdő-Rado “Sunflower Conjecture”.
MSC:
| 05C80 | Random graphs (graph-theoretic aspects) |
| 60D05 | Geometric probability and stochastic geometry |
| 60G15 | Gaussian processes |
Citations:
Zbl 1293.60014;Zbl 1118.05093;Zbl 1146.05040;Zbl 1421.05080;Zbl 1347.60141;Zbl 0103.27901;Zbl 1553.05168Cite
References:
| [1] | Alon, Noga; F\"{u}redi, Zolt\'{a}n, Spanning subgraphs of random graphs, Graphs Combin.. Graphs and Combinatorics, 8, 91-94 (1992) ·Zbl 0767.05082 ·doi:10.1007/BF01271712 |
| [2] | Alweiss, R.; Lovett, S.; Wu, K.; Zhang, J., Improved bounds for the sunflower lemma. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, 624-630 (2020) ·Zbl 1553.05168 ·doi:10.1145/3357713.3384234} |
| [3] | Bollob\'{a}s, B., Random {G}raphs, Cambridge Studies in Advanced Mathematics, 73, xviii+498 pp. (2001) ·Zbl 0979.05003 ·doi:10.1017/CBO9780511814068 |
| [4] | Bollob\'{a}s, B.; Thomason, A., Threshold functions, Combinatorica. Combinatorica. An International Journal of the J\'{a}nos Bolyai Mathematical Society, 7, 35-38 (1987) ·Zbl 0648.05048 ·doi:10.1007/BF02579198 |
| [5] | Dudek, Andrzej; Frieze, Alan; Loh, Po-Shen; Speiss, Shelley, Optimal divisibility conditions for loose {H}amilton cycles in random hypergraphs, Electron. J. Combin.. Electronic Journal of Combinatorics, 19, 44-17 (2012) ·Zbl 1266.05152 ·doi:10.37236/2523 |
| [6] | Erd\H{o}s, P.; Rado, R., Intersection theorems for systems of sets, J. London Math. Soc.. The Journal of the London Mathematical Society, 35, 85-90 (1960) ·Zbl 0103.27901 ·doi:10.1112/jlms/s1-35.1.85 |
| [7] | Erd\H{o}s, P.; R\'{e}nyi, A., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutat\'{o} Int. K\"{o}zl.. A Magyar Tudom\'{a}nyos Akad\'{e}mia. Matematikai Kutat\'{o} Int\'{e}zet\'{e}nek K\"{o}zlem\'{e}nyei, 5, 17-61 (1960) ·Zbl 0103.16301 |
| [8] | Ferber, Asaf; Kronenberg, Gal; Luh, Kyle, Optimal threshold for a random graph to be 2-universal, Trans. Amer. Math. Soc.. Transactions of the American Mathematical Society, 372, 4239-4262 (2019) ·Zbl 1420.05161 ·doi:10.1090/tran/7727 |
| [9] | Ferber, Asaf; Luh, Kyle; Nguyen, Oanh, Embedding large graphs into a random graph, Bull. Lond. Math. Soc.. Bulletin of the London Mathematical Society, 49, 784-797 (2017) ·Zbl 1372.05199 ·doi:10.1112/blms.12066 |
| [10] | Friedgut, Ehud, Sharp thresholds of graph properties, and the {\(k\)}-sat problem, J. Amer. Math. Soc.. Journal of the American Mathematical Society, 12, 1017-1054 (1999) ·Zbl 0932.05084 ·doi:10.1090/S0894-0347-99-00305-7 |
| [11] | Friedgut, Ehud, Hunting for sharp thresholds, Random Structures Algorithms. Random Structures & Algorithms, 26, 37-51 (2005) ·Zbl 1059.05092 ·doi:10.1002/rsa.20042 |
| [12] | Frieze, Alan; Sorkin, Gregory B., Efficient algorithms for three-dimensional axial and planar random assignment problems, Random Structures Algorithms. Random Structures & Algorithms, 46, 160-196 (2015) ·Zbl 1347.60141 ·doi:10.1002/rsa.20525 |
| [13] | Heckel, A., Random triangles in random graphs (2018) |
| [14] | Janson, Svante; {\L}uczak, Tomasz; Rucinski, Andrzej, Random Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, xii+333 pp. (2000) ·Zbl 0968.05003 ·doi:10.1002/9781118032718 |
| [15] | Johansson, Anders; Kahn, Jeff; Vu, Van, Factors in random graphs, Random Structures Algorithms. Random Structures & Algorithms, 33, 1-28 (2008) ·Zbl 1146.05040 ·doi:10.1002/rsa.20224 |
| [16] | Kahn, Jeff, Asymptotics for {S}hamir’s problem (2019) |
| [17] | Kahn, Jeff; Kalai, Gil, Thresholds and expectation thresholds, Combin. Probab. Comput.. Combinatorics, Probability and Computing, 16, 495-502 (2007) ·Zbl 1118.05093 ·doi:10.1017/S0963548307008474 |
| [18] | Karp, Richard M., Reducibility among combinatorial problems. Complexity of Computer Computations, 85-103 (1972) ·Zbl 1467.68065 ·doi:10.1007/978-1-4684-2001-2_9 |
| [19] | Keevash, Peter, Counting designs, J. Eur. Math. Soc. (JEMS). Journal of the European Mathematical Society (JEMS), 20, 903-927 (2018) ·Zbl 1386.05015 ·doi:10.4171/JEMS/779 |
| [20] | Krivelevich, Michael, Embedding spanning trees in random graphs, SIAM J. Discrete Math.. SIAM Journal on Discrete Mathematics, 24, 1495-1500 (2010) ·Zbl 1221.05283 ·doi:10.1137/100805753 |
| [21] | Linial, Nathan; Luria, Zur, An upper bound on the number of {S}teiner triple systems, Random Structures Algorithms. Random Structures & Algorithms, 43, 399-406 (2013) ·Zbl 1278.05030 ·doi:10.1002/rsa.20487 |
| [22] | van Lint, J. H.; Wilson, R. M., A Course in Combinatorics, xiv+602 pp. (2001) ·Zbl 0980.05001 ·doi:10.1017/CBO9780511987045 |
| [23] | Lord, N., Binomial averages when the mean is an integer, Math. Gaz., 94, 331-332 (2010) ·doi:10.1017/S0025557200006690 |
| [24] | Montgomery, Richard, Spanning trees in random graphs, Adv. Math.. Advances in Mathematics, 356, 106793-92 (2019) ·Zbl 1421.05080 ·doi:10.1016/j.aim.2019.106793 |
| [25] | Rao, Anup, Coding for sunflowers, Discrete Anal.. Discrete Analysis, 2-8 (2020) ·Zbl 1450.05092 ·doi:10.19086/da |
| [26] | Riordan, O., Random cliques in random graphs (2018) |
| [27] | Talagrand, M., Are all sets of positive measure essentially convex?. Geometric Aspects of Functional Analysis, Oper. Theory Adv. Appl., 77, 295-310 (1995) ·Zbl 0835.60003 ·doi:10.1007/978-3-0348-9090-8_25 |
| [28] | Talagrand, Michel, The Generic Chaining, Springer Monographs in Mathematics, viii+222 pp. (2005) ·Zbl 1075.60001 ·doi:10.1007/3-540-27499-5 |
| [29] | Talagrand, Michel, Selector processes on classes of sets, Probab. Theory Related Fields. Probability Theory and Related Fields, 135, 471-486 (2006) ·Zbl 1097.60019 ·doi:10.1007/s00440-004-0350-2 |
| [30] | Talagrand, Michel, Are many small sets explicitly small?. S{TOC}’10—{P}roceedings of the 2010 {ACM} {I}nternational {S}ymposium on {T}heory of {C}omputing, 13-35 (2010) ·Zbl 1293.60014 ·doi:10.1145/1806689.1806693 |
| [31] | Talagrand, Michel, Upper and Lower Bounds for Stochastic Processes, Ergeb. Math. Grenzgeb., 60, xvi+626 pp. (2014) ·Zbl 1293.60001 ·doi:10.1007/978-3-642-54075-2 |
| [32] | blog post; available on author’s webpage, The sunflower lemma via {S}hannon entropy |
| [33] | Wilson, Richard M., Nonisomorphic {S}teiner triple systems, Math. Z.. Mathematische Zeitschrift, 135, 303-313 (1973/74) ·Zbl 0264.05009 ·doi:10.1007/BF01215371 |
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.
