Name
Abstract | ||
|---|---|---|
Let E={X(1),X(2),...,X(m)} where the X(i) subset of or equal to V for 1 less than or equal to i less than or equal to m are distinct. The hypergraph G=(V,E) is said to be s-uniform if \X(1)\=s for 1 less than or equal to i less than or equal to m. A set of edges M={X(i) : i is an element of I} is a perfect matching if(i) i not equal j is an element of I implies X(i) boolean AND X(i) = 0, and(ii) U-i is an element of I X(i)=V.In this article we consider the question of whether a random s-uniform hypergraph contains a perfect matching. Let s greater than or equal to 3 be fixed and m/n(4/3)-->infinity. We show that an s-uniform hypergraph with m edges chosen uniformly from [74] contains a perfect matching with high probability. This improves an earlier result of Schmidt and Shamir who showed that m/n(3/2)-->infinity suffices. (C) 1995 John Wiley and Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1002/rsa.3240070104 | Random Struct. Algorithms |
Keywords | Field | DocType |
hypergraphs,random graphs | Discrete mathematics,Combinatorics,Random graph,Constraint graph,Hypergraph,Mathematics | Journal |
Volume | Issue | ISSN |
7 | 1 | 1042-9832 |
Citations | PageRank | References |
9 | 1.33 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan M. Frieze | 1 | 4837 | 787.00 |
| Svante Janson | 2 | 1009 | 149.67 |