Perfect matchings in hypergraphs and the Erdős matching conjecture

DOI10.1137/16M1056079zbMATH Open1339.05310arXiv1512.07177OpenAlexW2963800089WikidataQ123130618 ScholiaQ123130618MaRDI QIDQ3178439FDOQ3178439

Jie Han

Publication date: 13 July 2016

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

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.

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

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
• Fractional and integer matchings in uniform hypergraphs

zbMATH Keywords

hypergraphperfect matchingErdős matching conjecture

Mathematics Subject Classification ID

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

Cites Work

• On maximal paths and circuits of graphs
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Embedding large subgraphs into dense graphs
• 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
• Fractional and integer matchings in uniform hypergraphs
• 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?)
• Exact minimum degree thresholds for perfect matchings in uniform hypergraphs
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings in 4-uniform hypergraphs
• Title not available (Why is that?)
• On Erdős' extremal problem on matchings in hypergraphs
• Title not available (Why is that?)
• The size of a hypergraph and its matching number
• 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
• Near Perfect Matchings ink-Uniform Hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• Tight co-degree condition for perfect matchings in 4-graphs
• Matchings in hypergraphs of large minimum degree
• Recent advances on Dirac-type problems for hypergraphs
• A note on perfect matchings in uniform hypergraphs
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II

Cited In (26)

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

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)