Ramsey Properties of Randomly Perturbed Hypergraphs

Elad Aigner-Horev, Dan Hefetz, Mathias Schacht

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

We study Ramsey properties of randomly perturbed 3-uniform hypergraphs. For t ≥ 2, write Ket(3) to denote the 3-uniform expanded clique hypergraph obtained from the complete graph Kt 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 (Ket(3), Ket/(3)2). We prove that adding a set F of random hyperedges satisfying |F| ≫ n3−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 Ket(3) 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.

שפה מקוריתאנגלית
כותר פרסום המארחApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024
עורכיםAmit Kumar, Noga Ron-Zewi
מוציא לאורSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
מסת"ב (אלקטרוני)9783959773485
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ספט׳ 2024
אירוע27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024 - London, בריטניה
משך הזמן: 28 אוג׳ 202430 אוג׳ 2024

סדרות פרסומים

שםLeibniz International Proceedings in Informatics, LIPIcs
כרך317
ISSN (מודפס)1868-8969

כנס

כנס27th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2024 and the 28th International Conference on Randomization and Computation, RANDOM 2024
מדינה/אזורבריטניה
עירLondon
תקופה28/08/2430/08/24

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Ramsey Properties of Randomly Perturbed Hypergraphs'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי