2026-07-22T19:10:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21052 2024-09-16T06:02:39Z ddc:004 open_access

Ramsey Properties of Randomly Perturbed Hypergraphs Aigner-Horev, Elad Hefetz, Dan Schacht, Mathias Ramsey Theory Smoothed Analysis Random Hypergraphs We study Ramsey properties of randomly perturbed 3-uniform hypergraphs. For t ≥ 2, write K^(3)_t to denote the 3-uniform expanded clique hypergraph obtained from the complete graph K_t by expanding each of the edges of the latter with a new additional vertex. For an even integer t ≥ 4, let M denote the asymmetric maximal density of the pair (K^(3)_t, K^(3)_{t/2}). We prove that adding a set F of random hyperedges satisfying |F| ≫ n^{3-1/M} to a given n-vertex 3-uniform hypergraph H with non-vanishing edge density asymptotically almost surely results in a perturbed hypergraph enjoying the Ramsey property for K^(3)_t and two colours. We conjecture that this result is asymptotically best possible with respect to the size of F whenever t ≥ 6 is even. The key tools of our proof are a new variant of the hypergraph regularity lemma accompanied with a tuple lemma providing appropriate control over joint link graphs. Our variant combines the so called strong and the weak hypergraph regularity lemmata. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elad Aigner-Horev and Dan Hefetz and Mathias Schacht 2024 Is Part Of LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2024.59 urn:nbn:de:0030-drops-210528 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.59 eng https://creativecommons.org/licenses/by/4.0/legalcode