Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-21T22:51:06.685Z Has data issue: false hasContentIssue false

Transversal Ck-factors in subgraphs of the balanced blow-up of Ck

Published online by Cambridge University Press:  30 May 2022

Beka Ergemlidze
Affiliation:
Department of Mathematics and Statistics, University of South Florida, Tampa, FL33620, USA.
Theodore Molla*
Affiliation:
Department of Mathematics and Statistics, University of South Florida, Tampa, FL33620, USA.
*
*Corresponding author. Email: [email protected]

Abstract

For a subgraph $G$ of the blow-up of a graph $F$ , we let $\delta ^*(G)$ be the smallest minimum degree over all of the bipartite subgraphs of $G$ induced by pairs of parts that correspond to edges of $F$ . Johansson proved that if $G$ is a spanning subgraph of the blow-up of $C_3$ with parts of size $n$ and $\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$ , then $G$ contains $n$ vertex disjoint triangles, and presented the following conjecture of Häggkvist. If $G$ is a spanning subgraph of the blow-up of $C_k$ with parts of size $n$ and $\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$ , then $G$ contains $n$ vertex disjoint copies of $C_k$ such that each $C_k$ intersects each of the $k$ parts exactly once. A similar conjecture was also made by Fischer and the case $k=3$ was proved for large $n$ by Magyar and Martin.

In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of $G$ to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson’s result asymptotically.

MSC classification

Type
Paper
Copyright
© The Author(s), 2022. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Research supported in part by NSF Grant DMS 1800761.

References

Catlin, P. (1980) On the Hajnal-Szemerédi theorem on disjoint cliques. Util. Math 17 163177.Google Scholar
Ergemlidze, B. and Molla, T. (2021) Transversal Ck-factors in subgraphs of the balanced blow-up of Ck , arXiv:2103.09745.Google Scholar
Fischer, E. (1999) Variants of the Hajnal-Szemerédi Theorem. J. Graph Theory 31 275282.3.0.CO;2-F>CrossRefGoogle Scholar
Johansson, R. (2000) Triangle-factors in a balanced blown-up triangle. Discrete Math 211(1-3) 249254.CrossRefGoogle Scholar
Keevash, P. and Mycroft, R. (2014) A geometric theory for hypergraph matching. Mem. Am. Math. Soc 233(1098).Google Scholar
Keevash, P. and Mycroft, R. (2015) A multipartite Hajnal-Szemerédi Theorem. J. Combin. Theory Ser. B 114(1098) 187236.CrossRefGoogle Scholar
Lo, A. and Markström, K. (2015) $F$ -factors in hypergraphs via absorption. Graphs Combin 31(3) 679712.CrossRefGoogle Scholar
Lo, A. and Markström, K. (2013) A multipartite version of the Hajnal-Szemer edi theorem for graph and hypergraphs. Combin. Probab. Comput 22 97111.CrossRefGoogle Scholar
Magyar, C. and Martin, R. (2002) Tripartite version of the Corrádi-Hajnal theorem. Discrete Math 254 289308.CrossRefGoogle Scholar
Martin, R. and Szemerédi, E. (2008) Quadripartite version of the Hajnal-Szemerédi theorem. Discrete Math 308 43374360.CrossRefGoogle Scholar
Rödl, V., Ruciński, A. and Szemerédi, E. (2006) A Dirac-type theorem for 3-uniform hypergraphs. Combin. Probab. Comput 15(1-2) 229251.CrossRefGoogle Scholar