### Linda Cook, Two results on graphs with holes of restricted lengths

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

We call an induced cycle of length at least four a hole. The parity of a hole is the parity of its length. Forbidding holes of certain types in a graph has deep structural implications. In 2006, Chudnovksy, Seymour, Robertson, and Thomas famously proved that a graph is perfect if and only if it does not contain

### Petr Hliněný, Twin-width is linear in the poset width

Zoom ID: 934 3222 0374 (ibsdimag)

Twin-width is a new parameter informally measuring how diverse are the neighbourhoods of the graph vertices, and it extends also to other binary relational structures, e.g. to digraphs and posets. It was introduced quite recently, in 2020 by Bonnet, Kim, Thomassé, and Watrigant. One of the core results of these authors is that FO model checking on graph classes of

### Eun Jung Kim (김은정), A Constant-factor Approximation for Weighted Bond Cover

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

The Weighted $\mathcal F$-Vertex Deletion for a class $\mathcal F$ of graphs asks, given a weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in\mathcal F$. The case when $\mathcal F$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal ### Cheolwon Heo (허철원), Representations of even-cycle matroids Room B232 IBS (기초과학연구원) A signed graph is a pair$(G,\Sigma)$where$G$is a graph and$\Sigma$is a subset of edges of$G$. A cycle$C$of$G$is a subset of edges of$G$such that every vertex of the subgraph of$G$induced by$C$has an even degree. We say that$C$is even ### Dabeen Lee (이다빈), 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 ### Kevin Hendrey, Extremal functions for sparse minors Room B232 IBS (기초과학연구원) 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) ### Péter Pál Pach, The Alon-Jaeger-Tarsi conjecture via group ring identities Zoom ID: 934 3222 0374 (ibsdimag) The Alon-Jaeger-Tarsi conjecture states that for any finite field$\mathbb{F}$of size at least 4 and any nonsingular matrix$M$over$\mathbb{F}$there exists a vector$x$such that neither$x$nor$Mx$has a 0 component. In joint work with János Nagy we proved this conjecture when the size of the field is sufficiently ### Eunjin Oh (오은진), Feedback Vertex Set on Geometric Intersection Graphs Room B232 IBS (기초과학연구원) 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 ### Paul Seymour, Polynomial bounds for chromatic number Zoom ID: 934 3222 0374 (ibsdimag) The Gyárfás-Sumner conjecture says that for every forest$H$, there is a function$f$such that the chromatic number$\chi(G)$is at most$f(\omega(G))$for every$H$-free graph$G$("$H$-free" means with no induced subgraph isomorphic to$H$, and$\omega(G)$is the size of the largest clique of$G$). This well-known conjecture has been proved only for a ### Joonkyung Lee (이준경), Majority dynamics on sparse random graphs Room B232 IBS (기초과학연구원) 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ős-Rényi random graph$G(n,p)$, the random initial$\pm 1$-assignment converges to a$99\%\$-agreement with high

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209