BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.15.20//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20190101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20201111T163000
DTEND;TZID=Asia/Seoul:20201111T173000
DTSTAMP:20260418T193517
CREATED:20200927T024800Z
LAST-MODIFIED:20240707T082419Z
UID:3059-1605112200-1605115800@dimag.ibs.re.kr
SUMMARY:Meike Hatzel\, Constant congestion bramble
DESCRIPTION: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\, Paweł Komosa and Manuel Sorge. \nA 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) \cap V(H_2) \neq \emptyset$ 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. \nBrambles 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 $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0\,\frac{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{\Omega}(k^{1/2})$ and size $\widetilde{O}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{O}$ hide polylogarithmic factors and divisors\, respectively.) \nWe first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(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 $\delta \in (0\,\frac{1}{2}]$\, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2+\delta})$ and size $2^{\widetilde{O}(k^{2\delta})}$.
URL:https://dimag.ibs.re.kr/event/2020-11-11/
LOCATION:Zoom ID: 869 4632 6610 (ibsdimag)
CATEGORIES:Virtual Discrete Math Colloquium
END:VEVENT
END:VCALENDAR