2023/06/21 by Ma, Yue, Hou, Xinmin · 1 citation
#05C35 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2306.12222
Let Gnk=\G1,G2,…,Gk\ be a multiset of graphs on vertex set [n] and let F be a fixed graph with edge set F=\e1, e2,…, em\ and k≥ m. We say Gnk is rainbow F-free if there is no \i1, i2,…, im\⊆[k] satisfying ej∈ Gij for every j∈[m]. Let \exk(n,F) be the maximum ∑i=1k|Gi| among all the rainbow F-free multisets Gnk. Keevash, Saks, Sudakov, and Verstraëte (2004) determined the exact value of \exk(n, Kr) when n is sufficiently large and proposed the conjecture that the results remain true when n≥ Cr2 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 \exk(n, Kr) for n≥ r-1 when r=4 and 5, i.e. the conjecture of Keevash, Saks, Sudakov, and Verstraëte is true for r∈\4,5\.