Back to Search Start Over

A general approach to transversal versions of Dirac‐type theorems.

Authors :
Gupta, Pranshu
Hamann, Fabian
Müyesser, Alp
Parczyk, Olaf
Sgueglia, Amedeo
Source :
Bulletin of the London Mathematical Society. Dec2023, Vol. 55 Issue 6, p2817-2839. 23p.
Publication Year :
2023

Abstract

Given a collection of hypergraphs H=(H1,...,Hm)${{\bf H}}=(H_1, \ldots , H_m)$ with the same vertex set, an m$m$‐edge graph F⊂∪i∈[m]Hi$F\subset \cup _{i\in [m]}H_i$ is a transversal if there is a bijection ϕ:E(F)→[m]$\phi :E(F)\rightarrow [m]$ such that e∈E(Hϕ(e))$e\in E(H_{\phi (e)})$ for each e∈E(F)$e\in E(F)$. How large does the minimum degree of each Hi$H_i$ need to be so that H${{\bf H}}$ necessarily contains a copy of F$F$ that is a transversal? Each Hi$H_i$ in the collection could be the same hypergraph, hence the minimum degree of each Hi$H_i$ needs to be large enough to ensure that F⊆Hi$F\subseteq H_i$. Since its general introduction by Joos and Kim (Bull. Lond. Math. Soc. 52 (2020) 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$rn$ graphs on an n$n$‐vertex set, each with minimum degree at least (r/(r+1)+o(1))n$(r/(r+1)+o(1))n$, contains a transversal copy of the r$r$th power of a Hamilton cycle. This can be viewed as a rainbow version of the Pósa–Seymour conjecture. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
00246093
Volume :
55
Issue :
6
Database :
Academic Search Index
Journal :
Bulletin of the London Mathematical Society
Publication Type :
Academic Journal
Accession number :
174107270
Full Text :
https://doi.org/10.1112/blms.12896