Ramsey numbers for partially-ordered sets

DOI10.1007/S11083-017-9449-9zbMATH Open1417.05238arXiv1512.05261OpenAlexW2964048878MaRDI QIDQ1789062FDOQ1789062

Authors: Christopher Cox, Derrick Stolee 

Publication date: 9 October 2018

Published in: Order (Search for Journal in Brave)

Abstract: We present a refinement of Ramsey numbers by considering graphs with a partial ordering on their vertices. This is a natural extension of the ordered Ramsey numbers. We formalize situations in which we can use arbitrary families of partially-ordered sets to form host graphs for Ramsey problems. We explore connections to well studied Tur'an-type problems in partially-ordered sets, particularly those in the Boolean lattice. We find a strong difference between Ramsey numbers on the Boolean lattice and ordered Ramsey numbers when the partial ordering on the graphs have large antichains.

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

Recommendations

• Ramsey numbers of partial order graphs (comparability graphs) and implications in ring theory
• scientific article; zbMATH DE number 1341925
• Ramsey numbers of ordered graphs
• Ordered Ramsey numbers
• Ramsey numbers of ordered graphs

zbMATH Keywords

Ramsey theorypartially ordered setsHasse diagram[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Tur%EF%BF%BD%EF%BF%BDn-type+problems&go=Go Tur��n-type problems]Boolean latticeLubell functionordered graphsordered Ramsey numbersBoolean Ramsey numbers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Combinatorics of partially ordered sets (06A07) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• The Chromatic Number of Kneser Hypergraphs
• Title not available (Why is that?)
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• A new upper bound for the bipartite Ramsey problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• A bipartite Ramsey problem and the Zarankiewicz numbers
• An Upper Bound on Zarankiewicz' Problem
• Combinatorial partitions of finite posets and lattices - Ramsey lattices
• Ordered Ramsey theory and track representations of graphs
• Extremal problems for sets forming Boolean algebras and complete partite hypergraphs
• Largest families without an \(r\)-fork
• Largest family without \(A \cup B \subseteq C \cap D\)
• On families of subsets with a forbidden subposet
• Diamond-free families
• On diamond-free subposets of the Boolean lattice
• The partition method for poset-free families
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Bipartite Ramsey numbers and Zarankiewicz numbers
• Boolean algebras and Lubell functions
• On the geometric Ramsey number of outerplanar graphs
• Fibres and ordered set coloring
• Ramsey numbers of ordered graphs
• Ordered Ramsey numbers
• Poset-free families and Lubell-boundedness
• An improvement of the general bound on the largest family of subsets avoiding a subposet
• Title not available (Why is that?)
• Ordered Ramsey numbers of loose paths and matchings
• Ordered Ramsey numbers
• A Ramsey theoretic problem for finite ordered sets
• A Ramseyian theorem on products of trees
• Boolean lattices: Ramsey properties and embeddings

Cited In (15)

• On colorings of the Boolean lattice avoiding a rainbow copy of a poset
• Ramsey properties of countably infinite partial orderings
• In search of the first-order part of Ramsey's theorem for pairs
• Title not available (Why is that?)
• Poset Ramsey number \(R(P,Q_n)\). I: Complete multipartite posets
• Poset Ramsey number \(R(P,Q_n)\). II: \(\mathrm{N}\)-shaped poset
• A construction for Boolean cube Ramsey numbers
• Title not available (Why is that?)
• On the abstract chromatic number and its computability for finitely axiomatizable theories
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• Ramsey numbers of Boolean lattices
• On a Ramsey-theoretic property of orders
• Unordered canonical Ramsey numbers
• Rainbow Ramsey problems for the Boolean lattice
• The Boolean rainbow Ramsey number of antichains, Boolean posets and chains

Uses Software

• SageMath
• z3

This page was built for publication: Ramsey numbers for partially-ordered sets

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