On edge-ordered Ramsey numbers of hypergraphs
math.CO, cs.DM
Submitted: 2026-10-29
Updated: 2026-10-29
Comments: 10 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: For an integer h at least2, an edge-ordered h-uniform hypergraph H< is an h-uniform hypergraph with a linear ordering of its hyperedges.
Terminology
Abstract
For an integer h at least2, an edge-ordered h-uniform hypergraph H< is an h-uniform hypergraph with a linear ordering of its hyperedges. For an integer q at least 1, the edge-ordered Ramsey number R edge(H<;q) of H< is the smallest positive integer N such that there exists an edge-ordered h-uniform hypergraph G< on N vertices such that, for every q-coloring of the hyperedges of G<, there is a monochromatic copy of H< in G< preserving the hyperedge order. In this note, we show that, for every edge-ordered h-uniform hypergraph F< on n vertices with m at least1 hyperedges, R edge(F<;q) at most R h(F;q) Cm squared where F is the underlying unordered hypergraph, R h(F;q) is its standard q-color Ramsey number, and C=C(h,q)>0 is a constant. For fixed h at least3 and q at least2, this shows that prescribing the hyperedge order does not require an increase in the tower height of the classical upper bound. It also settles a problem posed by Fox and Li (2020), and for h=2 gives the bound 2 O(n 4 n), improving their bounds for every fixed q at least 3.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality