×

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.05176

References:

[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.