Random graph orders

DOI10.1007/BF00341633zbMath0697.06004OpenAlexW1974575606WikidataQ57401611 ScholiaQ57401611MaRDI QIDQ911622

Michael Henry Albert, Alan M. Frieze

Publication date: 1989

Published in: Order (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00341633

zbMATH Keywords

diagramheightdimensionjump numberrandom posetsrandom graphtransitive closurerandom diagramsrandom graph orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Related Items

Zero-one laws with variable probability ⋮ Unnamed Item ⋮ Evaluating topological ordering in directed acyclic graphs ⋮ Uniform random posets ⋮ Order-invariant measures on causal sets ⋮ First order properties of random posets ⋮ The reversal ratio of a poset. ⋮ Continuum limits for classical sequential growth models ⋮ Random graph orders do not satisfy a 0–1 law ⋮ Parallel execution of schedules with random dependency graph ⋮ On tail distribution of interpost distance ⋮ Performance considerations on a random graph model for parallel processing

Cites Work

• Unnamed Item
• Unnamed Item
• Random orders
• Connectedness and diameter for random orders of fixed dimension
• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• Weighted sums of certain dependent random variables
• On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
• Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
• Probabilities on finite models
• Probability Inequalities for Sums of Bounded Random Variables