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
- 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
- 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?)
- 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₄^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
(80)- Some Ore-type results for matching and perfect matching in \(k\)-uniform hypergraphs
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- On maximal tail probability of sums of nonnegative, independent and identically distributed random variables
- \(d\)-matching in 3-uniform hypergraphs
- A generalization of Erdős' matching conjecture
- Near-perfect clique-factors in sparse pseudorandom graphs
- Matching in 3-uniform hypergraphs
- Rainbow matchings for 3-uniform hypergraphs
- Maximum size of a graph with given fractional matching number
- On the rainbow matching conjecture for 3-uniform hypergraphs
- On the A_-spectral radius of graphs without large matchings
- A note on exact minimum degree threshold for fractional perfect matchings
- Dirac-type theorems in random hypergraphs
- The Erdős matching conjecture and concentration inequalities
- An application of the universality theorem for Tverberg partitions to data depth and hitting convex sets
- The complexity of perfect matchings and packings in dense hypergraphs
- Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
- Degree versions of theorems on intersecting families via stability
- Vertex degree sums for matchings in 3-uniform hypergraphs
- A linear bound on the Manickam-Miklós-Singhi conjecture
- Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
- Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
- Fractional matchings in hypergraphs
- Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
- A better bound on the size of rainbow matchings
- Erdős matching conjecture for almost perfect matchings
- How to Poison Your Mother-in-Law, and Other Caching Problems
- Decision problem for perfect matchings in dense k-uniform hypergraphs
- Perfect matchings in hypergraphs and the Erdős matching conjecture
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Improved bounds for Erdős' matching conjecture
- On vertex independence number of uniform hypergraphs
- Perfect matchings in 3-partite 3-uniform hypergraphs
- Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
- On the matching number and the independence number of a random induced subhypergraph of a hypergraph
- On Rainbow Matchings for Hypergraphs
- Hamilton cycles in dense vertex-transitive graphs
- On perfect matchings and tilings in uniform hypergraphs
- Polynomial-time perfect matchings in dense hypergraphs
- Perfect matchings in random s‐uniform hypergraphs
- Nearly perfect matchings in uniform hypergraphs
- Matching of given sizes in hypergraphs
- A stability result on matchings in 3-uniform hypergraphs
- Rainbow perfect matchings for 4-uniform hypergraphs
- Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
- Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
- Forbidding Hamilton cycles in uniform hypergraphs
- Near perfect matchings in \(k\)-uniform hypergraphs
- Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
- On a connection of two graph-theoretic problems with conjectures of Ramanujan and Samuels
- Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
- A geometric theory for hypergraph matching
- Transitive tournament tilings in oriented graphs with large minimum total degree
- scientific article; zbMATH DE number 7662450 (Why is no real title available?)
- Near-perfect clique-factors in sparse pseudorandom graphs
- Rainbow version of the Erdős Matching Conjecture via concentration
- Anti-Ramsey Number of Matchings in 3-Uniform Hypergraphs
- Rainbow spanning structures in graph and hypergraph systems
- Improved bound on vertex degree version of Erdős matching conjecture
- Large Yk,b ${Y}_{k,b}$‐tilings and Hamilton ℓ $\ell $‐cycles in k $k$‐uniform hypergraphs
- Minimum degree conditions for tight Hamilton cycles
- Vertex degree sums for matchings in 3-uniform hypergraphs
- On the matching number of \(k\)-uniform connected hypergraphs with maximum degree
- Some results around the Erdős matching conjecture
- Transversal Hamilton cycle in hypergraph systems
- A stability result for almost perfect matchings
- An analogue of the Erdős matching conjecture for weak compositions
- Some stability results for linear forests in hypergraphs
- Color-bias perfect matchings in hypergraphs
- On the Keevash-Knox-Mycroft conjecture
- Vertex degree sums for perfect matchings in 3-uniform hypergraphs
- Toward a high-dimensional Dirac's theorem
- Matchings in multipartite hypergraphs
- Clique factors in pseudorandom graphs
- A partial edge-density version of the Corrádi-Hajnal theorem in hypergraphs
- Packing k-partite k-uniform hypergraphs
- Perfect matchings in 4-uniform hypergraphs
- A note on perfect matchings in uniform hypergraphs
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)
