Discrete Mathematics Group

Chun-Hung Liu (劉俊宏), Asymptotic dimension of minor-closed families and beyond
2020-10-22 10:10 - 11:10 (Asia/Seoul) | Zoom ID:95464969835 (356260)
The asymptotic dimension of metric spaces is an important notion in geometric group theory. The metric spaces considered in this talk are the ones whose underlying spaces are the vertex-sets of (edge-)weighted graphs and whose metrics are the distance functions in weighted graphs. A standard compactness argument shows that it suffices to consider the asymptotic dimension of classes of finite weighted graphs. We prove that the asymptotic dimension of any minor-closed family of weighted graphs, any class of weighted graphs of bounded tree-width, and any class of graphs of bounded layered tree-width are at most 2, 1, and 2, respectively. The first result solves a question of Fujiwara and Papasoglu; the second and third results solve a number of questions of Bonamy, Bousquet, Esperet, Groenland, Pirot and Scott. These bounds for asymptotic dimension are optimal and generalize and improve some results in the literature, including results for Riemannian surfaces and Cayley graphs of groups with a forbidden minor.

Joonkyung Lee (이준경), On graph norms for complex-valued functions
2020-10-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For any given graph $H$, one may define a natural corresponding functional $|.|_H$ for real-valued functions by using homomorphism density. One may also extend this to complex-valued functions, once $H$ is paired with a $2$-edge-colouring $alpha$ to assign conjugates. We say that $H$ is real-norming (resp. complex-norming) if $|.|_H$ (resp. there is $alpha$ such that $|.|_{H,alpha}$) is a norm on the vector space of real-valued (resp. complex-valued) functions. This generalises Gowers norms, a widely used tool in extremal combinatorics to quantify quasirandomness.
We unify these two seemingly different notions of graph norms in real- and complex-valued settings, by proving that $H$ is complex-norming if and only if it is real-norming. Our proof does not explicitly construct a suitable $2$-edge-colouring $alpha$ but obtain its existence and uniqueness, which may be of independent interest.
As an application, we give various example graphs that are not norming. In particular, we show that hypercubes are not norming, which answers the only question appeared in Hatami’s pioneering work in the area that remained untouched. This is joint work with Alexander Sidorenko.

Hong Liu (刘鸿), Cycles and trees in graphs (8/8)
2020-10-15 17:00 - 18:00 | Zoom ID:8628398170 (123450)
This lecture series covers several different techniques on embedding paths/trees/cycles in (pseudo)random graphs/expanders as (induced) subgraphs.

Hong Liu (刘鸿), Cycles and trees in graphs (7/8)
2020-10-14 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Hong Liu (刘鸿), Cycles and trees in graphs (6/8)
2020-10-13 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Hong Liu (刘鸿), Cycles and trees in graphs (5/8)
2020-10-12 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Hong Liu (刘鸿), Cycles and trees in graphs (4/8)
2020-10-08 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Hong Liu (刘鸿), Cycles and trees in graphs (3/8)
2020-10-07 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Hong Liu (刘鸿), Cycles and trees in graphs (2/8)
2020-10-06 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Hong Liu (刘鸿), Cycles and trees in graphs (1/8)
2020-10-05 17:00 - 18:00 | Zoom ID:8628398170 (123450)

Minki Kim (김민기), Complexes of graphs with bounded independence number
2020-09-29 16:30 - 17:30 | 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 graphs with bounded maximum degree. This is joint work with Alan Lew.

Zihan Tan, Towards Tight(er) Bounds for the Excluded Grid Theorem
2020-09-24 10:00 - 11:00 | 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 integer $g > 0$, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that f(g) is at least of order $g^2 log g$. For a long time, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g) = O(g^{98} operatorname{poly log} g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36} operatorname{poly log} g)$, and then to $f(g) = O(g^{19} operatorname{poly log} g)$. In this talk, we present our recent work that further improves this bound to $f(g) = O(g^9 operatorname{poly log} g)$ via a simpler proof. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this talk can lead to even tighter bounds on $f(g)$.
This talk is based on joint work with Julia Chuzhoy.

