Advances in anti-Ramsey theory for random graphs

• Guilherme Oliveira Mota UFABC / USP

DOI: https://doi.org/10.5753/etc.2017.3204

Resumo

Dados grafos G e H, denotamos a seguinte propriedade por G rb → p H: para toda coloração própria das arestas de G (com uma quantidade arbitrária de cores) existe uma cópia multicolorida de H em G, i.e., uma cópia de H sem duas arestas da mesma cor. Sabe-se que, para todo grafo H, a função limiar p_H^rb = p_H^rb(n) para essa propriedade no grafo aleatório binomial G(n, p) é assintoticamente no máximo n^-1/m(2)(H), onde m⁽²⁾(H) denota a assim chamada 2-densidade máxima de H. Neste trabalho discutimos esse e alguns resultados recentes no estudo de propriedades anti-Ramsey para grafos aleatórios, e mostramos que se H = C₄ ou H = K₄ então p_H^rb < n^-1/m(2)(H), que está em contraste com os fatos conhecidos de que p_ck^rb = n^-1/m2(Ck) para k ≥ 7, e p_kl^rb = n^-1/m(2)(Kl) para k ≥ 19.

Referências

Bollobás, B. (2001). Random graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press.

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.