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.
Type: | Article |
---|---|
Title: | A general approach to transversal versions of Dirac-type theorems |
Open access status: | An open access version is available from UCL Discovery |
DOI: | 10.1112/blms.12896 |
Publisher version: | https://doi.org/10.1112/blms.12896 |
Language: | English |
Additional information: | © 2023 The Authors. Bulletin of the London Mathematical Society is copyright © London Mathematical Society. This is an open access article under the terms of the Creative Commons Attribution License, which permits use, distribution and reproduction in any medium, provided the original work is properly cited. |
Keywords: | Science & Technology, Physical Sciences, Mathematics, LOOSE HAMILTON CYCLES, DEGREE THRESHOLD, MINIMUM |
UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10181849 |
Archive Staff Only
![]() |
View Item |