On Perfect Subdivision Tilings

EUROCOMB’23

Abstract
For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\delta_{sub}(n, H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of $\delta_{sub}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is a constant $1 < \xi^*(H)\leq 2$ such that $\delta_{sub}(n, H) = \left(1 - \frac{1}{\xi^*(H)} + o(1) \right)n$ if $H$ has a bipartite subdivision with two parts having different parities. Otherwise, the threshold may depend on the parity of $n.$

Pages:
708–716
References

Noga Alon. Transversal numbers of uniform hypergraphs. Graphs and Combinatorics, 6(1):1-4, 1990.
https://doi.org/10.1007/BF01787474

Noga Alon and Raphael Yuster. H-factors in dense graphs. Journal of Combinatorial Theory, Series B, 66(2):269-282, 1996.
https://doi.org/10.1006/jctb.1996.0020

B Andrásfal. Graphentheoretische extremalprobleme. Acta Mathematica Hungarica, 15(3-4):413-438, 1964.
https://doi.org/10.1007/BF01897150

Vladimir I Arnautov. Estimation of the exterior stability number of a graph by means of the minimal degree of the vertices. Prikl. Mat. i Programmirovanie, 11(3-8):126, 1974.

József Balogh, Lina Li, and Andrew Treglown. Tilings in vertex ordered graphs. Journal of Combinatorial Theory, Series B, 155:171-201, 2022.
https://doi.org/10.1016/j.jctb.2022.02.006

Julia Böttcher, Mathias Schacht, and Anusch Taraz. Proof of the bandwidth conjecture of bollobás and komlós. Mathematische Annalen, 343(1):175-205, 2009.
https://doi.org/10.1007/s00208-008-0268-6

Paul Erdős and Miklós Simonovits. A limit theorem in graph theory. In Studia Sci. Math. Hung. Citeseer, 1965.

Paul Erdős and Miklós Simonovits. Supersaturated graphs and hypergraphs. Combinatorica, 3(2):181-192, 1983.
https://doi.org/10.1007/BF02579292

Paul Erdös and Arthur H Stone. On the structure of linear graphs. Bulletin of the American Mathematical Society, 52(12):1087-1091, 1946.
https://doi.org/10.1090/S0002-9904-1946-08715-7

Andrea Freschi and Andrew Treglown. Dirac-type results for tilings and coverings inordered graphs. In Forum of Mathematics, Sigma, volume 10, page e104. Cambridge University Press, 2022.
https://doi.org/10.1017/fms.2022.92

András Hajnal and Endre Szemerédi. Proof of a conjecture of p. erdos. Combinatorial theory and its applications, 2:601-623, 1970.

Jie Han, Patrick Morris, and Andrew Treglown. Tilings in randomly perturbed graphs: Bridging the gap between hajnal-szemerédi and johansson-kahn-vu. Random Structures & Algorithms, 58(3):480-516, 2021.
https://doi.org/10.1002/rsa.20981

Eoin Hurley, Felix Joos, and Richard Lang. Sufficient conditions for perfect mixed tilings. arXiv preprint arXiv:2201.03944, 2022.

Joseph Hyde, Hong Liu, and Andrew Treglown. A degree sequence komlós theorem. SIAM Journal on Discrete Mathematics, 33(4):2041-2061, 2019.
https://doi.org/10.1137/18M1197102

GOH Katona, T Nemetz, and M Simonovits. On a graph-problem of turán in the theory of graphs. Matematikai Lapok, 15:228-238, 1964.

Jaehoon Kim, Daniela Kühn, Deryk Osthus, and Mykhaylo Tyomkyn. A blow-up lemma for approximate decompositions. Transactions of the American Mathematical Society, 371(7):4655-4742, 2019.
https://doi.org/10.1090/tran/7411

János Komlós. Tiling turán theorems. Combinatorica, 20(2):203-218, 2000.
https://doi.org/10.1007/s004930070020

János Komlós, Gábor Sárközy, and Endre Szemerédi. Proof of the alon-yuster conjecture. Discrete Mathematics, 235(1-3):255-269, 2001.
https://doi.org/10.1016/S0012-365X(00)00279-X

János Komlós, Gábor N Sárközy, and Endre Szemerédi. Blow-up lemma. Combinatorica, 17(1):109-123, 1997.
https://doi.org/10.1007/BF01196135

János Komlós, Ali Shokoufandeh, Miklós Simonovits, and Endre Szemerédi. The regularity lemma and its applications in graph theory. Summer school on theoretical aspects of computer science, pages 84-112, 2002.
https://doi.org/10.1007/3-540-45878-6_3

János Komlós and Miklós Simonovits. Szemerédi's regularity lemma and its applications in graph theory. 1996.

Daniela Kühn and Deryk Osthus. Embedding large subgraphs into dense graphs. arXiv preprint arXiv:0901.3541, 2009.
https://doi.org/10.1017/CBO9781107325975.007

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

Daniela Kühn, Deryk Osthus, and Anusch Taraz. Large planar subgraphs in dense graphs. Journal of Combinatorial Theory, Series B, 95(2):263-282, 2005.
https://doi.org/10.1016/j.jctb.2005.04.004

Hyunwoo Lee. On perfect subdivision tilings. arXiv preprint arXiv:2302.09393, 2023.

Allan Lo and Klas Markström. f -factors in hypergraphs via absorption. Graphs and Combinatorics, 31(3):679-712, 2015.
https://doi.org/10.1007/s00373-014-1410-8

Charles Payan. Sur le nombre d'absorption d'un graphe simple. 1975.

Vojtěch Rödl, Andrzej Ruciński, and Endre Szemerédi. A dirac-type theorem for 3-uniform hypergraphs. Combinatorics, Probability and Computing, 15(1-2):229-251, 2006.
https://doi.org/10.1017/S0963548305007042

Vojtěch Rödl and Mathias Schacht. Regularity lemmas for graphs. In Fete of combinatorics and computer science, pages 287-325. Springer, 2010.
https://doi.org/10.1007/978-3-642-13580-4_11

Ali Shokoufandeh and Yi Zhao. Proof of a tiling conjecture of komlós. Random Structures & Algorithms, 23(2):180-205, 2003.
https://doi.org/10.1002/rsa.10091

Endre Szemerédi. Regular partitions of graphs. Technical report, Stanford Univ Calif Dept of Computer Science, 1975.

Metrics

0

Views

0

PDF views