On edge-ordered Ramsey numbers

DOI10.1002/RSA.20954MaRDI QIDQ3386532zbMATHOpenAlexFDO

Authors Jacob Fox, Ray Li

Publication date 5 January 2021

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

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

zbMATH Keywords

Ramsey theorysparse graphsedge-ordered graphs

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(6)

• Erdős-Szekeres theorem for multidimensional arrays
• Edge-ordered Ramsey numbers
• Categorical view of the partite lemma in structural Ramsey theory
• Turán problems for edge-ordered graphs
• scientific article; zbMATH DE number 1792649 (Why is no real title available?)
• Edge-ordered Ramsey numbers

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)