Ordered Ramsey numbers of loose paths and matchings

DOI10.1016/J.DISC.2015.09.026MaRDI QIDQ898098zbMATH OpenOpenAlexFDO

Authors Christopher Cox, Derrick Stolee

Publication date 8 December 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

matchingshypergraph Ramsey theoryloose pathsordered Ramsey numbers

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: For a $k$-uniform hypergraph $G$ with vertex set $1,ldots,n$, the ordered Ramsey number $operatorname{OR}_t(G)$ is the least integer $N$ such that every $t$-coloring of the edges of the complete $k$-uniform graph on vertex set $1,ldots,N$ contains a monochromatic copy of $G$ whose vertices follow the prescribed order. Due to this added order restriction, the ordered Ramsey numbers can be much larger than the usual graph Ramsey numbers. We determine that the ordered Ramsey numbers of loose paths under a monotone order grows as a tower of height one less than the maximum degree. We also extend theorems of Conlon, Fox, Lee, and Sudakov [Ordered Ramsey numbers, arXiv:1410.5292] on the ordered Ramsey numbers of 2-uniform matchings to provide upper bounds on the ordered Ramsey number of $k$-uniform matchings under certain orderings.

Recommendations

• Ramsey numbers of ordered graphs
• Ordered Ramsey numbers
• Ramsey numbers of ordered graphs
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Ordered size Ramsey number of paths

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3262254 (Why is no real title available?)
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• On the geometric Ramsey number of outerplanar graphs
• Ordered Ramsey numbers
• Ordered Ramsey theory and track representations of graphs
• Partition relations for cardinal numbers
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• The Ramsey number for stripes
• The Ramsey number of a graph with bounded maximum degree
• Two remarks on the Burr-Erdős conjecture

Cited in

(16)

• On the abstract chromatic number and its computability for finitely axiomatizable theories
• Ramsey numbers for partially-ordered sets
• Erdős-Szekeres type theorems for ordered uniform matchings
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Turán numbers of ordered tight hyperpaths
• Ramsey numbers of interval 2-chromatic ordered graphs
• Ordered Ramsey numbers
• Ramsey numbers of ordered graphs
• Ramsey problems for monotone paths in graphs and hypergraphs
• Minimal ordered Ramsey graphs
• On ordered Ramsey numbers of bounded-degree graphs
• Variants of the Erdős-Szekeres and Erdős-Hajnal Ramsey problems
• Ordered size Ramsey number of paths
• Off-diagonal ordered Ramsey numbers of matchings
• Ordered Ramsey theory and track representations of graphs
• Ramsey numbers of ordered graphs

This page was built for publication: Ordered Ramsey numbers of loose paths and matchings

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