Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
From MaRDI portal
Publication:423641
DOI10.1016/J.JCTA.2012.02.004zbMATH Open1242.05189arXiv1107.1219OpenAlexW2127902766WikidataQ105583655 ScholiaQ105583655MaRDI QIDQ423641FDOQ423641
Authors: Noga Alon, Peter Frankl, Hao Huang, Vojtěch Rödl, Andrzej Ruciński, Benny Sudakov 
Publication date: 4 June 2012
Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)
Abstract: 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 ErdH{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 -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.
Full work available at URL: https://arxiv.org/abs/1107.1219
Recommendations
Vertex degrees (05C07) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- On maximal paths and circuits of graphs
- Embedding large subgraphs into dense graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- Some Theorems on Abstract Graphs
- Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Near perfect coverings in graphs and hypergraphs
- Matchings in 3-uniform hypergraphs
- On the maximum number of edges in a triple system not containing a disjoint family of a given size
- On perfect matchings in uniform hypergraphs with large minimum vertex degree
- Title not available (Why is that?)
- Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
- Title not available (Why is that?)
- Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
- The size of a hypergraph and its matching number
- Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
- Perfect matchings in uniform hypergraphs with large minimum degree
- Degrees giving independent edges in a hypergraph
- On a Chebyshev-Type Inequality for Sums of Independent Random Variables
- Optimal File Sharing in Distributed Networks
- Distributed Storage Allocations
Cited In (70)
- Vertex degree sums for matchings in 3-uniform hypergraphs
- A stability result on matchings in 3-uniform hypergraphs
- Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
- Rainbow perfect matchings for 4-uniform hypergraphs
- Some results around the Erdős matching conjecture
- Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs
- On the matching number and the independence number of a random induced subhypergraph of a hypergraph
- Transversal Hamilton cycle in hypergraph systems
- Title not available (Why is that?)
- On the matching number of \(k\)-uniform connected hypergraphs with maximum degree
- On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels
- Packing \(k\)-partite \(k\)-uniform hypergraphs
- A note on perfect matchings in uniform hypergraphs
- Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
- Vertex degree sums for matchings in 3-uniform hypergraphs
- Improved bound on vertex degree version of Erdős matching conjecture
- Perfect matchings in 3-partite 3-uniform hypergraphs
- Degree versions of theorems on intersecting families via stability
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Perfect matchings in random s‐uniform hypergraphs
- Dirac-type theorems in random hypergraphs
- Nearly perfect matchings in uniform hypergraphs
- Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
- A generalization of Erdős' matching conjecture
- The Erdős matching conjecture and concentration inequalities
- Improved bounds for Erdős' matching conjecture
- Erdős matching conjecture for almost perfect matchings
- A geometric theory for hypergraph matching
- Fractional matchings in hypergraphs
- Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
- Perfect matchings in hypergraphs and the Erdős matching conjecture
- On vertex independence number of uniform hypergraphs
- Perfect matchings in 4-uniform hypergraphs
- Matching of given sizes in hypergraphs
- A linear bound on the Manickam-Miklós-Singhi conjecture
- Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs
- Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- \(d\)-matching in 3-uniform hypergraphs
- Rainbow spanning structures in graph and hypergraph systems
- Near perfect matchings in \(k\)-uniform hypergraphs
- A better bound on the size of rainbow matchings
- Hamilton cycles in dense vertex-transitive graphs
- Rainbow matchings for 3-uniform hypergraphs
- Minimum degree conditions for tight Hamilton cycles
- Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
- How to Poison Your Mother-in-Law, and Other Caching Problems
- The complexity of perfect matchings and packings in dense hypergraphs
- Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- On perfect matchings and tilings in uniform hypergraphs
- Matching in 3-uniform hypergraphs
- On maximal tail probability of sums of nonnegative, independent and identically distributed random variables
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- On Rainbow Matchings for Hypergraphs
- Near-perfect clique-factors in sparse pseudorandom graphs
- Near-perfect clique-factors in sparse pseudorandom graphs
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- Transitive tournament tilings in oriented graphs with large minimum total degree
- Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
- Maximum size of a graph with given fractional matching number
- On the rainbow matching conjecture for 3-uniform hypergraphs
- Rainbow version of the Erdős Matching Conjecture via concentration
- A note on exact minimum degree threshold for fractional perfect matchings
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Forbidding Hamilton cycles in uniform hypergraphs
- An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets
- Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
- On the \(A_\alpha\)-spectral radius of graphs without large matchings
This page was built for publication: Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423641)
