Número de Ramsey relativo a arestas de potências de caminhos
Resumo
Dados grafos G e H e um inteiro positivo q, dizemos que G é q-Ramsey para H se toda q-coloração das arestas de G contém uma cópia monocromática de H. Denotamos essa propriedade por G ⭢ (H)q. O número de Ramsey relativo a arestas r̂(H) de um grafo H é definido como r̂(H) = min{|E(G)|: G ⭢ (H)2}. Respondendo uma pergunta sugerida por Conlon, provamos que r̂(Pnk) = O(n) para todo k fixo, onde Pnk é a k-ésima potência do caminho com n vértices Pn, i.e., o grafo com conjunto de vértices V(Pn) e todas as arestas {u, v} tais que a distância entre u e v em Pn é no máximo k.
Referências
Alon, N. and Chung, F. R. K. (1988). Explicit construction of linear sized tolerant networks. Discrete Math., 72(1-3):15–19.
Beck, J. (1983). On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory, 7(1):115–129.
Beck, J. (1990). On size Ramsey number of paths, trees and circuits. II. In Mathematics of Ramsey theory, volume 5 of Algorithms Combin., pages 34–45. Springer, Berlin.
Ben-Eliezer, I., Krivelevich, M., and Sudakov, B. (2012). The size Ramsey number of a directed path. J. Combin. Theory Ser. B, 102(3):743–755.
Conlon, D. (2016). Problema sugerido para o ATI–HIMR Focused Research Workshop: Large-scale structures in random graphs, Alan Turing Institute, Dezembro de 2016.
Conlon, D., Fox, J., and Sudakov, B. (2015). Recent developments in graph Ramsey theory. In Surveys in combinatorics 2015, volume 424 of London Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge.
Dellamonica, Jr., D. (2012). The size-Ramsey number of trees. Random Structures Algorithms, 40(1):49–73.
Dudek, A. and Prałat, P. (2015). An alternative proof of the linearity of the size-Ramsey number of paths. Combin. Probab. Comput., 24(3):551–555.
Erdős, P. (1981). On the combinatorial problems which I would most like to see solved. Combinatorica, 1(1):25–42.
Erdős, P., Faudree, R. J., Rousseau, C. C., and Schelp, R. H. (1978). The size Ramsey number. Period. Math. Hungar., 9(1-2):145–161.
Erdős, P. and Lovász, L. (1975). Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam.
Friedman, J. and Pippenger, N. (1987). Expanding graphs contain all small trees. Combinatorica, 7(1):71–76.
Haxell, P. E. and Kohayakawa, Y. (1995). The size-Ramsey number of trees. Israel J. Math., 89(1-3):261–274.
Haxell, P. E., Kohayakawa, Y., and Łuczak, T. (1995). The induced size-Ramsey number of cycles. Combin. Probab. Comput., 4(3):217–239.
Ke, X. (1993). The size Ramsey number of trees with bounded degree. Random Structures Algorithms, 4(1):85–97.
Kohayakawa, Y., Retter, T., and Rödl, V. (2016). The size-Ramsey number of short subdivisions of bounded degree graphs. Submitted, 2016.
Kohayakawa, Y., Rödl, V., Schacht, M., and Szemerédi, E. (2011). Sparse partition universal graphs for graphs of bounded degree. Adv. Math., 226(6):5041–5065.
Kővári, T., Sós, V. T., and Turán, P. (1954). On a problem of K. Zarankiewicz. Colloquium Math., 3:50–57.
Letzter, S. (2016). Path Ramsey number for random graphs. Combin. Probab. Comput., 25(4):612–622.
Pokrovskiy, A. (2017). Calculating Ramsey numbers by partitioning colored graphs. Journal of Graph Theory, 84(4):477–500.
Ramsey, F. P. (1930). On a problem of formal logic. Proc. London Math. Soc., S2-30(1):264.
Reimer, D. (2002). The Ramsey size number of dipaths. Discrete Math., 257(1):173–175.
Beck, J. (1983). On size Ramsey number of paths, trees, and circuits. I. J. Graph Theory, 7(1):115–129.
Beck, J. (1990). On size Ramsey number of paths, trees and circuits. II. In Mathematics of Ramsey theory, volume 5 of Algorithms Combin., pages 34–45. Springer, Berlin.
Ben-Eliezer, I., Krivelevich, M., and Sudakov, B. (2012). The size Ramsey number of a directed path. J. Combin. Theory Ser. B, 102(3):743–755.
Conlon, D. (2016). Problema sugerido para o ATI–HIMR Focused Research Workshop: Large-scale structures in random graphs, Alan Turing Institute, Dezembro de 2016.
Conlon, D., Fox, J., and Sudakov, B. (2015). Recent developments in graph Ramsey theory. In Surveys in combinatorics 2015, volume 424 of London Math. Soc. Lecture Note Ser., pages 49–118. Cambridge Univ. Press, Cambridge.
Dellamonica, Jr., D. (2012). The size-Ramsey number of trees. Random Structures Algorithms, 40(1):49–73.
Dudek, A. and Prałat, P. (2015). An alternative proof of the linearity of the size-Ramsey number of paths. Combin. Probab. Comput., 24(3):551–555.
Erdős, P. (1981). On the combinatorial problems which I would most like to see solved. Combinatorica, 1(1):25–42.
Erdős, P., Faudree, R. J., Rousseau, C. C., and Schelp, R. H. (1978). The size Ramsey number. Period. Math. Hungar., 9(1-2):145–161.
Erdős, P. and Lovász, L. (1975). Problems and results on 3-chromatic hypergraphs and some related questions. In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, pages 609–627. Colloq. Math. Soc. János Bolyai, Vol. 10. North-Holland, Amsterdam.
Friedman, J. and Pippenger, N. (1987). Expanding graphs contain all small trees. Combinatorica, 7(1):71–76.
Haxell, P. E. and Kohayakawa, Y. (1995). The size-Ramsey number of trees. Israel J. Math., 89(1-3):261–274.
Haxell, P. E., Kohayakawa, Y., and Łuczak, T. (1995). The induced size-Ramsey number of cycles. Combin. Probab. Comput., 4(3):217–239.
Ke, X. (1993). The size Ramsey number of trees with bounded degree. Random Structures Algorithms, 4(1):85–97.
Kohayakawa, Y., Retter, T., and Rödl, V. (2016). The size-Ramsey number of short subdivisions of bounded degree graphs. Submitted, 2016.
Kohayakawa, Y., Rödl, V., Schacht, M., and Szemerédi, E. (2011). Sparse partition universal graphs for graphs of bounded degree. Adv. Math., 226(6):5041–5065.
Kővári, T., Sós, V. T., and Turán, P. (1954). On a problem of K. Zarankiewicz. Colloquium Math., 3:50–57.
Letzter, S. (2016). Path Ramsey number for random graphs. Combin. Probab. Comput., 25(4):612–622.
Pokrovskiy, A. (2017). Calculating Ramsey numbers by partitioning colored graphs. Journal of Graph Theory, 84(4):477–500.
Ramsey, F. P. (1930). On a problem of formal logic. Proc. London Math. Soc., S2-30(1):264.
Reimer, D. (2002). The Ramsey size number of dipaths. Discrete Math., 257(1):173–175.
Publicado
02/07/2017
Como Citar
CLEMENS, Dennis; JENSSEN, Matthew; KOHAYAKAWA, Yoshiharu; MORRISON, Natasha; MOTA, Guilherme Oliveira; REDING, Damian; ROBERTS, Barnaby.
Número de Ramsey relativo a arestas de potências de caminhos. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 2. , 2017, São Paulo.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2017
.
p. 85-88.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2017.3198.
