Perfect matchings in hypergraphs and the Erdős matching conjecture

DOI10.1137/16M1056079MaRDI QIDQ3178439zbMATH OpenOpenAlexWikidataFDO

Authors Jie Han

Publication date 13 July 2016

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.07177

zbMATH Keywords

Erdős matching conjecturehypergraphperfect matching

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove a new upper bound for the minimum $d$-degree threshold for perfect matchings in $k$-uniform hypergraphs when $d<k/2$. As a consequence, this determines exact values of the threshold when $0.42kled<k/2$ or when $(k,d)=(12,5)$ or $(17,7)$. Our approach is to give an upper bound on the ErdH{o}s Matching Conjecture and convert the result to the minimum $d$-degree setting by an approach of K"uhn, Osthus and Townsend. To obtain exact thresholds, we also apply a result of Treglown and Zhao.

Recommendations

• A note on perfect matchings in uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree

Cites work

• A note on perfect matchings in uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Embedding large subgraphs into dense graphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs. II
• scientific article; zbMATH DE number 4029608 (Why is no real title available?)
• scientific article; zbMATH DE number 3221072 (Why is no real title available?)
• Improved bounds for Erdős' matching conjecture
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Matchings in 3-uniform hypergraphs
• Matchings in hypergraphs of large minimum degree
• Near perfect matchings in \(k\)-uniform hypergraphs
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• On Erdős' extremal problem on matchings in hypergraphs
• On maximal paths and circuits of graphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings and K₄^3-tilings in hypergraphs of large codegree
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Perfect matchings in 4-uniform hypergraphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• Perfect matchings in uniform hypergraphs with large minimum degree
• Recent advances on Dirac-type problems for hypergraphs
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• The size of a hypergraph and its matching number
• Tight co-degree condition for perfect matchings in 4-graphs

Cited in

(30)

• Perfect matchings and ears in elementary bipartite graphs
• 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
• Matching in 3-uniform hypergraphs
• Beyond the Erdős matching conjecture
• A note on exact minimum degree threshold for fractional perfect matchings
• The Erdős matching conjecture and concentration inequalities
• The complexity of perfect matchings and packings in dense hypergraphs
• Vertex degree sums for matchings in 3-uniform hypergraphs
• Erdős matching conjecture for almost perfect matchings
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• Touching perfect matchings and halving lines
• On perfect matchings and tilings in uniform hypergraphs
• Matching of given sizes in hypergraphs
• The proof of the Perepechko’s conjecture concerning near-perfect matchings on Cm x Pn cylinders of odd order
• Minimum vertex degree thresholds for tiling complete 3-partite 3-graphs
• The number of perfect matchings in a hypercube
• Perfect matchings in highly cyclically connected regular graphs
• The matching polynomials of hypergraphs and weighted hypergraphs
• Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
• Improved bound on vertex degree version of Erdős matching conjecture
• Vertex degree sums for matchings in 3-uniform hypergraphs
• Perfect matching and polymatroids
• On the Keevash-Knox-Mycroft conjecture
• Vertex degree sums for perfect matchings in 3-uniform hypergraphs
• Matchings in multipartite hypergraphs
• A note on perfect matchings in uniform hypergraphs

This page was built for publication: Perfect matchings in hypergraphs and the Erdős matching conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3178439)