A general approach to transversal versions of Dirac-type theorems

EUROCOMB’23

Pranshu Gupta Fabian Hamann Alp Müyesser Olaf Parczyk Amedeo Sgueglia

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-072

PDF
Abstract
Given a collection of hypergraphs $\textbf{\textup{H}}=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\textbf{\textup{H}}$ 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 $F\subseteq 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ósa-Seymour conjecture.

Pages:
518–525
References

Ron Aharoni, Matt DeVos, Sebastián González Hermosillo de la Maza, Amanda Montejano, and Robert Šámal. A rainbow version of Mantel's theorem. Adv. Comb., pages Paper No. 2, 12, 2020.

Yangyang Cheng, Jie Han, Bin Wang, and Guanghui Wang. Rainbow spanning structures in graph and hypergraph systems. arXiv:2105.10219, 2021.

Yangyang Cheng, Jie Han, Bin Wang, Guanghui Wang, and Donglei Yang. Rainbow Hamilton cycle in hypergraph systems. arXiv:2111.07079, 2021.

Yangyang Cheng, Guanghui Wang, and Yi Zhao. Rainbow pancyclicity in graph systems. Electron. J. Combin., 28(3):Paper No. 3.24, 9, 2021.
https://doi.org/10.37236/9033

Pranshu Gupta, Fabian Hamann, Alp Müyesser, Olaf Parczyk, and Amedeo Sgueglia. A general approach to transversal versions of Dirac-type theorems. arXiv:2209.09289, 2022.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-072

Felix Joos and Jaehoon Kim. On a rainbow version of Dirac's theorem. Bull. Lond. Math. Soc., 52(3):498-504, 2020.
https://doi.org/10.1112/blms.12343

Daniela Kühn and Deryk Osthus. The minimum degree threshold for perfect graph packings. Combinatorica, 29(1):65-107, 2009.
https://doi.org/10.1007/s00493-009-2254-3

Hongliang Lu, Yan Wang, and Xingxing Yu. Co-degree threshold for rainbow perfect matchings in uniform hypergraphs. arXiv:2111.00372, 2021.

Hongliang Lu, Yan Wang, and Xingxing Yu. Rainbow perfect matchings for 4-uniform hypergraphs. SIAM Journal on Discrete Mathematics, 36(3):1645-1662, 2022.
https://doi.org/10.1137/21M1442383

Hongliang Lu, Xingxing Yu, and Xiaofan Yuan. Rainbow matchings for 3-uniform hypergraphs. J. Combin. Theory Ser. A, 183:105489, 2021.
https://doi.org/10.1016/j.jcta.2021.105489

Richard Montgomery, Alp Müyesser, and Yani Pehova. Transversal factors and spanning trees. Adv. Comb., 2022.
https://doi.org/10.19086/aic.2022.3

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Pranshu Gupta, Fabian Hamann, Alp Müyesser, Olaf Parczyk, Amedeo Sgueglia

PDF