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 ( log log n log log log n ) and O(log log n).
No takes yet. Share an insight, caveat, or question.
Milans et al. (2015) studied this question.