Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels

Details Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels

2011-07-06

arxiv.org/abs/1107.1219v2

Mathematics

Combinatorics

Scientific paper

In this paper we study conditions which guarantee the existence of perfect matchings and perfect fractional matchings in uniform hypergraphs. We reduce this problem to an old conjecture by Erd\H{o}s on estimating the maximum number of edges in a hypergraph when the (fractional) matching number is given, which we are able to solve in some special cases using probabilistic techniques. Based on these results, we obtain some general theorems on the minimum $d$-degree ensuring the existence of perfect (fractional) matchings. In particular, we asymptotically determine the minimum vertex degree which guarantees a perfect matching in 4-uniform and 5-uniform hypergraphs. We also discuss an application to a problem of finding an optimal data allocation in a distributed storage system.

Affiliated with

Also associated with

No associations

Rating

Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels 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 Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Large matchings in uniform hypergraphs and the conjectures of Erdos and Samuels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-678867