UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

Large Rainbow Cliques in Randomly Perturbed Dense Graphs

Aigner-Horev, E; Danon, O; Hefetz, D; Letzter, S; (2022) Large Rainbow Cliques in Randomly Perturbed Dense Graphs. SIAM Journal on Discrete Mathematics , 36 (4) pp. 2975-2994. 10.1137/21M1423117. Green open access

[thumbnail of Letzter_21m1423117.pdf]
Preview
Text
Letzter_21m1423117.pdf

Download (472kB) | Preview

Abstract

For two graphs G and H, write G⟶rbwH if G has the property that every proper coloring 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. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property G∪G(n,p)⟶rbwKs for every s. In this paper, 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; see our companion paper for more details. Also in this paper, we determine that the threshold for the property G∪G(n,p)⟶rbwC2ℓ−1 is n−2 for every ℓ≥2; in particular, the threshold does not depend on the length of the cycle C2ℓ−1. For even cycles, and in fact any fixed bipartite graph, no random edges are needed at all; that is, G⟶rbwH always holds, whenever G is as above and H is bipartite.

Type: Article
Title: Large Rainbow Cliques in Randomly Perturbed Dense Graphs
Open access status: An open access version is available from UCL Discovery
DOI: 10.1137/21M1423117
Publisher version: https://doi.org/10.1137/21M1423117
Language: English
Additional information: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
Keywords: random graphs, anti-Ramsey, perturbed graphs, thresholds
UCL classification: UCL
UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics
URI: https://discovery.ucl.ac.uk/id/eprint/10107284
Downloads since deposit
40Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item