Aigner-Horev, E;
Danon, O;
Hefetz, D;
Letzter, S;
(2021)
Rainbow Cliques in Randomly Perturbed Dense Graphs.
In:
Extended Abstracts EuroComb 2021.
(pp. 154-159).
Springer International Publishing: Cham, Switzerland.
Preview |
Text
ECA_Rainbow.pdf - Accepted Version Download (303kB) | Preview |
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. 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.
Type: | Book chapter |
---|---|
Title: | Rainbow Cliques in Randomly Perturbed Dense Graphs |
ISBN-13: | 9783030838225 |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1007/978-3-030-83823-2_25 |
Publisher version: | https://doi.org/10.1007/978-3-030-83823-2_2 |
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 > 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 UCL > Provost and Vice Provost Offices > UCL BEAMS UCL |
URI: | https://discovery.ucl.ac.uk/id/eprint/10143609 |
Archive Staff Only
View Item |