Threshold Functions for H-factors

DOI10.1017/S0963548300000559MaRDI QIDQ4290084zbMATH OpenFDO

Authors Noga Alon, Raphael Yuster

Publication date 28 August 1994

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548300000559

zbMATH Keywords

\(H\)-factorfractional arboricityproblem of Erdősrandom graphspanning subgraphthreshold function

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• scientific article; zbMATH DE number 5630514
• \(H(n)\)-factors in random graphs
• Factors in random graphs
• Nonvertex-balanced factors in random graphs
• Triangle Factors in Random Graphs

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A useful elementary correlation inequality
• Constructing a perfect matching is in random NC
• Decomposition of Finite Graphs Into Forests
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Hamiltonian circuits in random graphs
• On the existence of a factor of degree one of a connected random graph
• Poisson approximation for large deviations
• Spanning subgraphs of random graphs
• Threshold functions for extension statements

Cited in

(27)

• Almost \(H\)-factors in dense graphs
• \(H\)-factors in dense graphs
• The covering threshold of a directed acyclic graph by directed acyclic subgraphs
• Fairest edge usage and minimum expected overlap for random spanning trees
• Corrádi and Hajnal's theorem for sparse random graphs
• Cycle factors and renewal theory
• Factors in random graphs
• scientific article; zbMATH DE number 5630514 (Why is no real title available?)
• Sharp thresholds of graph properties, and the k-sat problem
• Triangle Factors in Random Graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• A note on the existence of fractional \(f\)-factors in random graphs
• Nonvertex-balanced factors in random graphs
• \({K_4}\)-factors in random graphs
• Tilings in randomly perturbed dense graphs
• On fractional K‐factors of random graphs
• Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors
• Random triangles in random graphs
• Cycle Saturation in Random Graphs
• Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022
• The hitting time of clique factors
• Minimum degree threshold for \(H\)-factors with high discrepancy
• H-factors in graphs with small independence number
• The hitting time of clique factors (extended abstract)
• Tiling random regular graphs efficiently
• Increasing the flexibility of the herding attack
• \(H(n)\)-factors in random graphs

This page was built for publication: Threshold Functions for H-factors

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