On edge-ordered Ramsey numbers

DOI10.1002/RSA.20954zbMATH Open1454.05076arXiv1906.08234OpenAlexW3081667540MaRDI QIDQ3386532FDOQ3386532

Authors: Jacob Fox, Ray Li 

Publication date: 5 January 2021

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: An edge-ordered graph is a graph with a linear ordering of its edges. Two edge-ordered graphs are equivalent if their is an isomorphism between them preserving the ordering of the edges. The edge-ordered Ramsey number $r_{edge}(H;q)$ of an edge-ordered graph $H$ is the smallest $N$ such that there exists an edge-ordered graph $G$ on $N$ vertices such that, for every $q$-coloring of the edges of $G$, there is a monochromatic subgraph of $G$ equivalent to $H$. Recently, Balko and Vizer announced that $r_{edge}(H;q)$ exists. However, their proof uses the Graham-Rothschild theorem and consequently gives an enormous upper bound on these numbers. We give a new proof giving a much better bound. We prove that for every edge-ordered graph $H$ on $n$ vertices, we have $r_{edge}(H;q)leq{2}^{c^q{n}^{2q-2}lo{g}^{q}n}$, where $c$ is an absolute constant. We also explore the edge-ordered Ramsey number of sparser graphs and prove a polynomial bound for edge-ordered graphs of bounded degeneracy. We also prove a strengthening for edge-labeled graphs, graphs where every edge is given a label and the labels do not necessary have an ordering.

Full work available at URL: https://arxiv.org/abs/1906.08234

Recommendations

• Edge-ordered Ramsey numbers
• Ordered Ramsey numbers
• Ramsey numbers of ordered graphs
• Ramsey numbers of ordered graphs
• On ordered Ramsey numbers of bounded-degree graphs

zbMATH Keywords

Ramsey theorysparse graphsedge-ordered graphs

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Cites Work

• Probability Inequalities for Sums of Bounded Random Variables
• Title not available (Why is that?)
• Expanding graphs contain all small trees
• The size Ramsey number
• The size Ramsey number of a directed path
• On size Ramsey number of paths, trees, and circuits. I
• The Induced Size-Ramsey Number of Cycles
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Increasing paths in edge ordered graphs
• Increasing Hamiltonian paths in random edge orderings
• Some Combinatorial Theorems on Monotonicity
• Increasing sequences with nonzero block sums and increasing paths in edge-ordered graphs
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• Combinatorial Relations and Chromatic Graphs
• Primitive Recursive Bounds for Van Der Waerden Numbers
• Ramsey numbers of degenerate graphs
• On two problems in graph Ramsey theory
• Title not available (Why is that?)
• Induced Ramsey-type theorems
• Ramsey's Theorem for n-Parameter Sets
• Title not available (Why is that?)
• A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph
• Title not available (Why is that?)
• Ramsey numbers of ordered graphs
• Ordered Ramsey numbers
• Recent developments in graph Ramsey theory
• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• On some multicolor Ramsey properties of random graphs
• The oriented size Ramsey number of directed paths
• Nearly-linear monotone paths in edge-ordered graphs
• Monotone paths in dense edge-ordered graphs
• Ordered size Ramsey number of paths
• Most edge-orderings of \(K_{n}\) have maximal altitude

Cited In (5)

• Edge-ordered Ramsey numbers
• Erdős-Szekeres theorem for multidimensional arrays
• Turán problems for edge-ordered graphs
• Title not available (Why is that?)
• Categorical view of the partite lemma in structural Ramsey theory

This page was built for publication: On edge-ordered Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386532)