2017/10/22 by Girão, António, Lewis, David, Popielarz, Kamil
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1710.08025
In this paper we study the following problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger. Given a graph H and an integer t, what is satt(n, \mathfrakR(H)), the minimum number of edges in a t-edge-coloured graph G on n vertices such that G does not contain a rainbow copy of H, but adding to G a new edge in any colour from \1,2,…,t\ creates a rainbow copy of H? Here, we completely characterize the growth rates of satt(n, \mathfrakR(H)) as a function of n, for any graph H belonging to a large class of connected graphs and for any t≥ e(H). This classification includes all connected graphs of minimum degree 2. In particular, we prove that satt(n, \mathfrakR(Kr))=Θ(nlog n), for any r≥ 3 and t≥ r \choose 2, thus resolving a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We also pose several new problems and conjectures.