# 학과 세미나 및 콜로퀴엄

구글 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].

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$.

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.

https://youtube.com/c/ibsdimag

https://youtube.com/c/ibsdimag

####
Room B232, IBS (기초과학연구원)
이산수학
이다빈 (IBS 이산수학그룹)
Mixing sets, submodularity, and chance-constrained optimization

Room B232, IBS (기초과학연구원)

이산수학

A particularly important substructure in modeling joint linear chance-constrained programs with random right-hand sides and finite sample space is the intersection of mixing sets with common binary variables (and possibly a knapsack constraint). In this talk, we first explain basic mixing sets by establishing a strong and previously unrecognized connection to submodularity. In particular, we show that mixing inequalities with binary variables are nothing but the polymatroid inequalities associated with a specific submodular function. This submodularity viewpoint enables us to unify and extend existing results on valid inequalities and convex hulls of the intersection of multiple mixing sets with common binary variables. Then, we study such intersections under an additional linking constraint lower bounding a linear function of the continuous variables. This is motivated from the desire to exploit the information encoded in the knapsack constraint arising in joint linear CCPs via the quantile cuts. We propose a new class of valid inequalities and characterize when this new class along with the mixing inequalities are sufficient to describe the convex hull. This is based on joint work with Fatma Fatma Kılınç-Karzan and Simge Küçükyavuz.

https://youtube.com/c/ibsdimag

https://youtube.com/c/ibsdimag