On the maximum \(F_5\)-free subhypergraphs of a random hypergraph. (English) Zbl 1532.05121
Summary: Denote by \(F_5\) the \(3\)-uniform hypergraph on vertex set \(\{1, 2, 3, 4, 5\}\) with hyperedges \(\{123,124, 345\}\). J. Balogh et al. [Random Struct. Algorithms 48, No. 4, 641–654 (2016; Zbl 1341.05176)] proved that if \(p > K \log n /n\) for some large constant \(K\), then every maximum \(F_5\)-free subhypergraph of \(G^3(n,p)\) is tripartite with high probability, and showed that if \(p_0 = 0.1\sqrt{\log n} /n\), then with high probability there exists a maximum \(F_5\)-free subhypergraph of \(G^3(n, p_0)\) that is not tripartite. In this paper, we sharpen the upper bound to be best possible up to a constant factor. We prove that if \(p > C \sqrt{\log n} /n\) for some large constant \(C\), then every maximum \(F_5\)-free subhypergraph of \(G^3(n, p)\) is tripartite with high probability.
MSC:
05C65 | Hypergraphs |
05C80 | Random graphs (graph-theoretic aspects) |
05C30 | Enumeration in graph theory |
05C35 | Extremal problems in graph theory |
Citations:
Zbl 1341.05176References:
[1] | László Babai, Miklós Simonovits, and Joel Spencer. Extremal subgraphs of random graphs. Journal of Graph Theory 14 (1990), no. 5, 599-622. · Zbl 0738.05048 |
[2] | József Balogh, Jane Butterfield, Ping Hu, and John Lenz. Mantel’s theorem for random hypergraphs. Random Structures & Algorithms 48 (2016), no. 4, 641-654. · Zbl 1341.05176 |
[3] | József Balogh, Robert Morris, and Wojciech Samotij. Independent sets in hypergraphs. Journal of the American Mathematical Society 28 (2015), no. 3, 669-709. · Zbl 1310.05154 |
[4] | Béla Bollobás. Three-graphs without two triples whose symmetric difference is contained in a third. Discrete Mathematics 8 (1974), no. 1, 21-24. · Zbl 0291.05114 |
[5] | David Conlon, and Timothy Gowers. Combinatorial theorems in sparse random sets. Annals of Mathematics (2016), 367-454. · Zbl 1351.05204 |
[6] | Bobby DeMarco, and Jeff Kahn. Mantel’s theorem for random graphs. Random Structures & Algo-rithmss 47 (2015), no. 1, 59-72. · Zbl 1328.05169 |
[7] | Bobby DeMarco, and Jeff Kahn. Turán’s theorem for random graphs, arXiv:1501.01340 (2015). · Zbl 1307.05201 |
[8] | Peter Frankl, and Zoltán Füredi. A new generalization of the Erdős-Ko-Rado theorem. Combina-torica 3 (1983), no. 3, 341-349. · Zbl 0529.05001 |
[9] | Willem Mantel, Problem 28, Wiskundige Opgaven (1907), 60-61. · JFM 38.0270.01 |
[10] | Wojciech Samotij. Stability results for random discrete structures. Random Structures & Algorithms 44 (2014), no. 3, 269-289. · Zbl 1290.05131 |
[11] | David Saxton, and Andrew Thomason. Hypergraph containers. Inventiones mathematicae 201 (2015), no. 3, 925-992. · Zbl 1320.05085 |
[12] | Mathias Schacht. Extremal results for random discrete structures. Annals of Mathematics (2016), 333-365. · Zbl 1351.05207 |
[13] | Paul Turán. Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), no. 61, 436-452. · JFM 67.0732.03 |
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.