Jinha Kim (김진하), Collapsibility of Non-Cover Complexes of Graphs
2020-09-22 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $G$ be a graph on the vertex set $V$. A vertex subset $W subset V$ is a cover of $G$ if $V setminus W$ is an independent set of $G$, and $W$ is a non-cover of $G$ if $W$ is not a cover of $G$. The non-cover complex of $G$ is a simplicial complex on $V$ whose faces are non-covers of $G$. Then the non-cover complex of $G$ is the combinatorial Alexander dual of the independence complex of $G$. In this talk, I will show the $(|V(G)|-igamma(G)-1)$-collapsibility of the non-cover complex of a graph $G$ where $igamma(G)$ denotes the independence domination number of $G$ using the minimal exclusion sequence method. This is joint work with Ilkyoo Choi and Boram Park.

Luke Postle, Further progress towards Hadwiger's conjecture
2020-09-17 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $tge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(tsqrt{log t})$ and hence is $O(tsqrt{log t})$-colorable. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(log t)^{beta})$-colorable for every $beta > 1/4$, making the first improvement on the order of magnitude of the $O(tsqrt{log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (log t)^{beta})$-colorable for every $beta > 0$; more specifically, they are $O(t (log log t)^{6})$-colorable.

Debsoumya Chakraborti, Maximum number of cliques in a graph with bounded maximum degree
2020-09-15 16:30 - 17:30 | 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 Kirsch and Radcliffe, we resolve the edge variant of this problem, where the number of edges is fixed instead of the number of vertices. This talk will be based on joint work with Da Qi Chen.

Sebastian Siebertz, Rank-width meets stability
2020-09-10 17:10 - 18:10 | 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 configurations that are forbidden as logical interpretations or transductions. Two notions from classical model theory are (monadic) stability and (monadic) dependence, which correspond to the impossibility of interpreting with first-order logic (after a vertex coloring step) arbitrary long linear orders and all graphs, respectively. Examples of monadically stable classes of graphs are nowhere dense graph classes, and examples of monadically dependent classes are classes of bounded rank-width (or equivalently, bounded clique-width), which can be seen as a dense analog of classes of bounded tree-width.
I will give an overview over recent approaches to combine model theoretic and graph theoretic tools to derive structural and algorithmic results for classes of (finite) graphs. I assume no background from logic.

Rutger Campbell, Disasters in abstracting combinatorial properties of linear dependence
2020-09-08 16:30 - 17:30 | 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 that there is a set of complex vectors indexed by E whose collection of linearly independent subsets corresponds to I.

Junguk Lee (이정욱), A quick introduction to stability and NIP: Part III. NIP
2020-09-01 10:30 - 11:30 | 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 counting types and definability types.

Junguk Lee (이정욱), A quick introduction to stability and NIP: Part II. Stability
2020-08-31 16:15 - 17:15 | Room B232, IBS (기초과학연구원)

Junguk Lee (이정욱), A quick introduction to stability and NIP: Part I. Basic first order logic
2020-08-31 15:00 - 16:00 | Room B232, IBS (기초과학연구원)

Nick Brettell, On the graph width parameter mim-width
2020-08-26 10:30 - 11:30 | 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 edges of G with one endpoint in X and one endpoint in Y. In this talk, I will present a quick overview of mim-width and some key results that highlight why this parameter is of interest from both a theoretical and algorithmic point of view. I will discuss some recent work regarding the boundedness or unboundedness of mim-width for hereditary classes defined by forbidding one or two induced subgraphs, and for generalisations of convex graphs. I will also touch on some interesting applications of this work, in particular for colouring and list-colouring. This is joint work with Jake Horsfield, Andrea Munaro, Giacomo Paesani, and Daniel Paulusma.

Ben Lund, Point-plane incidence bounds
2020-08-25 16:30 - 17:30 | 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, giving a similar lower bound on the number of planes spanned by a set of points in real space. I will discuss this result, along with a number of applications and related open problems.

2020 IBS Workshop on Extremal and Probabilistic Combinatorics (postponed)
2020-08-24 - 2020-08-28 | 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
Alexandr V. Kostochka, University of Illinois at Urbana-Champaign
Michael Krivelevich, Tel-Aviv University
Michał Karoński, Adam Mickiewicz University in Poznań
Anita Liebenau, UNSW Sydney
Hong Liu, University of Warwick
Tomasz Łuczak, Adam Mickiewicz University in Poznań
Richard Montgomery, University of Birmingham
Tobias Müller, Groningen University
Péter Pál Pach, Budapest University of Technology and Economics
Mathias Schacht, University of Hamburg
Asaf Shapira, Tel-Aviv University
Joel Spencer, New York University
Van Vu, Yale University
Yufei Zhao, MIT
This list is incomplete. It is subject to change.

Accommodation
Lotte City Hotel and Hotel ICC are within 700m. Invited speakers will be provided an accommodation at the near-by hotels.
Organizers

Mihyun Kang, Graz University of Technology, Austria.
Jaehoon Kim, KAIST, Korea.
Sang-il Oum, IBS Discrete Mathematics Group, Korea and KAIST, Korea.

2020 Combinatorics Workshop
2020-08-24 | 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 backgrounds to discuss recent and prospective advances in combinatorics and related areas.
Originally, we planned an offline workshop. However, COVID 19 is more spreading and many participants are worried about attending an offline conference. So the schedule and venue are changed as an online workshop with Zoom. I hope that all participants generously understand this sudden change.
Invited Speakers

Sejeong Bang (방세정), Yeungnam University
Ringi Kim (김린기), KAIST
Sangwook Kim (김상욱), Chonnam National University
Jinyoung Park (박진영), Institute for Advanced Study
Jongyook Park (박종육), Kyungpook N. University

Contributed speakers

Byung-Hak Hwang (황병학), Seoul National University
Jaeseong Oh (오재성), Seoul National University
Jun Seok Oh (오준석), Incheon National University
Tuan Tran, Institute for Basic Science (IBS)

More information is available on the website https://cw2020.combinatorics.kr.

Gwenaël Joret, Packing and covering balls in graphs excluding a minor
2020-08-19 16:30 - 17:30 | 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 balls of radius $r$ in $G$. The key aspect of this conjecture is that the constant $c$ does not depend on the radius $r$ of the balls. If we were to allow this dependency, then the statement is known to hold, and in fact it is true in the more general setting of graph classes with bounded expansion (as proved by Dvořák).
In this talk I will present a proof of this conjecture. The result we prove is a bit more general: (1) The conjecture holds for every proper minor-closed class of graphs (with the constant $c$ depending on the class), and (2) we can even focus on any set of balls in the graph we like, there is nothing special about taking all balls of a given radius. In other words, we show that for every proper minor-closed class $C$ of graphs, there exists a constant $c>0$ such that for every graph $G$ in $C$, every set $S$ of balls in $G$, and every positive integer $k$, either there are $k$ vertex-disjoint balls in $S$, or there is a subset of vertices of $G$ of size at most $c k$ meeting all balls in $S$.
Joint work with Nicolas Bousquet, Wouter Cames van Batenburg, Louis
Esperet, William Lochet, Carole Muller, and François Pirot.

Tuan Tran, Anti-concentration phenomena
2020-08-18 16:30 - 17:30 | 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}(Xin 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 of anti-concentration inequalities in extremal combinatorics, as well as random matrix theory. The talk is partially based on joint work with Matthew Kwan and Benny Sudakov.

Yunbum Kook (국윤범), Vertex Sparsification for Edge Connectivity
2020-08-11 16:30 - 17:30 | 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$, find a smaller graph, which we call connectivity-$c$ mimicking network, which preserves connectivity among $k$ terminals exactly up to the value of $c$. We show that contraction-based connectivity-$c$ mimicking networks with $O(kc^4)$ edges exist by (1) introducing an extension of well-linkedness to a thresholded $c$-connectivity setting and (2) leveraging a kernelization result, based on gammoid and the representative sets lemma, to identify `essential edges’ in minimum edge cuts between a partition of terminals. We also develop an algorithm based on expander decomposition, which can find a contraction-based $c$-mimicking network of the optimal size in $m(clog n)^{O(c)}$.
These results lead to the first data structures for answering fully dynamic offline $c$-edge-connectivity queries for $c ge 4$ in polylogarithmic time per query, as well as more efficient algorithms for survivable network design on bounded treewidth graphs.
This is a joint work with Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, and Daniel Vaz.

Nonlinear Algebra in Daejeon (Postponed)
2020-08-10 - 2020-08-13 | 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)

Robert Ganian, Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions
2020-08-05 16:30 - 17:30 | 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 detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this talk is to summarize these recent developments and put them into context. Special attention will be paid to the structural parameter treedepth, and at the end of the talk we will also consider how treedepth can be used to design algorithms for problems beyond ILP.

June Huh (허준이), Kazhdan-Lusztig polynomials of graphs and matroids
2020-08-04 16:30 - 17:30 | 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 zeros of the Kazhdan-Lusztig polynomial of a matroid lie on the negative real axis.
