On ordered Ramsey numbers of matchings versus triangles

EUROCOMB’23

Martin Balko Marian Poljak

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-013

PDF
Abstract
For graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the ordered Ramsey number $r_<(G^<,H^<)$ is the smallest $N \in \mathbb{N}$ such that any red-blue coloring of the edges of the complete ordered graph $K^<_N$ on $N$ vertices contains either a blue copy of $G^<$ or a red copy of $H^<$. Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_<(M^<,K^<_3)$ where $M^<$ is an $n$-vertex ordered matching. We prove that almost all $n$-vertex ordered matchings $M^<$ with interval chromatic number 2 satisfy $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{5/4})$ and $r_<(M^<,K^<_3) \in O(n^{7/4})$, improving a recent result by Rohatgi (2019). We also show that there are $n$-vertex ordered matchings $M^<$ with interval chromatic number at least 3 satisfying $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{4/3})$, which asymptotically matches the best known lower bound on these ordered Ramsey numbers for general $n$-vertex ordered matchings.

Pages:
94–100
References

M. Ajtai, J. Komlós, and E. Szemerédi. A note on Ramsey numbers. J. Combin. Theory Ser. A, 29(3):354-360, 1980.
https://doi.org/10.1016/0097-3165(80)90030-8

N. Alon and J. H. Spencer. The probabilistic method. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, fourth edition, 2016.

M. Balko, J. Cibulka, K. Král, and J. Kynčl. Ramsey numbers of ordered graphs. Electron. J. Combin., 27(1), 2020.
https://doi.org/10.37236/7816

M. Balko, V. Jelínek, and P. Valtr. On ordered Ramsey numbers of bounded-degree graphs. J. Combin. Theory Ser. B, 134:179-202, 2019.
https://doi.org/10.1016/j.jctb.2018.06.002

M. Balko and M. Poljak. On ordered Ramsey numbers of matchings versus triangles. Preprint, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-013

S. A. Choudum and B. Ponnusamy. Ordered Ramsey numbers. Discrete Math., 247(1-3):79-92, 2002.
https://doi.org/10.1016/S0012-365X(01)00161-3

V. Chvátal, V. Rödl, E. Szemerédi, and W. T. Trotter, Jr. The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B, 34(3):239-243, 1983.
https://doi.org/10.1016/0095-8956(83)90037-0

V. Chvatál, V. Rödl, E. Szemerédi, and W. T. Trotter, Jr. The Ramsey number of a graph with bounded maximum degree. J. Combin. Theory Ser. B, 34(3):239-243, 1983.
https://doi.org/10.1016/0095-8956(83)90037-0

J. Cibulka and J. Kynčl. Better upper bounds on the Füredi-Hajnal limits of permutations. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2280-2293. SIAM, Philadelphia, PA, 2017.
https://doi.org/10.1137/1.9781611974782.150

D. Conlon, J. Fox, C. Lee, and B. Sudakov. Ordered Ramsey numbers. J. Combin. Theory Ser. B, 122:353-383, 2017.
https://doi.org/10.1016/j.jctb.2016.06.007

D. Conlon, J. Fox, and B. Sudakov. 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, 2015.
https://doi.org/10.1017/CBO9781316106853.003

P. Erdős. Some remarks on the theory of graphs. Bull. Amer. Math. Soc., 53:292-294, 1947.
https://doi.org/10.1090/S0002-9904-1947-08785-1

P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Math., 2:463-470, 1935.

X. He and M. Kwan. Universality of random permutations. Bull. Lond. Math. Soc., 52(3):515-529, 2020.
https://doi.org/10.1112/blms.12345

J. H. Kim. The Ramsey number R(3, t) has order of magnitude t2/ log t. Random Structures Algorithms, 7(3):173-207, 1995.
https://doi.org/10.1002/rsa.3240070302

K. G. Milans and D. B. Stolee, D.and West. Ordered Ramsey theory and track representations of graphs. J. Comb., 6(4):445-456, 2015.
https://doi.org/10.4310/JOC.2015.v6.n4.a3

J. Pach and G. Tardos. Forbidden paths and cycles in ordered graphs and matrices. Israel J. Math., 155:359-380, 2006.
https://doi.org/10.1007/BF02773960

F. P. Ramsey. On a Problem of Formal Logic. Proc. London Math. Soc. (2), 30(4):264- 286, 1929.
https://doi.org/10.1112/plms/s2-30.1.264

D. Rohatgi. Off-diagonal ordered Ramsey numbers of matchings. Electron. J. Combin., 26(2):Paper No. 2.21, 18, 2019.
https://doi.org/10.37236/8085

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Martin Balko, Marian Poljak

PDF