Contents Online

# Journal of Combinatorics

## Volume 6 (2015)

### Number 4

### Ordered Ramsey theory and track representations of graphs

Pages: 445 – 456

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

#### Authors

#### 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