University of Birmingham > Talks@bham > Combinatorics and Probability Seminar > A bandwidth theorem for approximate decompositions

A bandwidth theorem for approximate decompositions

Add to your list(s) Download to your calendar using vCal

  • UserPadraig Condon (University of Birmingham)
  • ClockTuesday 27 February 2018, 15:00-16:00
  • HouseWatson LTA.

If you have a question about this talk, please contact Allan Lo.

We provide a degree condition on a regular $n$-vertex graph $G$ which ensures the existence of a near optimal packing of any family $H$ of bounded degree $n$-vertex $k$-chromatic separable graphs into $G$. In general, this degree condition is best possible.

Here a graph is separable if it has a sublinear separator whose removal results in a set of components of sublinear size. Equivalently, the separability condition can be replaced by that of having small bandwidth. Thus our result can be viewed as a version of the bandwidth theorem of B\”ottcher, Schacht and Taraz in the setting of approximate decompositions.

In particular, this yields an approximate version of the tree packing conjecture in the setting of regular host graphs $G$ of high degree. Similarly, our result implies approximate versions of the Oberwolfach problem, the Alspach problem and the existence of resolvable designs in the setting of regular host graphs of high degree. This is joint work with Jaehoon Kim, Daniela K\”uhn and Deryk Osthus.

This talk is part of the Combinatorics and Probability Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.