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$,

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

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,

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

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

Minki Kim (김민기), Complexes of graphs with bounded independence number

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

Let $G$ be a graph on $V$ and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose faces are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of $I_n(G)$ for various classes of graphs, focusing on the class of