A general approach to transversal versions of Dirac‐type theorems

DOI10.1112/BLMS.12896MaRDI QIDQ6138997zbMATH OpenOpenAlexWikidataFDO

Authors Pranshu Gupta, Fabian Hamann, Alp Müyesser, O. Parczyk

Publication date 18 December 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Hypergraphs (05C65) Transversal (matching) theory (05D15) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Given a collection of hypergraphs $extbfH=(H_1,ldots,H_m)$ with the same vertex set, an $m$-edge graph $Fsubsetcu{p}_{iin[m]}{H}_i$ is a transversal if there is a bijection $phi:E(F)o[m]$ such that $einE(H_{phi(e)})$ for each $einE(F)$. How large does the minimum degree of each $H_i$ need to be so that $extbfH$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $Fsubseteq{H}_i$. Since its general introduction by Joos and Kim [Bull. Lond. Math. Soc., 2020, 52(3):498-504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the P'osa-Seymour conjecture.

Recommendations

• On a rainbow version of Dirac's theorem
• From one to many rainbow Hamiltonian cycles
• Transversal Hamilton cycle in hypergraph systems

Cites work

• A rainbow version of Mantel's theorem
• An approximate Dirac-type theorem for k-uniform hypergraphs
• Dirac-type conditions for Hamiltonian paths and cycles in 3-uniform hypergraphs
• Dirac-type results for loose Hamilton cycles in uniform hypergraphs
• How to avoid using the regularity Lemma: Pósa's conjecture revisited
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• Loose Hamiltonian cycles forced by large (k-2)-degree-approximate version
• Minimum codegree threshold for Hamilton \(\ell\)-cycles in \(k\)-uniform hypergraphs
• Minimum degree thresholds for Hamilton \((k/2)\)-cycles in \(k\)-uniform hypergraphs
• Minimum vertex degree condition for tight Hamiltonian cycles in 3‐uniform hypergraphs
• Minimum vertex degree threshold for loose Hamilton cycles in 3-uniform hypergraphs
• On a rainbow version of Dirac's theorem
• On the square of a Hamiltonian cycle in dense graphs
• Proof of the bandwidth conjecture of Bollobás and Komlós
• Proof of the Seymour conjecture for large graphs
• Rainbow matchings for 3-uniform hypergraphs
• Rainbow pancyclicity in graph systems
• Rainbow perfect matchings for 4-uniform hypergraphs
• The minimum degree threshold for perfect graph packings
• Transversal factors and spanning trees

Cited in

(13)

• Minimum-degree conditions for rainbow triangles
• Optimal spread for spanning subgraphs of Dirac hypergraphs
• Transversal Hamilton cycle in hypergraph systems
• Spectral radius and rainbow k-factors of graphs
• Transversals via regularity
• Counting spanning subgraphs in dense hypergraphs
• Transversals in a collection of stars or generic trees
• Stability of transversal Hamilton cycles and paths
• Transversal panconnectedness in graph collections
• Directed graphs without rainbow triangles
• Universality for transversal Hamilton cycles
• Transversal Hamilton paths and cycles
• Transversal Hamilton cycle in the hypergraph system

This page was built for publication: A general approach to transversal versions of Dirac‐type theorems

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