2019/02/01 by Geneson, Jesse, Holmes, Amber, Liu, Xujun +3 · 1 citation
#05D10 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1902.00259
An ordered graph G is a simple graph together with a total ordering on its vertices. The (2-color) Ramsey number of G 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 G 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 nq+o(1) for any given exponent q∈(1,2).