Fractional and integer matchings in uniform hypergraphs
From MaRDI portal
Publication:2637239
DOI10.1007/978-88-7642-475-5_7zbMATH Open1282.05172arXiv1304.6901OpenAlexW2054420934MaRDI QIDQ2637239FDOQ2637239
Authors: Deryk Osthus, Timothy Townsend, Daniela Kühn 
Publication date: 10 February 2014
Published in: European Journal of Combinatorics, The Seventh European Conference on Combinatorics, Graph Theory and Applications (Search for Journal in Brave)
Abstract: Our main result improves bounds of Markstrom and Rucinski on the minimum d-degree which forces a perfect matching in a k-uniform hypergraph on n vertices. We also extend bounds of Bollobas, Daykin and Erdos by asymptotically determining the minimum vertex degree which forces a matching of size t < n/2(k-1) in a k-uniform hypergraph on n vertices. Further asymptotically tight results on d-degrees which force large matchings are also obtained. Our approach is to prove fractional versions of the above results and then translate these into integer versions.
Full work available at URL: https://arxiv.org/abs/1304.6901
Recommendations
- Fractional and integer matchings in uniform hypergraphs
- Perfect matchings in uniform hypergraphs with large minimum degree
- Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
- A note on exact minimum degree threshold for fractional perfect matchings
- Matchings in 3-uniform hypergraphs
Extremal problems in graph theory (05C35) Vertex degrees (05C07) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- On maximal paths and circuits of graphs
- Embedding large subgraphs into dense graphs
- Title not available (Why is that?)
- Perfect matchings and \(K_4^3\)-tilings in hypergraphs of large codegree
- Perfect matchings in large uniform hypergraphs with large minimum collective degree
- Matchings in 3-uniform hypergraphs
- Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
- Perfect matchings in 3-uniform hypergraphs with large vertex degree
- 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
- Perfect matchings in 4-uniform hypergraphs
- Title not available (Why is that?)
- Improved bounds for Erdős' matching conjecture
- SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Polynomial-time perfect matchings in dense hypergraphs
- Perfect matchings in uniform hypergraphs with large minimum degree
- Degrees giving independent edges in a hypergraph
- Matchings in hypergraphs of large minimum degree
- Regularity lemmas for hypergraphs and quasi-randomness
Cited In (29)
- A note on perfect matchings in uniform hypergraphs
- On the fractional matching polytope of a hypergraph
- Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
- Improved bound on vertex degree version of Erdős matching conjecture
- Fractional matchings and the Edmonds-Gallai theorem
- Perfect packings in quasirandom hypergraphs. I.
- Nearly perfect matchings in uniform hypergraphs
- Perfect Packings in Quasirandom Hypergraphs II
- The Erdős matching conjecture and concentration inequalities
- Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
- Fractional matchings in hypergraphs
- Perfect matchings in hypergraphs and the Erdős matching conjecture
- On vertex independence number of uniform hypergraphs
- Matching of given sizes in 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
- On the use of optimal fractional matchings for solving the (integer) matching problem
- Minimum number of edges in a hypergraph guaranteeing a perfect fractional matching and the MMS conjecture
- The complexity of perfect matchings and packings in dense hypergraphs
- Title not available (Why is that?)
- Fractional matchings and covers in infinite hypergraphs
- Matching in 3-uniform hypergraphs
- Fractional and integer matchings in uniform hypergraphs
- On certain classes of fractional matchings
- Note on matchings in 3-partite 3-uniform hypergraphs
- Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
- Maximum size of a graph with given fractional matching number
- A note on exact minimum degree threshold for fractional perfect matchings
This page was built for publication: Fractional and integer matchings in uniform hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637239)
