Akanksha Agrawal, Polynomial Kernel for Interval Vertex Deletion
Given a graph G and an integer k, the Interval Vertex Deletion (IVD) problem asks whether there exists a vertex subset S of size at most k, such that G-S is an interval graph. …
10 events found.
Seminars and Colloquiums
Events
-
-
Zoom ID: 869 4632 6610 (ibsdimag)
-
-
June Huh (허준이), Kazhdan-Lusztig polynomials of graphs and matroids
Room B232 IBS (기초과학연구원)I will introduce Kazhdan-Lusztig polynomials of matroids and survey combinatorial and geometric theories built around them. The focus will be on the conjecture of Gedeon, Proudfoot, and Young that all …
-
Robert Ganian, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
Zoom ID: 869 4632 6610 (ibsdimag)Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study …
-
Yunbum Kook (국윤범), Vertex Sparsification for Edge Connectivity
Room B232 IBS (기초과학연구원)Graph compression or sparsification is a basic information-theoretic and computational question. A major open problem in this research area is whether $(1+\epsilon)$-approximate cut-preserving vertex sparsifiers with size close to the number …
-
Tuan Tran, Anti-concentration phenomena
Room B232 IBS (기초과학연구원)Let $X$ be a real random variable; a typical anti-concentration inequality asserts that (under certain assumptions) if an interval $I$ has small length, then $\mathbb{P}(X\in I)$ is small, regardless the …
-
Gwenaël Joret, Packing and covering balls in graphs excluding a minor
Zoom ID: 869 4632 6610 (ibsdimag)In 2007, Chepoi, Estellon, and Vaxès conjectured that there exists a universal constant $c>0$ such that the following holds for every positive integers $r$ and $k$, and every planar graph …
-
Ben Lund, Point-plane incidence bounds
Room B232 IBS (기초과학연구원)In the early 1980s, Beck proved that, if P is a set of n points in the real plane, and no more than g points of P lie on any …
-
Nick Brettell, On the graph width parameter mim-width
Zoom ID: 869 4632 6610 (ibsdimag)Maximum induced matching width, also known as mim-width, is a width parameter for graphs introduced by Vatshelle in 2012. This parameter can be defined over branch decompositions of a graph …
-
Junguk Lee (이정욱), A quick introduction to stability and NIP: Part I. Basic first order logic
Room B232 IBS (기초과학연구원)I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. …
-
Junguk Lee (이정욱), A quick introduction to stability and NIP: Part II. Stability
Room B232 IBS (기초과학연구원)I give a quick survey on stability and NIP(Non-Independent Property). We first review basic facts on the first order logic and give some historical remarks on classification theory in model theory. …