Rainbow Cliques in Randomly Perturbed Dense Graphs

Elad Aigner-Horev, Oran Danon, Dan Hefetz, Shoham Letzter

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

תקציר

For two graphs G and H, write G⟶ rbw H if G has the property that every proper colouring of its edges yields a rainbow copy of H. We study the thresholds for such so-called anti-Ramsey properties in randomly perturbed dense graphs, which are unions of the form G∪ G(n, p), where G is an n-vertex graph with edge-density at least d, and d is a constant that does not depend on n. We determine the threshold for the property G∪ G(n, p) ⟶ rbw Ks for every s. We show that for s≥ 9 the threshold is n-1/m2(K⌈s/2⌉) ; in fact, our 1-statement is a supersaturation result. This turns out to (almost) be the threshold for s= 8 as well, but for every 4 ≤ s≤ 7, the threshold is lower and is different for each 4 ≤ s≤ 7. Moreover, we prove that for every ℓ≥ 2 the threshold for the property G∪ G(n, p) ⟶ rbw C2 - 1 is n- 2 ; in particular, the threshold does not depend on the length of the cycle C2 - 1. It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.

שפה מקוריתאנגלית
כותר פרסום המארחTrends in Mathematics
מוציא לאורSpringer Science and Business Media Deutschland GmbH
עמודים154-159
מספר עמודים6
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2021

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

שםTrends in Mathematics
כרך14
ISSN (מודפס)2297-0215
ISSN (אלקטרוני)2297-024X

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Rainbow Cliques in Randomly Perturbed Dense Graphs'. יחד הם יוצרים טביעת אצבע ייחודית.

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