Near perfect matchings in k-uniform hypergraphs

DOI10.1017/S0963548314000613zbMATH Open1371.05228arXiv1404.1136OpenAlexW2967508960MaRDI QIDQ5364253FDOQ5364253

Authors: Jie Han 

Publication date: 4 October 2017

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: Let $H$ be a $k$-uniform hypergraph on $n$ vertices where $n$ is a sufficiently large integer not divisible by $k$. We prove that if the minimum $(k-1)$-degree of $H$ is at least $lfloorn/kfloor$, then $H$ contains a matching with $lfloorn/kfloor$ edges. This confirms a conjecture of R"odl, Ruci'nski and Szemer'edi, who proved that the minimum $(k-1)$-degree $n/k+O(logn)$ suffices. More generally, we show that $H$ contains a matching of size $d$ if its minimum codegree is $d<n/k$, which is also best possible.

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

Recommendations

• Perfect matchings in uniform hypergraphs with large minimum degree
• Nearly perfect matchings in uniform hypergraphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• Perfect matchings in large uniform hypergraphs with large minimum collective degree

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• 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
• Perfect matchings (and Hamilton cycles) in hypergraphs with large degrees
• Perfect matchings in 4-uniform hypergraphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• 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

Cited In (25)

• A note on perfect matchings in uniform hypergraphs
• Improved bound on vertex degree version of Erdős matching conjecture
• Tight minimum degree conditions forcing perfect matchings in uniform hypergraphs
• Nearly perfect matchings in uniform hypergraphs
• Perfect matchings in uniform hypergraphs with large minimum degree
• Perfect matchings in hypergraphs and the Erdős matching conjecture
• On vertex independence number of uniform hypergraphs
• Proof of a tiling conjecture of Komlós
• Matching of given sizes in hypergraphs
• Perfect matchings in large uniform hypergraphs with large minimum collective degree
• \(d\)-matching in 3-uniform hypergraphs
• Perfect matching in \(k\)-partite \(k\)-graphs and 3-uniform HM-bipartite hypergraphs
• \(d\)-matching in \(k\)-uniform hypergraphs
• Co-degree threshold for rainbow perfect matchings in uniform hypergraphs
• On the matching polynomial of hypergraphs
• On a hypergraph matching problem
• Almost perfect matchings in \(k\)-partite \(k\)-graphs
• Matching in 3-uniform hypergraphs
• Matchings in \(k\)-partite \(k\)-uniform hypergraphs
• Some remarks on hypergraph matching and the Füredi–Kahn–Seymour conjecture
• Minimum codegree threshold for \(C_6^3\)-factors in 3-uniform hypergraphs
• Near Perfect Matchings in ${k}$-Uniform Hypergraphs II
• Decision problem for perfect matchings in dense \(k\)-uniform hypergraphs
• On matchings in hypergraphs
• Title not available (Why is that?)

This page was built for publication: Near perfect matchings in \(k\)-uniform hypergraphs

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