Crux, space constraints and subdivisions
Preprint
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 example of such a connection, 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(\sqrt{d})}$-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 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. 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 unions of graphs having crux size linear in $d$; (2) 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; (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.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Ramsey numbers of cycles versus general graphsForum of Mathematics, Sigma, 2023
- Clique immersion in graphs without a fixed bipartite graphJournal of Combinatorial Theory, Series B, 2022
- Subdivisions of a large clique in -free graphsJournal of Combinatorial Theory, Series B, 2015
- Hamiltonian degree sequences in digraphsJournal of Combinatorial Theory, Series B, 2010
- Minors in Expanding GraphsGeometric and Functional Analysis, 2009
- The order of the largest complete minor in a random graphRandom Structures & Algorithms, 2008
- Topological Minors in Graphs of Large GirthJournal of Combinatorial Theory, Series B, 2002
- Topological Cliques in GraphsCombinatorics, Probability and Computing, 1994
- Topological cliques of random graphsJournal of Combinatorial Theory, Series B, 1981
- Hadwiger's Conjecture is True for Almost Every GraphEuropean Journal of Combinatorics, 1980