Graphs without rainbow cliques of orders four and five

Abstract: Let

m a t h c a l G_{n}^{k} = G_{1}, G_{2}, l d o t s, G_{k}

be a multiset of graphs on vertex set

[n]

and let

F

be a fixed graph with edge set

F = e_{1}, e_{2}, l d o t s, e_{m}

and

k g e m

. We say

m a t h c a l G_{n}^{k}

is rainbow

F

-free if there is no

i_{1}, i_{2}, l d o t s, i_{m} s u b s e t e q [k]

satisfying

e_{j} i n G_{i_{j}}

for every

j i n [m]

. Let

e x_{k} (n, F)

be the maximum

s u m_{i = 1}^{k} | G_{i} |

among all the rainbow

F

-free multisets

m a t h c a l G_{n}^{k}

. Keevash, Saks, Sudakov, and Verstra"ete (2004) determined the exact value of

e x_{k} (n, K_{r})

when

n

is sufficiently large and proposed the conjecture that the results remain true when

n g e C r^{2}

for some constant

C

. Recently, Frankl (2022) confirmed the conjecture for

r = 3

and all possible values of

n

. In this paper, we determine the exact value of

e x_{k} (n, K_{r})

for

n g e r - 1

when

r = 4

and

5

, i.e. the conjecture of Keevash, Saks, Sudakov, and Verstra"ete is true for

r i n 4, 5

.

This page was built for publication: Graphs without rainbow cliques of orders four and five