Large Rainbow Cliques in Randomly Perturbed Dense Graphs

Abstract: For two graphs

G

and

H

, write

G s t a c k r e l m a t h r m r b w l o n g r i g h t a r r o w H

if

G

has the property that every {sl proper} colouring of its edges yields a {sl rainbow} copy of

H

. We study the thresholds for such so-called {sl anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form

G c u p m a t h b b 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 c u p m a t h b b G (n, p) s t a c k r e l m a t h r m r b w l o n g r i g h t a r r o w K_{s}

for every

s

. In this paper, we show that for

s g e q 9

the threshold is

n^{- 1 / m_{2} (K_{l e f t l c e i l s / 2 i g h t c e i l})}

; 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 l e q s l e q 7

, the threshold is lower; see our companion paper for more details. In this paper, we also consider the property

G c u p m a t h b b G (n, p) s t a c k r e l m a t h r m r b w l o n g r i g h t a r r o w C_{2 e l l - 1}

, and show that the threshold for this property is

n^{- 2}

for every

e l l g e q 2

; in particular, it does not depend on the length of the cycle

C_{2 e l l - 1}

. It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.

Recommendations

Cites Work

Cited In (1)

This page was built for publication: Large Rainbow Cliques in Randomly Perturbed Dense Graphs