A degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs

DOI10.1137/20M1364825MaRDI QIDQ5071104zbMATH OpenOpenAlexFDO

Authors Candida Bowtell, Joseph Hyde

Publication date 20 April 2022

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

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

zbMATH Keywords

degree sequenceshypergraphsperfect matchingsvertex degree

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The study of asymptotic minimum degree thresholds that force matchings and tilings in hypergraphs is a lively area of research in combinatorics. A key breakthrough in this area was a result of H`{a}n, Person and Schacht who proved that the asymptotic minimum vertex degree threshold for a perfect matching in an $n$-vertex $3$-graph is $$. In this paper we improve on this result, giving a family of degree sequence results, all of which imply the result of H`{a}n, Person and Schacht, and additionally allow one third of the vertices to have degree $$ below this threshold. Furthermore, we show that this result is, in some sense, tight.

Recommendations

• Matchings in 3-uniform hypergraphs of large minimum vertex degree
• Matchings in 3-uniform hypergraphs
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Vertex degree sums for perfect matchings in 3-uniform hypergraphs

Cites work

• \(H\)-factors in dense graphs
• A degree sequence Hajnal-Szemerédi theorem
• A degree sequence Komlós theorem
• A degree sequence version of the Kühn-Osthus tiling theorem
• A Dirac-Type Theorem for 3-Uniform Hypergraphs
• A geometric theory for hypergraph matching
• Critical chromatic number and the complexity of perfect packings in graphs
• Dirac-type questions for hypergraphs -- a survey (or more problems for Endre to solve)
• Embedding spanning bipartite graphs of small bandwidth
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• scientific article; zbMATH DE number 3186565 (Why is no real title available?)
• Matchings in 3-uniform hypergraphs
• On degree sequences forcing the square of a Hamilton cycle
• On Hamilton's ideals
• On perfect matchings in uniform hypergraphs with large minimum vertex degree
• On perfect packings in dense graphs
• Perfect matchings in 3-uniform hypergraphs with large vertex degree
• Recent advances on Dirac-type problems for hypergraphs
• Reducibility among combinatorial problems
• Some Theorems on Abstract Graphs
• The Factorization of Linear Graphs
• Tiling Turán theorems

Cited in

(5)

• On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition
• Minimum vertex degree threshold for \(\mathcal{C}_4^3\)-tiling
• On sufficient conditions for spanning structures in dense graphs
• Pósa-type results for Berge hypergraphs
• A pair degree condition for Hamiltonian cycles in 3-uniform hypergraphs

This page was built for publication: A degree sequence strengthening of the vertex degree threshold for a perfect matching in 3-uniform hypergraphs

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