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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2021

سلسلة المنشورات

الاسمTrends in Mathematics
مستوى الصوت14
رقم المعيار الدولي للدوريات (المطبوع)2297-0215
رقم المعيار الدولي للدوريات (الإلكتروني)2297-024X

بصمة

أدرس بدقة موضوعات البحث “Rainbow Cliques in Randomly Perturbed Dense Graphs'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا