Discrete Mathematics Group

Duksang Lee (이덕상), Intertwining connectivities for vertex-minors and pivot-minors
2021-08-10 16:30 - 17:30 (Asia/Seoul) | Room B232, IBS (기초과학연구원)
We show that for pairs (Q,R) and (S,T) of disjoint subsets of vertices of a graph G, if G is sufficiently large, then there exists a vertex v in V(G)−(Q∪R∪S∪T) such that there are two ways to reduce G by a vertex-minor operation while preserving the connectivity between Q and R and the connectivity between S and T. Our theorem implies an analogous theorem of Chen and Whittle (2014) for matroids restricted to binary matroids. Joint work with Sang-il Oum.

Maria Chudnovsky, Induced subgraphs and tree decompositions
2021-07-28 15:00 - 16:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach.
Tree decompositions are closely related to the existence of “laminar collections of separations” in a graph, which roughly means that the separations in the collection “cooperate” with each other, and the pieces that are obtained when the graph is simultaneously decomposed by all the separations in the collection “line up” to form a tree structure. Such collections of separations come up naturally in the context of forbidden minors.
In the case of families where induced subgraphs are excluded, while there are often natural separations, they are usually very far from forming a laminar collection. In what follows we mostly focus on families of graphs of bounded degree. It turns out that due to the bound on the degree, these collections of natural separations can be partitioned into a bounded number of laminar collections. This in turn allows to us obtain a wide variety of structural and algorithmic results, which we will survey in this talk.

Euiwoong Lee (이의웅), The Karger-Stein algorithm is optimal for k-cut
2021-07-27 15:00 - 16:00 | Room B232, IBS (기초과학연구원)
In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. It is easy to see that the elegant randomized contraction algorithm of Karger and Stein for global mincut (k=2) can be naturally extended for general k with the running time of $O(n^{2k-2})$. Using tree packings, Thorup gave a deterministic algorithm that has the same running time.
In this work, we show that for any fixed $kge 2$, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least $Omega(n^{-k})$. This also gives an extremal bound of $O(n^k)$ on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are essentially tight. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most $(2-delta)OPT/k$, using the Sunflower lemma.
Joint work with Anupam Gupta, David G. Harris, and Jason Li.

Semin Yoo (유세민), Combinatorics of Euclidean spaces over finite fields
2021-07-20 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
$q$-analogues of quantities in mathematics involve perturbations of classical quantities using the parameter $q$, and revert to the original quantities when $q$ goes $1$. An important example is the $q$-analogues of binomial coefficients, denoted by $binom{n}{k}_{q}$, which give the number of $k$-dimensional subspaces in $mathbb{F}_{q}^{n}$. When $q$ goes to $1$, this reverts to the binomial coefficients which measure the number of $k$-sets in $left [ n right ]$.
In this talk, we add one more structure in $mathbb{F}_{q}^{n}$, which is the Euclidean quadratic form: $text{dot}_{n}:=x_{1}^{2}+x_{2}^{2}+cdots+x_{n}^{2}$. It turns out that the number of quadratic subspaces of Euclidean type in $(mathbb{F}_{q}^{n},text{dot}_{n})$ can be described as the form of the analogue of binomial coefficients. The main goal of this talk is to define the dot-analogues of the binomial coefficients and to study related combinatorics. No prior knowledge about the theory of quadratic form is required.

Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row
2021-07-14 17:00 - 18:00 | Room B232, IBS (기초과학연구원)
We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain more than k vertex-disjoint odd cycles, where k is any constant. Previously, polynomial-time algorithms were only known for k=0 (bipartite graphs) and for k=1.
We observe that integer linear programs defined by coefficient matrices with bounded subdeterminants and two nonzeros per column can be also solved in strongly polynomial-time, using a reduction to b-matching.
This is joint work with Samuel Fiorini, Gwenaël Joret, and Yelena Yuditsky.

Jaehoon Kim (김재훈), $K_{r+1}$-saturated graphs with small spectral radius
2021-07-13 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $ein E(overline G)$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length 2 in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $nto infty$.

Suil O (오수일), Eigenvalues and [a, b]-factors in regular graphs
2021-07-06 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For positive integers, $r ge 3, h ge 1,$ and $k ge 1$, Bollobás, Saito, and Wormald proved some sufficient conditions for an $h$-edge-connected $r$-regular graph to have a k-factor in 1985. Lu gave an upper bound for the third-largest eigenvalue in a connected $r$-regular graph to have a $k$-factor in 2010. Gu found an upper bound for certain eigenvalues in an $h$-edge-connected $r$-regular graph to have a $k$-factor in 2014. For positive integers $a le b$, an even (or odd) $[a, b]$-factor of a graph $G$ is a spanning subgraph $H$ such that for each vertex $v in V (G)$, $d_H(v)$ is even (or odd) and $a le d_H(v) le b$. In this talk, we provide best upper bounds (in terms of $a, b$, and $r$) for certain eigenvalues (in terms of $a, b, r$, and $h$) in an $h$-edge-connected $r$-regular graph $G$ to guarantee the existence of an even $[a, b]$-factor or an odd $[a, b]$-factor. This result extends the one of Bollobás, Saito, and Wormald, the one of Lu, and the one of Gu.

Florian Gut and Attila Joó, Large vertex-flames in uncountable digraphs
2021-06-30 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
The local connectivity $ kappa_D(r,v) $ from $ r $ to $ v $ is defined to be the maximal number of internally disjoint $rrightarrow v $ paths in $ D $. A spanning subdigraph $ L $ of $ D $ with $ kappa_L(r,v)=kappa_D(r,v) $ for every $ vin V-r $ must have at least $ sum_{vin V-r}kappa_D(r,v) $ edges. It was shown by Lovász that, maybe surprisingly, this lower bound is sharp for every finite digraph. The optimality of an $ L $ can be captured by the following characterization: For every $ vin V-r $ there is a system $ mathcal{P}_v $ of internally disjoint $ rrightarrow v $ paths in $ L $ covering all the ingoing edges of $ v $ in $ L $ such that one can choose from each $ Pin mathcal{P}_v $ either an edge or an internal vertex in such a way that the resulting set meets every $ rrightarrow v $ path of $ D $. We prove that every digraph of size at most $ aleph_1 $ admits such a spanning subdigraph $ L $. The question if this remains true for larger digraphs remains open.

Jeong Ok Choi (최정옥), Invertibility of circulant matrices of arbitrary size
2021-06-29 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In this talk, we present sufficient conditions to guarantee the invertibility of rational circulant matrices with any given size. These sufficient conditions consist of linear combinations in terms of the entries in the first row with integer coefficients. Using these conditions we show the invertibility of some family of circulant matrices with particular forms of integers generated by a primitive element in $mathbb{Z}_p$. Also, the invertibility of circulant 0, 1-matrices can be argued combinatorially by applying sufficient conditions. This is joint work with Youngmi Hur.

Hongseok Yang (양홍석), DAG-symmetries and Symmetry-Preserving Neural Networks
2021-06-22 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The preservation of symmetry is one of the key tools for designing data-efficient neural networks. A representative example is convolutional neural networks (CNNs); they preserve translation symmetries, and this symmetry preservation is often attributed to their success in real-world applications. In the machine-learning community, there is a growing body of work that explores a new type of symmetries, both discrete and continuous, and studies neural networks that preserve those symmetries.
In this talk, I will explain what I call DAG-symmetries and our preliminary results on the shape of neural networks that preserve these symmetries. DAG-symmetries are finite variants of DAG-exchangeability developed by Jung, Lee, Staton, and Yang (2020) in the context of probabilistic symmetries. Using these symmetries, we can express that when a neural network works on, for instance, sets of bipartite graphs whose edges are labelled with reals, the network depends on neither the order of elements in the set nor the identities of vertices of the graphs. I will explain how a group of specific DAG-symmetries is constructed by applying a form of wreath product over a given finite DAG. Then, I will explain what linear layers of neural networks preserving these symmetries should look like.
This is joint work with Dongwoo Oh.

