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