Aigner-Horev, E;
Danon, O;
Hefetz, D;
Letzter, S;
(2022)
Small rainbow cliques in randomly perturbed dense graphs.
European Journal of Combinatorics
, 101
, Article 103452. 10.1016/j.ejc.2021.103452.
Preview |
Text
2006.00588v2.pdf - Accepted Version Download (679kB) | 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 > 0, and d is independent of n. In a companion paper, we proved that the threshold for the property G ∪ G(n, p) rbw −→ K` is n −1/m2(Kd`/2e) , whenever ` ≥ 9. For smaller `, the thresholds behave more erratically, and for 4 ≤ ` ≤ 7 they deviate downwards significantly from the aforementioned aesthetic form capturing the thresholds for large cliques. In particular, we show that the thresholds for ` ∈ {4, 5, 7} are n −5/4 , n −1 , and n −7/15, respectively. For ` ∈ {6, 8} we determine the threshold up to a (1 + o(1))-factor in the exponent: they are n −(2/3+o(1)) and n −(2/5+o(1)), respectively. For ` = 3, the threshold is n −2 ; this follows from a more general result about odd cycles in our companion paper.
Type: | Article |
---|---|
Title: | Small rainbow cliques in randomly perturbed dense graphs |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1016/j.ejc.2021.103452 |
Publisher version: | https://doi.org/10.1016/j.ejc.2021.103452 |
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 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/10107286 |
Archive Staff Only
View Item |