Ordered Ramsey numbers of loose paths and matchings

DOI10.1016/J.DISC.2015.09.026zbMATH Open1327.05225arXiv1411.4058OpenAlexW1803931064MaRDI QIDQ898098FDOQ898098

Christopher Cox, Derrick Stolee

Publication date: 8 December 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Ramsey numbers of interval 2-chromatic ordered graphs
• Off-diagonal ordered Ramsey numbers of matchings
• On the abstract chromatic number and its computability for finitely axiomatizable theories
• Minimal ordered Ramsey graphs
• On-line size Ramsey number for monotone \(k\)-uniform ordered paths with uniform looseness
• Ramsey numbers for partially-ordered sets

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)