Journal of Combinatorics

Volume 6 (2015)

Number 4

Ordered Ramsey theory and track representations of graphs

Pages: 445 – 456

DOI: https://dx.doi.org/10.4310/JOC.2015.v6.n4.a3

Authors

Kevin G. Milans (Department of Mathematics, West Virginia University, Morgantown, W.V., U.S.A.)

Derrick Stolee (Department of Computer Science, Iowa State University, Ames, Ia., U.S.A.)

Douglas B. West (Zhejiang Normal University, Jinhua, China; and Department of Mathematics, University of Illinois, Urbana, Il., U.S.A.)

Abstract

We study an ordered version of hypergraph Ramsey numbers for linearly ordered vertex sets, due to Fox, Pach, Sudakov, and Suk. In the $k$-uniform ordered path, the edges are the sets of $k$ consecutive vertices in a linear order. Moshkovitz and Shapira described its ordered Ramsey number in terms of an enumerative problem: it equals $1$ plus the number of elements in the poset obtained by starting with a certain disjoint union of chains and repeatedly taking the poset of down-sets, $k-1$ times. After presenting a proof of this and the resulting bounds, we apply the bounds to study the minimum number of interval graphs whose union is the line graph of the $n$-vertex complete graph, proving the conjecture of Heldt, Knauer, and Ueckerdt that this grows with $n$. In fact, the growth rate is between $\Omega \frac{\log \log n}{\log \log \log n)}$ and $O(\log \log n)$.

2010 Mathematics Subject Classification

Primary 05C55, 05C62. Secondary 05C35, 05C65.

Published 31 July 2015