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; (2020) Large rainbow cliques in randomly perturbed dense graphs. (In press).

[img] Text
1912.13512v5.pdf - Accepted version
Access restricted to UCL open access staff until 21 May 2021.

Download (323kB)

Abstract

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. Our results in this paper, combined with our results in a companion paper, determine the threshold for the property G ∪ G(n, p) rbw −→ Ks 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. In this paper, we also consider the property G∪G(n, p) rbw −→ C2ℓ−1, and show that the threshold for this property is n −2 for every ℓ ≥ 2; in particular, it 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.

Type: Article
Title: Large rainbow cliques in randomly perturbed dense graphs
Language: English
Additional information: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
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
1Download
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item