Existence thresholds and Ramsey properties of random posets

DOI10.1002/RSA.20952zbMATH Open1454.05122arXiv1910.00485OpenAlexW3047662601MaRDI QIDQ3386529FDOQ3386529

Authors: Victor Falgas-Ravry, Klas Markström, Andrew Treglown, Yi Zhao 

Publication date: 5 January 2021

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

Abstract: Let $mathcalP(n)$ denote the power set of $[n]$, ordered by inclusion, and let $mathcalP(n,p)$ denote the random poset obtained from $mathcalP(n)$ by retaining each element from $mathcalP(n)$ independently at random with probability $p$ and discarding it otherwise. Given any fixed poset $F$ we determine the threshold for the property that $mathcalP(n,p)$ contains $F$ as an induced subposet. We also asymptotically determine the number of copies of a fixed poset $F$ in $mathcalP(n)$. Finally, we obtain a number of results on the Ramsey properties of the random poset $mathcalP(n,p)$.

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

Recommendations

• First order properties of random posets
• Ramsey properties of random discrete structures
• The dimension of random ordered sets
• Threshold Functions for Ramsey Properties
• Random orders of dimension 2

zbMATH Keywords

Boolean latticerandom posetsRamsey propertiesexistence thresholds

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Two poset polytopes
• Asymptotic Enumeration of Partial Orders on a Finite Set
• Maximum-size antichains in random set-systems
• The height of a random partial order: Concentration of measure
• A random version of Sperner's theorem
• Threshold Functions for Ramsey Properties
• Ramsey theory for discrete structures
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random graphs with monochromatic triangles in every edge coloring
• Set families with a forbidden subposet
• Largest family without \(A \cup B \subseteq C \cap D\)
• Sperner type theorems with excluded subposets
• \(Q _{2}\)-free families in the Boolean lattice
• Maximum antichains in random subsets of a finite set
• The width of random subsets of Boolean lattices
• Small sublattices in random subsets of Boolean lattices
• The length of random subsets of Boolean lattices
• Title not available (Why is that?)
• On crown-free families of subsets
• Title not available (Why is that?)
• Induced and non-induced forbidden subposet problems
• An upper bound on the size of diamond-free families of sets
• Progress on poset-free families of subsets
• Applications of graph containers in the Boolean lattice
• Boolean lattices: Ramsey properties and embeddings

Cited In (9)

• First order properties of random posets
• Title not available (Why is that?)
• Rectilinear approximation and volume estimates for hereditary bodies via [0, 1]‐decorated containers
• 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
• Poset Ramsey numbers: large Boolean lattice versus a fixed poset
• Title not available (Why is that?)
• Existence theorems for measures on continous posets, with applications to random set theory.

This page was built for publication: Existence thresholds and Ramsey properties of random posets

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