Crux, space constraints and subdivisions

arXiv2207.06653MaRDI QIDQ6404944FDOQ6404944

Authors: Seonghyuk Im, Jaehoon Kim, Younjin Kim, Hong Liu 

Publication date: 14 July 2022

Abstract: For a given graph $H$, its subdivisions carry the same topological structure. The existence of $H$-subdivisions within a graph $G$ has deep connections with topological, structural and extremal properties of $G$. One prominent examples of such connections, due to Bollob'{a}s and Thomason and independently Koml'os and Szemer'edi, asserts that the average degree of $G$ being $d$ ensures a $K_{Omega(sqrtd)}$-subdivision in $G$. Although this square-root bound is best possible, various results showed that much larger clique subdivisions can be found in a graph from 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. This reveals the unifying cause underpinning all those improvements for various classes of graphs studied. Roughly speaking, when embedding subdivisions, natural space constraints arise; and such space constraints can be measured via crux. 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 (1) a characterisation of extremal graphs for which the square-root bound above is tight: they are essentially disjoint union of graphs each of which has the crux size linear in $d$; (2) a unifying approach to find a clique subdivision of almost optimal size in graphs which does not contain a fixed bipartite graph as a subgraph; (3) 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.

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

This page was built for publication: Crux, space constraints and subdivisions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404944)