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: 869 4632 6610 (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

Donggyu Kim (김동규), 𝝘-graphic delta-matroids and their applications

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

Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $\Gamma$-graphic delta-matroid for an abelian group $\Gamma$, which generalizes a graphic delta-matroid. For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose

Ben Lund, Maximal 3-wise intersecting families

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

A family $\mathcal F$ of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from $\mathcal F$ has a common element, and moreover, no set can be added to $\mathcal F$ while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a

Martin Milanič, Tree Decompositions with Bounded Independence Number

Zoom ID: 869 4632 6610 (ibsdimag)

The independence number of a tree decomposition $\mathcal{T}$ of a graph is the smallest integer $k$ such that each bag of $\mathcal{T}$ induces a subgraph with independence number at most $k$. If a graph $G$ is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can

Jaehoon Kim (김재훈), 2-complexes with unique embeddings in 3-space

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

A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of

Sebastian Wiederrecht, Matching Minors in Bipartite Graphs

Zoom ID: 869 4632 6610 (ibsdimag)

Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya's Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk

Casey Tompkins, Ramsey numbers of Boolean lattices

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

The poset Ramsey number $R(Q_{m},Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2\le R(Q_{2},Q_{n})\le2n+2$. Recently, Lu and Thompson improved the upper bound to $\frac{5}{3}n+2$. In

Tuukka Korhonen, Fast FPT-Approximation of Branchwidth

Zoom ID: 869 4632 6610 (ibsdimag)

Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.