Gupta, Pranshu; Hamann, Fabian; Muyesser, Alp; Parczyk, Olaf; Sgueglia, Amedeo; (2023) A general approach to transversal versions of Dirac-type theorems. Bulletin of the London Mathematical Society 10.1112/blms.12896. (In press).

Preview

PDF A general approach to transversal versions.pdf - Published Version Download (379kB) | Preview

Abstract

Given a collection of hypergraphs (Formula presented.) with the same vertex set, an (Formula presented.) -edge graph (Formula presented.) is a transversal if there is a bijection (Formula presented.) such that (Formula presented.) for each (Formula presented.). How large does the minimum degree of each (Formula presented.) need to be so that (Formula presented.) necessarily contains a copy of (Formula presented.) that is a transversal? Each (Formula presented.) in the collection could be the same hypergraph, hence the minimum degree of each (Formula presented.) needs to be large enough to ensure that (Formula presented.). 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 (Formula presented.) graphs on an (Formula presented.) -vertex set, each with minimum degree at least (Formula presented.), contains a transversal copy of the (Formula presented.) th power of a Hamilton cycle. This can be viewed as a rainbow version of the Pósa–Seymour conjecture.

Download activity - last month

Export as XMLCSVJSON

Download activity - last 12 months

Export as CSVXMLJSON

Downloads by country - last 12 months

Export as XMLCSVJSON

Archive Staff Only

View Item