Events Search and Views Navigation

Event Views Navigation

Today

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 of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a …

Continue Reading
Postponed

Nonlinear Algebra in Daejeon (Postponed)

IBS Science Culture Center

Program Summer School @ KAIST (August 4-7, 2020) Discussion Weekend (August 8-9, 2020) Workshop @ IBS Science Culture Center (August 10-13, 2020) Website: https://dimag.ibs.re.kr/home/nonlinear/ Organizing Committee Insong Choe (Konkuk U.) Kangjin Han (DGIST) David Hyeon (SNU) Sijong Kwak (KAIST) Yongnam Lee (KAIST) Anton Leykin (Georgia Tech) Sang-il Oum (IBS & KAIST) Frank Sottile (TAMU)

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 of terminals exist. As a step towards this goal, we initiate the study of a thresholded version of the problem: for a given parameter $c$, …

Continue Reading

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 location of $I$. Inequalities of this type have found powerful applications in many branches of mathematics. In this talk we will discuss several recent applications …

Continue Reading

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 $G$: Either $G$ contains $k$ vertex-disjoint balls of radius $r$, or there is a subset of vertices of size at most $c k$ meeting all …

Continue Reading
Livestream

2020 Combinatorics Workshop

Zoom ID: 869 4632 6610 (ibsdimag)

Combinatorics Workshop (조합론 학술대회) is the biggest annual conference in combinatorics in Korea. It was firstly held in 2004 by the Yonsei University BK21 Research Group. It has been advised by the committee of discrete mathematics of the Korean Mathematical Society since 2013. The aim of this workshop is to bring active researchers with different …

Continue Reading
Watch Now
Postponed

2020 IBS Workshop on Extremal and Probabilistic Combinatorics (postponed)

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

Date August 24, 2020 - August 28, 2020 Arrival: August 23 Sunday. Departure: August 29, Saturday Venue Institute for Basic Science,  55 Expo-ro, Yuseong-gu, Daejeon, South Korea Invited Speakers Julia Böttcher, London School of Economics Boris Bukh, Carnegie Mellon University Amin Coja-Oghlan, Goethe University David Conlon, Caltech Penny Haxell, University of Waterloo Hao Huang, Emory University Jeff Kahn, Rutgers University …

Continue Reading

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 single line, then there are $\Omega(n(n-g))$ lines that each contain at least 2 points of P. In 2016, I found a generalization of this theorem, …

Continue Reading

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 G, where the width of a vertex partition (X,Y) in G is the size of a maximum induced matching in the bipartite graph induced by …

Continue Reading

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. We review basic properties of stability and NIP. Finally, we aim to give several characterizations of stability and NIP of a given formula in terms of …

Continue Reading
DIMAG on YouTube

We use YouTube Live to broadcast seminar talks live if the speaker agrees.

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.