←


←

Menu
Contact | A-Z
img

Monday, November 23, 2026 - 16:00 in V3-201 (Common Room)


Improved lower-bounds for the tree-width and path-width of cubic graphs

A talk in the Probabilistic Combinatorics Research Seminar series by
Lena Volk from TU Darmstadt

Abstract: Cubic graphs can have tree-width linear in their number of vertices, for instance if they are expanders. Yet, it is not known how large the linear factor can be. Every cubic n-vertex graph has path-width, and hence tree-width, at most n/6 + o(n), but the best known lower bounds have remained far below this: random cubic graphs have tree-width at least 0.042n asymptotically almost surely, and the best known lower bound on the path-width is 0.082n, attained by Ramanujan graphs. We prove that there are cubic n-vertex graphs of tree-width at least 0.0698n. Indeed, random lifts of K4 asymptotically almost surely attain this. Further, for uniformly random cubic graphs, we improve the existing lower bound on the tree-width from 0.042n to 0.056n. To this end, we lower bound the tree-width of cubic graphs in terms of their vertex and edge expansion. Moreover, we show that random cubic graphs asymptotically almost surely have path-width at least 0.101n. This is joined work with Irene Heinrich and Pascal Schweitzer.



Back

© 2017–Present Sonderforschungbereich 1283 | Imprint | Privacy Policy