Divisible subdivisions

Divisible subdivisions

-
Michael Krivelevich, Tel Aviv University

We develop sufficient conditions for containment of graph subdivisions with subdivided edges of prescribed divisibility in terms of containment of graph minors. Concretely, we prove that for every graph H of maximum degree at most 3 and for every positive integer q there is a finite f=f(H,q) such that every minor of a complete graph K_f contains a subdivision of H in which every edge is replaced by a path whose length is divisible by q. Both the assumption of maximum degree at most 3 and the requirement of zero residue modulo q for path length are essential. For the case of cycles we can do much better - we show that for f=O(q \log q) every K_f-minor contains a cycle of length divisible by q. This result settles a recent problem of Friedman and Krivelevich  about cycles in (weakly) expanding graphs.

Joint work with Noga Alon.