***********************************
* Princeton Discrete Math Seminar *
***********************************
Speaker: Michael Krivelevich, Tel Aviv University
Thursday 18th February, 3:00 via Zoom.
Title: Divisible subdivisions
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.
----------------------------------
Next week: Zdenek Dvorak
Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)