Ramsey numbers of ordered graphs under graph operations

MaRDI QIDQ6313414zbMATH OpenFDO

Authors Jesse Geneson, Xujun Liu, Dana Neidinger, Yanitsa Pehova, Isaac Wass

Publication date 1 February 2019

Mathematics Subject Classification ID

Ramsey theory (05D10)

Abstract: An ordered graph $mathcalG$ is a simple graph together with a total ordering on its vertices. The (2-color) Ramsey number of $mathcalG$ is the smallest integer $N$ such that every 2-coloring of the edges of the complete ordered graph on $N$ vertices has a monochromatic copy of $mathcalG$ that respects the ordering. In this paper we investigate the effect of various graph operations on the Ramsey number of a given ordered graph, and detail a general framework for applying results on extremal functions of 0-1 matrices to ordered Ramsey problems. We apply this method to give upper bounds on the Ramsey number of ordered matchings arising from sum-decomposable permutations, an alternating ordering of the cycle, and an alternating ordering of the tight hyperpath. We also construct ordered matchings on $n$ vertices whose Ramsey number is $n^{q+o(1)}$ for any given exponent $qin(1,2)$.

This page was built for publication: Ramsey numbers of ordered graphs under graph operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6313414)