Constant Congestion Brambles

In this talk I will present a small result we achieved during a workshop in February this year. My coauthors on this are Marcin Pilipczuk, Pawel Komosa and Manuel Sorge.

A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H_1 and H_2 in the bramble either V(H_1) intersects V(H_2) or there is an edge of G with one endpoint in V(H_1) and the second endpoint in V(H_2). The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble.

Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph G equals one plus the treewidth of G. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree n-vertex expander a bramble of order Ω(n^{1/2+δ}) requires size exponential in Ω(n^{2δ}) for any fixed δ \in (0,1/2]. On the other hand, the combination of results of Grohe and Marx, and Chekuri and Chuzhoy shows that a graph of treewidth k admits a bramble of order \widetilde{Ω}(k^{1/2}) and size \widetilde{O}(k^{3/2}). (\widetilde{Ω} and \widetilde{O} hide polylogarithmic factors and divisors, respectively.)

We first sharpen the second bound by proving that every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2}) and congestion 2, i.e., every vertex of G is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every δ \in (0,1/2], every graph G of treewidth at least k contains a bramble of order \widetilde{Ω}(k^{1/2+δ}) and size 2^{\widetilde{O}(k^{2δ})}.

The seminar will be broadcasting via Zoom through the following link:

Join Zoom Meeting

https://upr-si.zoom.us/j/85914318577?pwd=cnFJcmg2ZEZkbFhpeG1VYk0veHp2Zz09

If you missed it, you can watch the lecture via the following link:

https://upr-si.zoom.us/rec/share/2Yot036CPpC3-D6eJGZ8v4wCw3Z1bDevLFd5IiNx7YacZN2T3B1lAamp-L8FfZF2.lnUGGgaRxrr5zNgN

Passcode: K2@ZVpEY