Crux, space constraints and subdivisions

EUROCOMB’23

Seonghyuk Im Jaehoon Kim Younjin Kim Hong Liu

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

PDF
Abstract
The existence of $H$-subdivisions within a graph $G$ has deep connections with topological, structural and extremal properties of $G$. One prominent example of such a connection, due to Bollobás and Thomason and independently Komlós and Szemerédi, asserts that the average degree of $G$ being $d$ ensures a $K_{\Omega(\sqrt{d})}$-subdivision in $G$. Although this square-root bound is the best possible, various results showed that much larger clique subdivisions can be found in a graph for many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. Our main result gives an asymptotically optimal bound on the size of a largest clique subdivision in a generic graph $G$, which is determined by both its average degree and its crux size. As corollaries, we obtain (i) a characterisation of extremal graphs for which the square-root bound above is tight: they are essentially a disjoint union of graphs each of which has the crux size linear in $d$; (ii) a unifying approach to find a clique subdivision of almost optimal size in graphs which do not contain a fixed bipartite graph as a subgraph; (iii) and that the clique subdivision size in random graphs $G(n,p)$ witnesses a dichotomy: when $p = \omega(n^{-1/2})$, the barrier is the space, while when $p=o( n^{-1/2})$, the bottleneck is the density.

Pages:
607–614
References

Bela Bollobás and Paul A. Catlin. Topological cliques of random graphs. Journal of Combinatorial Theory. Series B, 30(2):224-227, 1981.
https://doi.org/10.1016/0095-8956(81)90066-6

Bela Bollobás, Paul A. Catlin, and Paul Erdos. Hadwiger's conjecture is true for almost every graph. European Journal of Combinatorics, 1(3):195-199, 1980.
https://doi.org/10.1016/S0195-6698(80)80001-1

Béla Bollobás and Andrew Thomason. Proof of a conjecture of Mader, Erdos and Hajnal on topological complete subgraphs. European Journal of Combinatorics, 19(8):883-887, 1998.
https://doi.org/10.1006/eujc.1997.0188

Nikolaos Fountoulakis, Daniela Kühn, and Deryk Osthus. The order of the largest complete minor in a random graph. Random Structures & Algorithms, 33(2):127-141, 2008.
https://doi.org/10.1002/rsa.20215

John Haslegrave, Jie Hu, Jaehoon Kim, Hong Liu, Bingyu Luan, and Guanghui Wang. Crux and long cycles in graphs. SIAM J. Discrete Math., 36(4):2942-2958, 2022.
https://doi.org/10.1137/21M143488X

John Haslegrave, Jaehoon Kim, and Hong Liu. Extremal density for sparse minors and subdivisions. International Mathematics Research Notices, 2021.
https://doi.org/10.1007/978-3-030-83823-2_5

Seonghyuk Im, Jaehoon Kim, Younjin Kim, and Hong Liu. Crux, space constraints and subdivisions. arXiv preprint, arXiv:2207.06653, 2022.

Heinz Adolf Jung. Eine Verallgemeinerung des n-fachen Zusammenhangs für Graphen. Mathematische Annalen, 187:95-103, 1970.
https://doi.org/10.1007/BF01350174

János Komlós and Endre Szemerédi. Topological cliques in graphs. Combinatorics, Probability and Computing, 3(2):247-256, 1994.
https://doi.org/10.1017/S0963548300001140

János Komlós and Endre Szemerédi. Topological cliques in graphs. II. Combinatorics, Probability and Computing, 5(1):79-90, 1996.
https://doi.org/10.1017/S096354830000184X

Michael Krivelevich and Benjamin Sudakov. Minors in expanding graphs. Geometric and Functional Analysis, 19(1):294-331, 2009.
https://doi.org/10.1007/s00039-009-0713-z

Kazimierz Kuratowski. Sur le problème des courbes gauches en topologie. Fundamenta Mathematica, 15:271-283, 1930.
https://doi.org/10.4064/fm-15-1-271-283

Hong Liu and Richard Montgomery. A proof of Mader's conjecture on large clique subdivisions in C4-free graphs. Journal of the London Mathematical Society. Second Series, 95(1):203-222, 2017.
https://doi.org/10.1112/jlms.12019

Wolfgang Mader. Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen, 174:265-268, 1967.
https://doi.org/10.1007/BF01364272

Wolfgang Mader. An extremal problem for subdivisions of K_5^{-}. Journal of Graph Theory, 30(4):261-276, 1999.
https://doi.org/10.1002/(SICI)1097-0118(199904)30:4<261::AID-JGT2>3.0.CO;2-Z

Joseph Samuel Myers. Graphs without large complete minors are quasi-random. Combinatorics, Probability and Computing, 11(6):571-585, 2002.
https://doi.org/10.1017/S096354830200531X

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 Seonghyuk Im, Jaehoon Kim, Younjin Kim, Hong Liu

PDF