Ramsey-type problems in orientations of graphs
Abstract
The Ramsey number R(H) of a graph H is the minimum number n such that there exists a graph G on n vertices with the property that every two-coloring of its edges contains a monochromatic copy of H . In this work we study a variant of this notion, called the oriented Ramsey problem, for an acyclic oriented graph H→, in which we require that every orientation G→ of the graph G contains a copy of H→. We also study the threshold function for this problem in random graphs. Finally, we consider the isometric case, in which we require the copy to be isometric, by which we mean that, for every two vertices x, y ∈ V (H→) and their respective copies x', y' in G→, the distance between x and y is equal to the distance between x' and y'.
References
Balko, M., Cibulka, J., Král, K., and Kynčl, J. (2015). Ramsey numbers of ordered graphs. Electronic Notes in Discrete Mathematics, 49:419 – 424. The Eight European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2015.
Balogh, J., Morris, R., and Samotij, W. (2015). Independent sets in hypergraphs. J. Amer. Math. Soc., 28(3):669–709.
Banakh, T., Idzik, A., Pikhurko, O., Protasov, I., and Pszczoła, K. (2017). Isometric copies of directed trees in orientations of graphs.
Conlon, D., Dellamonica, Jr., D., La Fleur, S., Rödl, V., and Schacht, M. (2016). A note on induced Ramsey numbers. arXiv e-prints.
Conlon, D., Fox, J., Lee, C., and Sudakov, B. (2017). Ordered Ramsey numbers. J. Combin. Theory Ser. B, 122:353–383.
Erdős, P. and Moser, L. (1964). On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125–132.
Hàn, H., Retter, T., Rödl, V., and Schacht, M. (2016). Ramsey-type numbers involving graphs and hypergraphs with large girth.
Nenadov, R. and Steger, A. (2016). A short proof of the random Ramsey theorem. Combin. Probab. Comput., 25(1):130–144.
Rödl, V. and Ruciński, A. (1995). Threshold functions for Ramsey properties. J. Amer. Math. Soc., 8(4):917–942.
Rödl, V., Ruciński, A., and Schacht, M. (2016). An exponential-type upper bound for folkman numbers. Combinatorica.
Saxton, D. and Thomason, A. (2015). Hypergraph containers. Invent. Math., 201(3):925–992.
Balogh, J., Morris, R., and Samotij, W. (2015). Independent sets in hypergraphs. J. Amer. Math. Soc., 28(3):669–709.
Banakh, T., Idzik, A., Pikhurko, O., Protasov, I., and Pszczoła, K. (2017). Isometric copies of directed trees in orientations of graphs.
Conlon, D., Dellamonica, Jr., D., La Fleur, S., Rödl, V., and Schacht, M. (2016). A note on induced Ramsey numbers. arXiv e-prints.
Conlon, D., Fox, J., Lee, C., and Sudakov, B. (2017). Ordered Ramsey numbers. J. Combin. Theory Ser. B, 122:353–383.
Erdős, P. and Moser, L. (1964). On the representation of directed graphs as unions of orderings. Magyar Tud. Akad. Mat. Kutató Int. Közl., 9:125–132.
Hàn, H., Retter, T., Rödl, V., and Schacht, M. (2016). Ramsey-type numbers involving graphs and hypergraphs with large girth.
Nenadov, R. and Steger, A. (2016). A short proof of the random Ramsey theorem. Combin. Probab. Comput., 25(1):130–144.
Rödl, V. and Ruciński, A. (1995). Threshold functions for Ramsey properties. J. Amer. Math. Soc., 8(4):917–942.
Rödl, V., Ruciński, A., and Schacht, M. (2016). An exponential-type upper bound for folkman numbers. Combinatorica.
Saxton, D. and Thomason, A. (2015). Hypergraph containers. Invent. Math., 201(3):925–992.
Published
2018-07-26
How to Cite
CAVALAR, Bruno Pasqualotto.
Ramsey-type problems in orientations of graphs. In: PROCEEDINGS OF THE THEORY OF COMPUTATION MEETING (ETC), 3. , 2018, Natal.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2018
.
p. 141-144.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2018.3172.
