𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Perfect fractional matchings in random hypergraphs

✍ Scribed by Michael Krivelevich

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
890 KB
Volume
9
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

Given an r-uniform hypergraph H = (V, E ) on ( V ( = n vertices, a real-valued function

f(e) 5 1 for all u E V and C e E E f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n + m , at the very moment to when the last isolated vertex disappears, the hypergraph H,, has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (Inn + w(n))/ (;I;), where w(n) is any function tending to infinity with n, then with probability tending to 1 a random r-uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r-partite hypergraphs.

πŸ“œ SIMILAR VOLUMES

New bounds on nearly perfect matchings i
New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help
✍ Van H. Vu πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 253 KB

Let H be a k + 1 -uniform, D-regular hypergraph on n vertices and let H be the minimum number of vertices left uncovered by a matching in H. C j H , the j-codegree of H, is the maximum number of edges sharing a set of j vertices in common. We prove a general upper bound on H , based on the codegree

Transversal hypergraphs to perfect match
Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms
✍ Endre Boros; Khaled Elbassioni; Vladimir Gurvich πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 285 KB

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers

Partial Steiner systems and matchings in
Partial Steiner systems and matchings in hypergraphs
✍ A.V. Kostochka; V. RΓΆdl πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 203 KB

For tk, a t, k T-system is a k-uniform hypergraph H such that any two Ε½ . distinct edges of H have at most t y 1 vertices in common. Clearly, any t, k -system on n n k

Matchings in hypergraphs of large minimu
Matchings in hypergraphs of large minimum degree
✍ Daniela KΓΌhn; Deryk Osthus πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 112 KB

## Abstract It is well known that every bipartite graph with vertex classes of size __n__ whose minimum degree is at least __n__/2 contains a perfect matching. We prove an analog of this result for hypergraphs. We also prove several related results that guarantee the existence of almost perfect mat

Choosability in Random Hypergraphs
Choosability in Random Hypergraphs
✍ Michael Krivelevich; Van H. Vu πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 155 KB

The choice number of a hypergraph H=(V, E) is the least integer s for which, for every family of color lists S=[S(v): v # V], satisfying |S(v)|=s for every v # V, there exists a choice function f so that f (v) # S(v) for every v # V, and no edge of H is monochromatic under f. In this paper we consid