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

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

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

Junguk Lee (이정욱), A quick introduction to stability and NIP: Part III. NIP

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

Rutger Campbell, Disasters in abstracting combinatorial properties of linear dependence

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

Let E be a finite set and I be a collection of subsets of E. When is there a set of real vectors indexed by E such that I correspond to its linearly independent subsets? In 1935, Whitney introduced matroids using some necessary conditions for this. However, complete characterizations with various techniques are intractable. This remains the case even if it is already known

Sebastian Siebertz, Rank-width meets stability

Zoom ID: 869 4632 6610 (ibsdimag)

Forbidden graph characterizations provide a convenient way of specifying graph classes, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded tree-width, which are characterized as those classes that exclude some planar graph as a minor. Similarly, in model theory, classes of structures are characterized by

Debsoumya Chakraborti, Maximum number of cliques in a graph with bounded maximum degree

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

Generalized extremal problems have been one of the central topics of study in extremal combinatorics throughout the last few decades. One such simple-looking problem, maximizing the number of cliques of a fixed order in a graph with a fixed number of vertices and given maximum degree, was recently resolved by Chase. Settling a conjecture of

Luke Postle, Further progress towards Hadwiger’s conjecture

Zoom ID: 869 4632 6610 (ibsdimag)

In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  Recently, Norin, Song and I showed that every graph with no $K_t$ minor is

Zihan Tan, Towards Tight(er) Bounds for the Excluded Grid Theorem

Zoom ID: 869 4632 6610 (ibsdimag)

We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f$, such that for every integer $g > 0$, every graph of treewidth at least $f(g)$ contains the g×g-grid as a minor. For every

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.