DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2024.59

Ramsey Properties of Randomly Perturbed Hypergraphs

Authors: Elad Aigner-Horev, Dan Hefetz, and Mathias Schacht

Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)

Abstract

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.

Cite as

Elad Aigner-Horev, Dan Hefetz, and Mathias Schacht. Ramsey Properties of Randomly Perturbed Hypergraphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 59:1-59:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{aignerhorev_et_al:LIPIcs.APPROX/RANDOM.2024.59,
  author =	{Aigner-Horev, Elad and Hefetz, Dan and Schacht, Mathias},
  title =	{{Ramsey Properties of Randomly Perturbed Hypergraphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)},
  pages =	{59:1--59:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-348-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{317},
  editor =	{Kumar, Amit and Ron-Zewi, Noga},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.59},
  URN =		{urn:nbn:de:0030-drops-210528},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2024.59},
  annote =	{Keywords: Ramsey Theory, Smoothed Analysis, Random Hypergraphs}
}

Search Results

Documents authored by Schacht, Mathias

Ramsey Properties of Randomly Perturbed Hypergraphs

Abstract

Cite as

Thanks for your feedback!

Could not send message