Threshold Functions for H-factors
From MaRDI portal
Publication:4290084
DOI10.1017/S0963548300000559zbMath0794.05098MaRDI QIDQ4290084
Publication date: 28 August 1994
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Corrádi and Hajnal's Theorem for Sparse Random Graphs, Sharp thresholds of graph properties, and the $k$-sat problem, On fractional K‐factors of random graphs, Fairest edge usage and minimum expected overlap for random spanning trees, Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors, Cycle Saturation in Random Graphs, Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022, Combinatorial and computational aspects of graph packing and graph decomposition, \(H(n)\)-factors in random graphs, Tilings in Randomly Perturbed Dense Graphs, Nonvertex‐Balanced Factors in Random Graphs, Increasing the flexibility of the herding attack, The covering threshold of a directed acyclic graph by directed acyclic subgraphs
Cites Work
- Constructing a perfect matching is in random NC
- A useful elementary correlation inequality
- Fast probabilistic algorithms for Hamiltonian circuits and matchings
- Spanning subgraphs of random graphs
- Hamiltonian circuits in random graphs
- Threshold functions for extension statements
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- A fast parallel algorithm for the maximal independent set problem
- Poisson approximation for large deviations
- On the existence of a factor of degree one of a connected random graph
- Decomposition of Finite Graphs Into Forests
