On the Maximum F5-free Subhypergraphs of a Random Hypergraph

Igor Araujo; József Balogh; Haoran Luo

doi:10.37236/11328

On the Maximum F₅-free Subhypergraphs of a Random Hypergraph

Igor Araujo, József Balogh, Haoran Luo

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Denote by F₅ the 3-uniform hypergraph on vertex set {1, 2, 3, 4, 5} with hyperedges {123, 124, 345}. Balogh, Butterfield, Hu, and Lenz proved that if p > K log n/n for some large constant K, then every maximum F₅-free subhypergraph of G³(n, p) is tripartite with high probability, and showed that if (Formula present) then with high probability there exists a maximum F₅-free subhy-pergraph of G³(n, p₀) 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 (Formula present) for some large constant C, then every maximum F₅-free subhypergraph of G³(n, p) is tripartite with high probability.

Original language	English (US)
Article number	P4.22
Journal	Electronic Journal of Combinatorics
Volume	30
Issue number	4
DOIs	https://doi.org/10.37236/11328
State	Published - 2023

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Online availability

10.37236/11328

Library availability

Discover UIUC Full Text

Cite this

@article{582f9687bc7244adbaf153687b911a2a,

title = "On the Maximum F5-free Subhypergraphs of a Random Hypergraph",

abstract = "Denote by F5 the 3-uniform hypergraph on vertex set {1, 2, 3, 4, 5} with hyperedges {123, 124, 345}. Balogh, Butterfield, Hu, and Lenz proved that if p > K log n/n for some large constant K, then every maximum F5-free subhypergraph of G3(n, p) is tripartite with high probability, and showed that if (Formula present) then with high probability there exists a maximum F5-free subhy-pergraph of G3(n, p0) 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 (Formula present) for some large constant C, then every maximum F5-free subhypergraph of G3(n, p) is tripartite with high probability.",

author = "Igor Araujo and J{\'o}zsef Balogh and Haoran Luo",

note = "We thank the referees for their useful comments and careful reading of the manuscript. The research of Igor Araujo, J\u00F3zsef Balogh, and Haoran Luo is partially supported by UIUC Campus Research Board RB 22000. The research of J\u00F3zsef Balogh is also partially supported by NSF Grant DMS-1764123 and RTG DMS-1937241, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC), and the Simons Fellowship. The research of Igor Araujo, J\u00F3zsef Balogh, and Haoran Luo is partially supported by UIUC Campus Research Board RB 22000. The research of J\u00F3zsef Balogh is also partially supported by NSF Grant DMS-1764123 and RTG DMS-1937241, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC), and the Simons Fellowship.",

year = "2023",

doi = "10.37236/11328",

language = "English (US)",

volume = "30",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "4",

}

TY - JOUR

T1 - On the Maximum F5-free Subhypergraphs of a Random Hypergraph

AU - Araujo, Igor

AU - Balogh, József

AU - Luo, Haoran

N1 - We thank the referees for their useful comments and careful reading of the manuscript. The research of Igor Araujo, J\u00F3zsef Balogh, and Haoran Luo is partially supported by UIUC Campus Research Board RB 22000. The research of J\u00F3zsef Balogh is also partially supported by NSF Grant DMS-1764123 and RTG DMS-1937241, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC), and the Simons Fellowship. The research of Igor Araujo, J\u00F3zsef Balogh, and Haoran Luo is partially supported by UIUC Campus Research Board RB 22000. The research of J\u00F3zsef Balogh is also partially supported by NSF Grant DMS-1764123 and RTG DMS-1937241, Arnold O. Beckman Research Award (UIUC Campus Research Board RB 22000), the Langan Scholar Fund (UIUC), and the Simons Fellowship.

PY - 2023

Y1 - 2023

N2 - Denote by F5 the 3-uniform hypergraph on vertex set {1, 2, 3, 4, 5} with hyperedges {123, 124, 345}. Balogh, Butterfield, Hu, and Lenz proved that if p > K log n/n for some large constant K, then every maximum F5-free subhypergraph of G3(n, p) is tripartite with high probability, and showed that if (Formula present) then with high probability there exists a maximum F5-free subhy-pergraph of G3(n, p0) 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 (Formula present) for some large constant C, then every maximum F5-free subhypergraph of G3(n, p) is tripartite with high probability.

AB - Denote by F5 the 3-uniform hypergraph on vertex set {1, 2, 3, 4, 5} with hyperedges {123, 124, 345}. Balogh, Butterfield, Hu, and Lenz proved that if p > K log n/n for some large constant K, then every maximum F5-free subhypergraph of G3(n, p) is tripartite with high probability, and showed that if (Formula present) then with high probability there exists a maximum F5-free subhy-pergraph of G3(n, p0) 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 (Formula present) for some large constant C, then every maximum F5-free subhypergraph of G3(n, p) is tripartite with high probability.

UR - http://www.scopus.com/inward/record.url?scp=85176612016&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85176612016&partnerID=8YFLogxK

U2 - 10.37236/11328

DO - 10.37236/11328

M3 - Article

AN - SCOPUS:85176612016

SN - 1077-8926

VL - 30

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 4

M1 - P4.22

ER -