Alan Lew, Representability and boxicity of simplicial complexes
2021-06-16 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology, Roberts defined the boxicity of a graph G to be the minimal k such that G can be written as the intersection of k interval graphs.
A natural higher-dimensional generalization of interval graphs is the class d-representable complexes. These are simplicial complexes that carry the information on the intersection patterns of a family of convex sets in $mathbb R^d$. We define the d-boxicity of a simplicial complex X to be the minimal k such that X can be written as the intersection of k d-representable complexes.
A classical result of Roberts, later rediscovered by Witsenhausen, asserts that the boxicity of a graph with n vertices is at most n/2. Our main result is the following high dimensional extension of Roberts’ theorem: Let X be a simplicial complex on n vertices with minimal non-faces of dimension at most d. Then, the d-boxicity of X is at most $frac{1}{d+1}binom{n}{d}$.
Examples based on Steiner systems show that our result is sharp. The proofs combine geometric and topological ideas.

O-joung Kwon (권오정), Classes of intersection digraphs with good algorithmic properties
2021-06-08 15:00 - 16:00 | Zoom ID: 875 9395 3555 (relay) [CLOSED]
An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_vcap T_v
eq emptyset$ for every vertex $v$. Compared to well-known undirected intersection graphs like interval graphs and permutation graphs, not many algorithmic applications on intersection digraphs have been developed.
Motivated by the successful story on algorithmic applications of intersection graphs using a graph width parameter called mim-width, we introduce its directed analogue called `bi-mim-width’ and prove that various classes of reflexive intersection digraphs have bounded bi-mim-width. In particular, we show that as a natural extension of $H$-graphs, reflexive $H$-digraphs have linear bi-mim-width at most $12|E(H)|$, which extends a bound on the linear mim-width of $H$-graphs [On the Tractability of Optimization Problems on $H$-Graphs. Algorithmica 2020]
For applications, we introduce a novel framework of directed versions of locally checkable problems, that streamlines the definitions and the study of many problems in the literature and facilitates their common algorithmic treatment. We obtain unified polynomial-time algorithms for these problems on digraphs of bounded bi-mim-width, when a branch decomposition is given. Locally checkable problems include Kernel, Dominating Set, and Directed $H$-Homomorphism.
This seminar is a part of the
“Round the World Relay in Combinatorics”
on June 8, 2021.
http://people.maths.ox.ac.uk/scott/relay.htm

2:00 UTC, 11:00 KST Melbourne (Australia) Monash University
David Wood (Monash University), Universality in Minor-Closed Graph Classes
3:00 UTC, 12:00 KST Shanghai (China) Shanghai Center for Mathematical Sciences
Baogang Xu (Nanjing Normal University, China), On coloring of graphs of girth 2l+1 without longer odd holes
4:00 UTC, 13:00 KST Auckland (New Zealand) The University of Auckland
Jeroen Schillewaert (University of Auckland), Constructing highly regular expanders from hyperbolic Coxeter groups
5:00 UTC, 14:00 KST Sydney (Australia) Combinatorial Mathematics Society of Australasia
Gordon Royle (University of Western Australia (UWA)), Real chromatic roots of planar graphs
6:00 UTC, 15:00 KST Daejeon (Korea) IBS Discrete Mathematics Group
O-joung Kwon (Incheon National University and IBS Discrete Mathematics Group), Classes of intersection digraphs with good algorithmic properties
7:00 UTC, 16:00 KST Krakow (Poland) Jagiellonian University
Bartosz Walczak (Jagiellonian), Coloring polygon visibility graphs and their generalizations
8:00 UTC, 17:00 KST Glasgow (UK) University of Glasgow
Heng Guo (University of Edinburgh), A Markov chain approach towards the sampling Lovász local lemma
9:00 UTC, 18:00 KST London (UK) London School of Economics
Annika Heckel (LMU), How does the chromatic number of a random graph vary?
10:00 UTC, 19:00 KST Moscow (Russia) Moscow Institute of Physics and Technology
Noga Alon (Princeton and Tel Aviv)
11:00 UTC, 20:00 KST Budapest (Hungary) Hungarian Academy of Sciences + Eötvös Loránd University
László Lovász (Eotvos University, Budapest)
12:00 UTC, 21:00 KST Bordeaux (France) LaBRI
Carla Groenland (Utrecht University), Universal Graphs and Labelling Schemes
13:00 UTC, 22:00 KST New York (USA) City University of New York + Montclair State University + Hofstra University
Deepak Bal (Montclair State University)
14:00 UTC, 23:00 KST Prague (Czech) Czech Academy of Sciences + Czech Technical University + London School of Economics
Dhruv Mubayi (University of Illinois at Chicago), The feasible region of hypergraphs
15:00 UTC, 00:00 KST Brno (Czech) Masaryk University
James Davies (University of Waterloo), Colouring circle graphs and their generalisations
16:00 UTC, 01:00 KST Oxford (UK) University of Oxford
Jacob Fox (Stanford University), Removal lemmas
17:00 UTC, 02:00 KST Columbus (USA) Ohio State University
Allan Sly (Princeton University)
18:00 UTC, 03:00 KST Rio (Brazil) Instituto de Matemática Pura e Aplicada
Marcelo Campos (IMPA), The singularity probability of a random symmetric matrix is exponentially small
19:00 UTC, 04:00 KST Atlanta (USA) Georgia Institute of Technology
Jim Geelen (University of Waterloo), Homomorphisms and colouring for graphs and binary matroids
20:00 UTC, 05:00 KST Santiago (Chile) Universidad de Chile
David Conlon (Caltech)
21:00 UTC, 06:00 KST Burnaby (Canada) Simon Fraser University
Fan Chung (UCSD), Trees and forests in Green’s functions of a graph
22:00 UTC, 07:00 KST Victoria (Canada) University of Victoria
Andrew Suk (UCSD), Turán-type problems for point-line incidences
23:00 UTC, 08:00 KST Fairbanks (USA) University of Alaska
Ron Gould (Emory), Chorded cycles

Adam Zsolt Wagner, Constructions in combinatorics via neural networks
2021-06-02 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, recent advances in the field of reinforcement learning have led computers to reach superhuman level play in Atari games and Go, purely through self-play. In this talk, I will give a very basic introduction to neural networks and reinforcement learning algorithms. I will also indicate how these methods can be adapted to the “game” of trying to find a counterexample to a mathematical conjecture, and show some examples where this approach was successful.

Doowon Koh (고두원), Mattila-Sjölin type functions: A finite field model
2021-06-01 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Let $mathbb{F}_q$ be a finite field of order $q$ which is a prime power. In the finite field setting, we say that a function $phicolon mathbb{F}_q^dtimes mathbb{F}_q^dto mathbb{F}_q$ is a Mattila-Sjölin type function in $mathbb{F}_q^d$ if for any $Esubset mathbb{F}_q^d$ with $|E|gg q^{frac{d}{2}}$, we have $phi(E, E)=mathbb{F}_q$. The main purpose of this talk is to present the existence of such a function. More precisely, we will construct a concrete function $phi: mathbb{F}_q^4times mathbb{F}_q^4to mathbb{F}_q$ with $qequiv 3 mod{4}$ such that if $Esubset mathbb F_q^4$ with $|E|>q^2,$ then $phi(E,E)=mathbb F_q$. This is a joint work with Daewoong Cheong, Thang Pham, and Chun-Yen Shen.

Dimitrios M. Thilikos, Bounding Obstructions sets: the cases of apices of minor closed classes
2021-05-26 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Given a minor-closed graph class ${cal G}$, the (minor) obstruction of ${cal G}$ is the set of all minor-minimal graphs not in ${cal G}$. Given a non-negative integer $k$, we define the $k$-apex of ${cal A}$ as the class containing every graph $G$ with a set $S$ of vertices whose removal from $G$ gives a graph on ${cal G}$. We prove that every obstruction of the $k$-apex of ${cal G}$ has size bounded by some 4-fold exponential function of $p(k)$ where p is a polynomial function whose degree depends on the size of the minor-obstructions of ${cal G}$. This bound drops to a 2-fold exponential one when ${cal G}$ excludes some apex graph as a minor (i.e., a graph in the $1$-apex of planar graphs).
Joint work with Ignasi Sau and Giannos Stamoulis.

Ben Lund, Limit shape of lattice Zonotopes
2021-05-25 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A convex lattice polytope is the convex hull of a set of integral points. Vershik conjectured the existence of a limit shape for random convex lattice polygons, and three proofs of this conjecture were given in the 1990s by Bárány, by Vershik, and by Sinai. To state this old result more precisely, there is a convex curve $L subset [0,1]^2$ such that the following holds. Let $P$ be a convex lattice polygon chosen uniformly at random from the set of convex lattice polygons with vertices in $[0,N]^2$. Then, for $N$ sufficiently large, $(1/N)P$ will be arbitrarily close (in Hausdorff distance) to $L$ with high probability. It is an open question whether there exists a limit shape for three dimensional polyhedra.
I will discuss this problem and some relatives, as well as joint work with Bárány and Bureaux on the existence of a limit shape for lattice zonotopes in all dimensions.

Benjamin Bumpus, Directed branch-width: A directed analogue of tree-width
2021-05-21 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of tree-width have been proposed. However, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’.
In this talk, I will introduce a new tree-width analogue for digraphs called directed branch-width which allows us to define digraph classes for which many problems (including directed HamiltonPath and MaxCut) become linear-time solvable. Furthermore, via the definition of directed branch-width, I will obtain a generalisation to digraphs of Gurski and Wanke’s characterization of graph classes of bounded tree-width in terms of their line graphs.
This is joint work with Kitty Meeks and William Pettersson.

Pascal Gollin, Enlarging vertex-flames in countable digraphs
2021-05-18 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means that it preserves the local connectivity to each vertex from the root. A structural generalisation of vertex-flames and largeness to infinite digraphs was given by Joó and the analogue of Lovász’ result for countable digraphs was shown.
In this talk, I present a strengthening of this result stating that in every countable rooted digraph each vertex-flame can be extended to a large vertex-flame.
Joint work with Joshua Erde and Attila Joó.

Johannes Carmesin, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings
2021-05-12 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, this problem would be NP-hard. Instead of minimum genus, here we use local planarity — and provide a polynomial algorithm.
Our embedding method is based on Whitney’s trick to use matroids to construct embeddings in the plane. Consequently we obtain a characterisation of the graphs admitting locally planar embeddings in surfaces in terms of a certain matroid being co-graphic.

Mark Siggers, The list switch homomorphism problem for signed graphs
2021-05-11 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other by the iteration of the local action of switching all signs on edges incident to a given vertex, we say that there is a switch homomorphism from a signed graph $G$ to a signed graph $H$ if there is a sign preserving homomorphism from $G’$ to $H$ for some graph $G’$ that is switch equivalent to $G$. By reductions to CSP this problem, and its list version, are known to be either polynomial time solvable or NP-complete, depending on $H$. Recently those signed graphs $H$ for which the switch homomorphism problem is in $P$ were characterised. Such a characterisation is yet unknown for the list version of the problem.
We talk about recent work towards such a characterisation and about how these problems fit in with bigger questions that still remain around the recent CSP dichotomy theorem.

Hong Liu, Sublinear expander and embeddings sparse graphs
2021-05-06 16:15 - 17:15 | Zoom
A notion of sublinear expander has played a central role in the resolutions of a couple of long-standing conjectures in embedding problems in graph theory, including e.g. the odd cycle problem of Erdős and Hajnal that the harmonic sum of odd cycle length in a graph diverges with its chromatic number. I will survey some of these developments.

Raul Lopes, Adapting the Directed Grid Theorem into an FPT Algorithm
2021-05-06 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
The Grid Theorem of Robertson and Seymour [JCTB, 1986] is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. [JCTB, 2001] , and proved by Kawarabayashi and Kreutzer [STOC, 2015]. They showed that there is a function f(k) such that every digraph of directed tree-width at least f(k) contains a cylindrical grid of order k as a butterfly minor and stated that their proof can be turned into an XP algorithm, with parameter k, that either constructs a decomposition of the appropriate width, or finds the claimed large cylindrical grid as a butterfly minor.
In this talk, we present the ideas used in our adaptation of the Directed Grid Theorem into an FPT algorithm. We provide two FPT algorithms with parameter k. The first one either produces an arboreal decomposition of width 3k-2 or finds a haven of order k in a digraph D. The second one uses a bramble B that naturally occurs in digraphs of large directed tree-width to find a well-linked set of order k that is contained in the set of vertices of a path hitting all elements of B. As tools to prove these results, we show how to solve a generalized version of the problem of finding balanced separators for a given set of vertices T in FPT time with parameter |T|.
Joint work with Victor Campos, Ana Karolinna Maia, and Ignasi Sau.

Extremal and Probabilistic Combinatorics (2021 KMS Spring Meeting)
2021-04-30 09:00 - 12:20
A special session “Extremal and Probabilistic Combinatorics” at the 2021 KMS Spring Meeting is organized by Tuan Tran.
URL: https://www.kms.or.kr/meetings/spring2021/
Speakers and Schedule
All talks are on April 30.

[9:00 am] Joonkyung Lee (이준경), University College London

Majority dynamics on sparse random graphs

[9:30 am] Dong Yeap Kang (강동엽), Unversity of Birmingham

The Erdős-Faber-Lovász conjecture and related results

[10:00 am] Jinyoung Park (박진영), IAS

The threshold for the square of a Hamilton cycle

[10:50 am] Debsoumya Chakraborti, IBS Discrete Mathematics Group

Generalized graph saturation

[11:20 am] Jaehoon Kim (김재훈), KAIST

Resolution of the Oberwolfach problem

[11:50 am] Hong Liu, University of Warwick

Sublinear expanders and its applications

Abstracts
Debsoumya Chakraborti, Generalized graph saturation
Graph saturation is one of the oldest areas of investigation in extremal combinatorics. A graph G is called F-saturated if G does not contain a subgraph isomorphic to F, but the addition of any edge creates a copy of F. We resolve one of the most fundamental questions of minimizing the number of cliques of size r in a $K_s$-saturated graph for all sufficiently large numbers of vertices, confirming a conjecture of Kritschgau, Methuku, Tait and Timmons. We further prove a corresponding stability result. This talk will be based on joint work with Po-Shen Loh.
Jaehoon Kim (김재훈), Resolution of the Oberwolfach problem
The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of $K_{2n+1}$ into edge-disjoint copies of a given 2-factor. We show that this can be achieved for all large n. We actually prove a significantly more general result, which allows for decompositions into more general types of factors.
Dong Yeap Kang (강동엽), The Erdős-Faber-Lovász conjecture and related results
A hypergraph is linear if every pair of two distinct edges shares at most one vertex. A longstanding conjecture by Erdős, Faber, and Lovász in 1972, states that the chromatic index of any linear hypergraph on n vertices is at most n.
In this talk, I will present the ideas to prove the conjecture for all large n. This is joint work with Tom Kelly, Daniela Kühn, Abhishek Methuku, and Deryk Osthus.

Joonkyung Lee (이준경), Majority dynamics on sparse random graphs
Majority dynamics on a graph G is a deterministic process such that every vertex updates its {-1,1}-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph G(n,p), the random initial {-1,1}-assignment converges to the unanimity with high probability whenever p>> 1/n.
This conjecture was firstly confirmed for $p>Cn^{-1/2}$ for a large constant C>0 by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, none of them managed to extend it beyond the barrier $p>Cn^{-1/2}$. We prove the conjecture for sparser random graphs G(n,p), where $Dn^{-3/5}log n < p < C n^{-1/2}$ with a large constant D>0.
Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.
Hong Liu, Sublinear expanders and its applications
I will review the history of sublinear expander and present some recent applications, which lead to resolutions of several long-standing problems in sparse graphs embeddings.
Jinyoung Park (박진영), The threshold for the square of a Hamilton cycle
We will talk about a recent result of Jeff Kahn, Bhargav Narayanan, and myself stating that the threshold for the random graph G(n,p) to contain the square of a Hamilton cycle is $1/sqrt n$, resolving a conjecture of Kühn and Osthus from 2012. The proof idea is motivated by the recent work of Frankston and the three aforementioned authors on a conjecture of Talagrand — “a fractional version of Kahn-Kalai expectation threshold conjecture.”

Jungho Ahn (안정호), Well-partitioned chordal graphs with the obstruction set and applications
2021-04-27 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We mainly provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs and give a polynomial-time algorithm that given any graph, either finds an obstruction or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices are in FPT, parameterized by k, on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we introduce some problems that are polynomial-time solvable on split graphs but become NP-complete on well-partitioned chordal graphs.
This is joint work with Lars Jaffke, O-joung Kwon, and Paloma T. Lima.

Reinhard Diestel, Tangles of set separations: a novel clustering method and type recognition in machine learning
2021-04-21 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that typically occur together. They can thereby discover, relate, and structure types: of behaviour, political views, texts, or proteins. Tangles offer a new, quantitative, paradigm for grouping phenomena rather than things. They can identify key phenomena that allow predictions of others. Tangles also offer a new paradigm for clustering in large data sets.
The mathematical theory of tangles has its origins in the theory of graph minors developed by Robertson and Seymour. It has recently been axiomatized in a way that makes it applicable to a wide range of contexts outside mathematics: from clustering in data science to predicting customer behaviour in economics, from DNA sequencing and drug development to text analysis and machine learning.
This very informal talk will not show you the latest intricacies of abstract tangle theory (for which you can find links on the tangle pages of my website), but to win you over to join our drive to develop real tangle applications in areas as indicated above. We have some software to share, but are looking for people to try it out with us on real-world examples!
Here are some introductory pages from a book I am writing on this, which may serve as an extended abstract: https://arxiv.org/abs/2006.01830

Sang-il Oum (엄상일), What is an isotropic system?
2021-04-20 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Bouchet introduced isotropic systems in 1983 unifying some combinatorial features of binary matroids and 4-regular graphs. The concept of isotropic system is a useful tool to study vertex-minors of graphs and yet it is not well known. I will give an introduction to isotropic systems.

István Tomon, Ramsey properties of semilinear graphs
2021-04-14 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
A graph $G$ is semilinear of bounded complexity if the vertices of $G$ are elements of $mathbb{R}^{d}$, and the edges of $G$ are defined by the sign patterns of $t$ linear functions, where $d$ and $t$ are constants. In this talk, I will present several results about the symmetric and asymmetric Ramsey properties of semilinear graphs. Some interesting instances of such graphs are intersection graphs of boxes, interval overlap graphs, and shift graphs, so our results extend several well known theorems about the Ramsey and coloring properties of these geometrically defined graphs.

William Overman, Some Ordered Ramsey Numbers of Graphs on Four Vertices
2021-04-13 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Ordered Ramsey numbers were introduced in 2014 by Conlon, Fox, Lee, and Sudakov. Their results included upper bounds for general graphs and lower bounds showing separation from classical Ramsey numbers. We show the first nontrivial results for ordered Ramsey numbers of specific small graphs. In particular we prove upper bounds for orderings of graphs on four vertices, and determine some numbers exactly using SAT solvers for lower bounds. These results are in the spirit of exact calculations for classical Ramsey numbers and use only elementary combinatorial arguments.
This is joint work with Jeremy Alm, Kayla Coffey, and Carolyn Langhoff.

Michał Pilipczuk, Structural properties of powers of sparse graphs
2021-04-07 17:00 - 18:00 | Zoom ID: 869 4632 6610 (ibsdimag)
For a graph G and an integer d, the dth power of G is the graph $G^d$ on the same vertex set as G where two vertices are considered adjacent if and only if they are at distance at most d in G. Assuming that G is sparse, what can we say about the structure in $G^d$? Certainly $G^d$ can be dense, as the square of a star is a complete graph, but $G^d$ still retains many properties that can be derived from the sparsity of G. We will present some recent results in this spirit, in particular connected to colorings and to the Erdős-Hajnal property, assuming that G is drawn from a fixed class of bounded expansion or from a fixed nowhere dense class. The talk will be based on the recent papers: “Clustering Powers of Sparse Graphs” (with J. Nešetřil, P. Ossona de Mendez, and X. Zhu) and “Erdős-Hajnal properties for powers of sparse graphs” (with M. Briański, P. Micek, and M. Seweryn).

Rutger Campbell, Matroid orientability and representability
2021-04-06 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In this talk we will have a brief introduction to oriented matroids and their relation to real-representability.
