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

DOI10.1137/20M1364825zbMATH Open1486.05047arXiv2008.12222OpenAlexW3081273614MaRDI QIDQ5071104FDOQ5071104

Authors: Candida Bowtell, Joseph Hyde 

Publication date: 20 April 2022

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

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.

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

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

zbMATH Keywords

perfect matchingshypergraphsvertex degreedegree sequences

Mathematics Subject Classification ID

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

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

Cited In (5)

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

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)