Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
From MaRDI portal
(Redirected from Publication:423641)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 4029608 (Why is no real title available?)
- scientific article; zbMATH DE number 1540669 (Why is no real title available?)
- scientific article; zbMATH DE number 3221072 (Why is no real title available?)
- Degrees giving independent edges in a hypergraph
- Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
- Distributed Storage Allocations
- Embedding large subgraphs into dense graphs
- Matchings in 3-uniform hypergraphs
- Near perfect coverings in graphs and hypergraphs
- Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
- On a Chebyshev-Type Inequality for Sums of Independent Random Variables
- On maximal paths and circuits of graphs
- On perfect matchings in uniform hypergraphs with large minimum vertex degree
- On the maximum number of edges in a triple system not containing a disjoint family of a given size
- Optimal File Sharing in Distributed Networks
- Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
- Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Perfect matchings in uniform hypergraphs with large minimum degree
- Some Theorems on Abstract Graphs
- The probabilistic method. With an appendix on the life and work of Paul Erdős.
- The size of a hypergraph and its matching number
Cited in
(70)- Packing \(k\)-partite \(k\)-uniform hypergraphs
- A note on perfect matchings in uniform hypergraphs
- Vertex degree sums for matchings in 3-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
- A stability result on matchings in 3-uniform hypergraphs
- Improved bound on vertex degree version of Erdős matching conjecture
- Perfect matchings in 3-partite 3-uniform hypergraphs
- Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
- Degree versions of theorems on intersecting families via stability
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Dirac-type theorems in random hypergraphs
- Perfect matchings in random s‐uniform 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
- Improved bounds for Erdős' matching conjecture
- A generalization of Erdős' matching conjecture
- The Erdős matching conjecture and concentration inequalities
- Erdős matching conjecture for almost perfect matchings
- Fractional matchings in hypergraphs
- A geometric theory for hypergraph matching
- Perfect matchings in hypergraphs and the Erdős matching conjecture
- On vertex independence number of uniform hypergraphs
- Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
- Perfect matchings in 4-uniform hypergraphs
- Matching of given sizes in hypergraphs
- A linear bound on the Manickam-Miklós-Singhi conjecture
- 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
- Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs
- A better bound on the size of rainbow matchings
- Near perfect matchings in \(k\)-uniform hypergraphs
- Rainbow spanning structures in graph and hypergraph systems
- Hamilton cycles in dense vertex-transitive graphs
- Rainbow perfect matchings for 4-uniform hypergraphs
- Rainbow matchings for 3-uniform hypergraphs
- Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
- Some results around the Erdős matching conjecture
- Minimum degree conditions for tight Hamilton cycles
- How to Poison Your Mother-in-Law, and Other Caching Problems
- The complexity of perfect matchings and packings in dense hypergraphs
- Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform 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
- On the matching number and the independence number of a random induced subhypergraph of a hypergraph
- Transversal Hamilton cycle in hypergraph systems
- 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
- scientific article; zbMATH DE number 7662450 (Why is no real title available?)
- Near-perfect clique-factors in sparse pseudorandom graphs
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- Maximum size of a graph with given fractional matching number
- Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
- On the matching number of \(k\)-uniform connected hypergraphs with maximum degree
- On the rainbow matching conjecture for 3-uniform hypergraphs
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Forbidding Hamilton cycles in uniform hypergraphs
- A note on exact minimum degree threshold for fractional perfect matchings
- Transitive tournament tilings in oriented graphs with large minimum total degree
- Rainbow version of the Erdős Matching Conjecture via concentration
- 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_-spectral radius of graphs without large matchings
- On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels
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)
