# 학과 세미나 및 콜로퀴엄

2021-09
Sun Mon Tue Wed Thu Fri Sat
1 2 3 4
5 6 7 1 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 1 29 30
2021-10
Sun Mon Tue Wed Thu Fri Sat
1 2
3 4 5 1 6 7 8 9
10 11 12 1 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

구글 Calendar나 iPhone 등에서 구독하면 세미나 시작 전에 알림을 받을 수 있습니다.

I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time $2^{O(\sqrt{k})}(n + m)$, where $n$ and $m$ denote the numbers of vertices and edges, respectively. This improves the $2^{O(\sqrt{k}\log k)}(n + m)$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017].
Host: Sang-il Oum     영어     2021-09-22 08:25:36
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O'Donnell, Tamuz and Tan conjectured that, in the Erd\H{o}s--R\'enyi random graph $G(n,p)$, the random initial $\pm 1$-assignment converges to a $99\%$-agreement with high probability whenever $p=\omega(1/n)$. This conjecture was first confirmed for $p\geq\lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< \lambda n^{-1/2}$. We break this $\Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $\lambda' n^{-3/5}\log n \leq p \leq \lambda n^{-1/2}$ with a large constant $\lambda'>0$.
Host: Sang-il Oum     영어     2021-09-22 08:28:45
The extremal function $c(H)$ of a graph $H$ is the supremum of densities of graphs not containing $H$ as a minor, where the density of a graph is the ratio of the number of edges to the number of vertices. Myers and Thomason (2005), Norin, Reed, Thomason and Wood (2020), and Thomason and Wales (2019) determined the asymptotic behaviour of $c(H)$ for all polynomially dense graphs $H$, as well as almost all graphs of constant density. We explore the asymptotic behavior of the extremal function in the regime not covered by the above results, where in addition to having constant density the graph $H$ is in a graph class admitting strongly sublinear separators. We establish asymptotically tight bounds in many cases. For example, we prove that for every planar graph $H$, $c(H) = (1+o(1))\max (v(H)/2, v(H)-\alpha(H)),$ extending recent results of Haslegrave, Kim and Liu (2020). Joint work with Sergey Norin and David R. Wood.