Factors in random graphs

Details Factors in random graphs Factors in random graphs

2008-03-24

arxiv.org/abs/0803.3406v1

Mathematics

Combinatorics

To appear in Random Structures and Algorithms

Scientific paper

Let $H$ be a fixed graph on $v$ vertices. For an $n$-vertex graph $G$ with $n$ divisible by $v$, an $H$-{\em factor} of $G$ is a collection of $n/v$ copies of $H$ whose vertex sets partition $V(G)$. In this paper we consider the threshold $th_{H} (n)$ of the property that an Erd\H{o}s-R\'enyi random graph (on $n$ points) contains an $H$-factor. Our results determine $th_{H} (n)$ for all strictly balanced $H$. The method here extends with no difficulty to hypergraphs. As a corollary, we obtain the threshold for a perfect matching in random $k$-uniform hypergraph, solving the well-known "Shamir's problem."

Affiliated with

Also associated with

No associations

Rating

Factors in random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Factors in random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Factors in random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-615749