Advances in anti-Ramsey theory for random graphs
Abstract
Given graphs G and H, we denote the following property by G rb → p H: for every proper edge-colouring of G (with an arbitrary number of colours) there is a rainbow copy of H in G, i.e., a copy of H with no two edges of the same colour. It is known that, for every graph H, the threshold function pHrb = pHrb(n) of this property for the binomial random graph G(n, p), is asymptotically at most n-1/m(2)(H), where m(2)(H) denotes the so-called maximum 2-density of H. In this work we discuss this and some recent results in the study of anti-Ramsey properties in random graphs, and we prove that if H = C4 or H = K4 then pHrb < n-1/m(2)(H), which is in contrast with the known facts that pckrb = n-1/m2(Ck) for k ≥ 7, and pklrb = n-1/m(2)(Kl) for k ≥ 19.
References
Bollobás, B. and Thomason, A. (1987). Threshold functions. Combinatorica, 7(1):35–38.
Chung, F. and Graham, R. (2008). Quasi-random graphs with given degree sequences. Random Structures & Algorithms, 32(1):1–19.
Erdős, P. (1979). Some old and new problems in various branches of combinatorics. In Proc. 10th southeastern conference on combinatorics, graph theory and computing, pages 19–37, Winnipeg, Man. Utilitas Math.
Kohayakawa, Y. (1997). Szemerédi’s regularity lemma for sparse graphs. In Foundations of computational mathematics (Rio de Janeiro, 1997), pages 216–230. Springer, Berlin.
Kohayakawa, Y., Konstadinidis, P. B., and Mota, G. O. (2014). On an anti-Ramsey thresh-old for random graphs. European Journal of Combinatorics, 40:26–41.
Kohayakawa, Y., Konstadinidis, P. B., and Mota, G. O. (2017). On an anti-ramsey thresh-old for sparse graphs with one triangle. Journal of Graph Theory. In press.
Kohayakawa, Y. and Rödl, V. (2003). Szemerédi’s regularity lemma and quasi-randomness. In Recent advances in algorithms and combinatorics, volume 11 of CMS Books Math./Ouvrages Math. SMC, pages 289–351. Springer, New York.
Nenadov, R., Person, Y., Škorić, N., and Steger, A. (2017). An algorithmic framework for obtaining lower bounds for random Ramsey problems. J. Combin. Theory Ser. B, 124:1–38.
Rödl, V. and Ruciński, A. (1993). Lower bounds on probability thresholds for Ramsey properties. In Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., pages 317–346. János Bolyai Math. Soc., Budapest.
Rödl, V. and Ruciński, A. (1995). Threshold functions for Ramsey properties. J. Amer. Math. Soc., 8(4):917–942.
Rödl, V. and Tuza, Z. (1992). Rainbow subgraphs in properly edge-colored graphs. Random Structures Algorithms, 3(2):175–182.
Szemerédi, E. (1978). Regular partitions of graphs. In Problèmes combinatoires et théorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 of Colloq. Internat. CNRS, pages 399–401. CNRS, Paris.
