Edge ordered hypergraph ramsey numbers do not increase tower height
On edge-ordered Ramsey numbers of hypergraphs
Discrete Mathematics
Summary
The paper studies a special kind of math problem about hypergraphs, which are like webs connecting multiple points. It looks at hypergraphs where the connections have a set order, and considers how hard it is to find a particular ordered structure when the edges are colored in multiple colors. The authors show that requiring an order on these connections does not make the problem much harder than the unordered version, solving an open question from earlier research. For certain cases, their new results improve known bounds and offer clearer insight into how these ordered structures behave.
What this means in practice
- •For combinatorial algorithm designers: Design algorithms that handle ordered hypergraph structures without significantly increasing complexity bounds known for unordered cases.
- •For complexity theorists: Use the improved bounds on edge-ordered hypergraph Ramsey numbers to refine complexity classifications of hypergraph problems involving ordered constraints.
A theory result. No direct application yet.
Authors
Martin Balko, Jelena Glišić
Abstract
For an integer $h\geq2$, an edge-ordered $h$-uniform hypergraph $H^<$ is an $h$-uniform hypergraph with a linear ordering of its hyperedges. For an integer $q \geq 1$, the edge-ordered Ramsey number $R_{\mathrm{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\geq1$ hyperedges, $R_{\mathrm{edge}}(F^<;q) \leq R_h(F;q)^{Cm^2}$ 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\geq3$ and $q\geq2$, 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\log n)}$, improving their bounds for every fixed $q \geq 3$.