On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph

DOI10.1137/0605049zbMath0558.05026OpenAlexW2085227596MaRDI QIDQ3222867

Paul Erdős, Amnon B. Barak

Publication date: 1984

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6a73f0cbff6604de5aabab6a3be04a68df6e36b1

zbMATH Keywords

random digraphindependent vertices

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Zero-one laws (60F20) Directed graphs (digraphs), tournaments (05C20)

Related Items (23)

Limiting properties of random graph models with vertex and edge weights ⋮ On the asymptotics for the minimal distance between extreme vertices in a generalised Barak-Erdős graph ⋮ Unnamed Item ⋮ Evaluating topological ordering in directed acyclic graphs ⋮ Convergence of directed random graphs to the Poisson-weighted infinite tree ⋮ Searching in random partially ordered sets ⋮ A scalable approach to computing representative lowest common ancestor in directed acyclic graphs ⋮ Probabilistic and analytical properties of the last passage percolation constant in a weighted random directed graph ⋮ A dynamic topological sort algorithm for directed acyclic graphs ⋮ Limit theorems for a random directed slab graph ⋮ A Path Cover Technique for LCAs in Dags ⋮ Random graph orders ⋮ Unnamed Item ⋮ Average-Case Analysis of Online Topological Ordering ⋮ Average-case analysis of incremental topological ordering ⋮ The Hilbert-Galton board ⋮ Random graph orders do not satisfy a 0–1 law ⋮ Parallel execution of schedules with random dependency graph ⋮ Barak-Erdős graphs and the infinite-bin model ⋮ Two-sided infinite-bin models and analyticity for Barak-Erdős graphs ⋮ On the length of the shortest path in a sparse Barak-Erdős graph ⋮ On tail distribution of interpost distance ⋮ Random partial orders, posts, and the causal set approach to discrete quantum gravity

Cites Work

• Unnamed Item
• Unnamed Item
• On colouring random graphs
• Cliques in random graphs

This page was built for publication: On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph