Paul Seymour, Polynomial bounds for chromatic number
2021-10-08 10:00 - 11:00 (Asia/Seoul) | Zoom ID: 869 4632 6610 (ibsdimag)
The Gyárfás-Sumner conjecture says that for every forest $H$, there is a function $f$ such that the chromatic number $chi(G)$ is at most $f(omega(G))$ for every $H$-free graph $G$ (“$H$-free” means with no induced subgraph isomorphic to $H$, and $omega(G)$ is the size of the largest clique of $G$). This well-known conjecture has been proved only for a few types of forest.
Nevertheless, there is a much stronger conjecture, due to Esperet: that for every forest $H$, there is a polynomial function $f$ as above. As one might expect, this has been proved for even fewer types of forest; and the smallest tree $H$ for which Esperet’s conjecture is not known is the five-vertex path $P_5$.
A third notorious conjecture is the Erdős-Hajnal conjecture, that for every graph $H$, there exists $c>0$ such that $alpha(G)omega(G)ge |G|^c$ for every $H$-free graph $G$ (where $alpha(G)$ is the size of the largest stable set of $G$). The smallest graph $H$ for which this is not known is also $P_5$, which, conveniently, is a forest; and every forest that satisfies Esperet’s conjecture also satisfies the Erdős-Hajnal conjecture. So there is substantial interest in the chromatic numbers of $P_5$-free graphs. The best upper bound that was previously known, due to Esperet, Lemoine, Maffray, and Morel, was that $chi(G)le (5/27)3^omega(G)$ for every $P_5$-free graph $G$ with $omega(G) > 2$. In recent work with Alex Scott and Sophie Spirkl, we have proved several results related to Esperet’s conjecture, including proofs of its truth for some new types of forest $H$, and a “near-polynomial” bound when $H = P_5$, that $chi(G) le omega(G)^{log_2(omega(G))}$ for every $P_5$-free graph $G$ with $omega(G) > 2$. We survey these results and give a proof of the new bound for $P_5$.

Joonkyung Lee (이준경), Majority dynamics on sparse random graphs
2021-10-12 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $pm 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 $pm 1$-assignment converges to a $99%$-agreement with high probability whenever $p=omega(1/n)$.
This conjecture was first confirmed for $pgeqlambda n^{-1/2}$ for a large constant $lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p< lambda n^{-1/2}$. We break this $Omega(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where $lambda’ n^{-3/5}log n leq p leq lambda n^{-1/2}$ with a large constant $lambda’>0$.
Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.

Young Researchers in Extremal and Probabilistic Combinatorics
2021-10-20 - 2021-10-22 | Zoom ID: 554 788 7710 (507464)
The aim of the Young Researchers in Extremal and Probabilistic Combinatorics is to bring together early career researchers working on these topics. The workshop will consist of several 25 minute talks across three days from October 20 to 22, 2021. Due to Covid the workshop will be held online.

Invited Speakers & Program
Oct. 20 Wednesday 4 PM (KST) – 8 PM (KST)

Andrzej Grzesik (Jagiellonian University): Degenerated generalized Turán numbers of cycles, 4:00-4:25
Jan Volec (Czech Technical University): Existence of common graphs with large chromatic number, 4:30-4:55
Balázs Patkós (Rényi Institute): Vector sum-intersection theorems, 5:00-5:25
István Tomon (ETH Zurich): Small doubling, atomic structure and $ell$-divisible set families, 5:30-5:55
Michael Anastos (Freie Universität Berlin): Longest Cycles in Sparse Random Graphs and Where to Find Them, 6:30-6:55
Adam Zsolt Wagner (Tel Aviv University): Constructions in combinatorics via neural networks, 7:00-7:25
Yelena Yuditsky (Université libre de Bruxelles): On multicolor Ramsey numbers and subset-coloring of hypergraphs, 7:30-7:55

Oct. 21 Thursday 4 PM (KST) – 8 PM (KST)

Kevin Hendrey (IBS Discrete Mathematics Group): Extremal functions for sparse minors, 4:00-4:25
Simona Boyadzhiyska (Freie Universität Berlin): Ramsey simplicity of random graphs, 4:30-4:55
Shagnik Das (National Taiwan University): Schur’s Theorem in randomly perturbed sets, 5:00-5:25
Tony Huynh (Monash University): Subgraph densities in minor-closed classes (and beyond), 5:30-5:55
Ander Lamaison (Masaryk University): Hypergraphs with minimum uniform Turán density, 6:30-6:55
Ben Lund (IBS Discrete Mathematics Group): Maximal 3-wise intersecting families, 7:00-7:25
Liana Yepremyan (London School of Economics): Enumerating independent sets in Abelian Cayley graphs, 7:30-7:55

Oct. 22 Friday 4 PM (KST) – 8 PM (KST)

Andrey Kupavskii (CNRS): Binary scalar products, 4:00-4:25
Dániel Gerbner (Rényi Institute): Exact results for generalized Turán problems, 4:30-4:55
Oliver Janzer (University of Cambridge): Tiling with monochromatic bipartite graphs of bounded maximum degree, 5:00-5:25
Nika Salia (Rényi Institute): Pósa-type results for Berge Hypergraphs, 5:30-5:55
Debsoumya Chakraborti (IBS Discrete Mathematics Group): Mixing time and expanders, 6:30-6:55
Wei-Tian Li (National Chung Hsing University): Ramsey Properties for $V$-shaped Posets in the Boolean Lattices, 7:00-7:25
Dimitry Zakharov (Moscow Institute of Physics and Technology): Zero subsums in vector spaces over finite fields, 7:30-7:55

Abstracts (pdf file)

Donggyu Kim (김동규), 𝝘-graphic delta-matroids and their applications
2021-10-26 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Bouchet (1987) defined delta-matroids by relaxing the base exchange axiom of matroids. Oum (2009) introduced a graphic delta-matroid from a pair of a graph and its vertex subset. We define a $Gamma$-graphic delta-matroid for an abelian group $Gamma$, which generalizes a graphic delta-matroid.
For an abelian group $Gamma$, a $Gamma$-labelled graph is a graph whose vertices are labelled by elements of $Gamma$. We prove that a certain collection of edge sets of a $Gamma$-labelled graph forms a delta-matroid, which we call a $Gamma$-graphic delta-matroid, and provide a polynomial-time algorithm to solve the separation problem, which allows us to apply the symmetric greedy algorithm of Bouchet (1987) to find a maximum weight feasible set in such a delta-matroid. We also prove that a $Gamma$-graphic delta-matroid is a graphic delta-matroid if and only if it is even. We prove that every $mathbb{Z}_p^k$-graphic delta matroid is represented by some symmetric matrix over a field of characteristic of order $p^k$, and if every $Gamma$-graphic delta-matroid is representable over a finite field $mathbb{F}$, then $Gamma$ is isomorphic to $mathbb{Z}_p^k$ and $mathbb{F}$ is a field of order $p^ell$ for some prime $p$ and positive integers $k$ and $ell$.
This is joint work with Duksang Lee and Sang-il Oum.

Ben Lund, Maximal 3-wise intersecting families
2021-11-02 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A family $mathcal F$ of subsets of {1,2,…,n} is called maximal k-wise intersecting if every collection of at most k members from $mathcal F$ has a common element, and moreover, no set can be added to $mathcal F$ while preserving this property. In 1974, Erdős and Kleitman asked for the smallest possible size of a maximal k-wise intersecting family, for k≥3. We resolve this problem for k=3 and n even and sufficiently large.
This is joint work with Kevin Hendrey, Casey Tompkins, and Tuan Tran.

Martin Milanič, Tree Decompositions with Bounded Independence Number
2021-11-05 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
The independence number of a tree decomposition $mathcal{T}$ of a graph is the smallest integer $k$ such that each bag of $mathcal{T}$ induces a subgraph with independence number at most $k$. If a graph $G$ is given together with a tree decomposition with bounded independence number, then the Maximum Weight Independent Set (MWIS) problem can be solved in polynomial time. Motivated by this observation, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs $H$ for which any graph excluding $H$ with respect to the relation admits a tree decomposition with bounded independence number. Furthermore, using a variety of tools including SPQR trees and potential maximal cliques, we show how to obtain such tree decompositions efficiently.
As an immediate consequence, we obtain that the MWIS problem can be solved in polynomial time in an infinite family of graph classes that properly contain the class of chordal graphs. In fact, our approach shows that the Maximum Weight Independent $mathcal{H}$-Packing problem, a common generalization of the MWIS and the Maximum Weight Induced Matching problems, can be solved in polynomial time in these graph classes.
This is joint work with Clément Dallard and Kenny Štorgel.

Jaehoon Kim (김재훈), 2-complexes with unique embeddings in 3-space
2021-11-09 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A well-known theorem of Whitney states that a 3-connected planar graph admits an essentially unique embedding into the 2-sphere. We prove a 3-dimensional analogue: a simply-connected 2-complex every link graph of which is 3-connected admits an essentially unique locally flat embedding into the 3-sphere, if it admits one at all. This can be thought of as a generalisation of the 3-dimensional Schoenflies theorem. This is joint work with Agelos Georgakopoulos.

Sebastian Wiederrecht, Matching Minors in Bipartite Graphs
2021-11-11 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Matching minors are a specialisation of minors which preserves the existence and elementary structural properties of perfect matchings. They were first discovered as part of the study of the Pfaffian recognition problem on bipartite graphs (Polya’s Permanent Problem) and acted as a major inspiration for the definition of butterfly minors in digraphs. In this talk we consider the origin and motivation behind the study of matching minors, the current state of the art, and their relation to structural digraph theory. The main result is a generalisation of the structure theorem by Robertson et al. and McCuaig for $K_{3,3}$-matching minor free bipartite graphs to bipartite graphs excluding $K_{t,t}$ as a matching minor for general t. This generalisation can be seen as a matching theoretic version of the Flat Wall Theorem by Robertson and Seymour.

Graph Product Structure Theory: Gathering of Participants from Korea
2021-11-23 - 2021-11-26 | Room B223, IBS (기초과학연구원)
On November 22-26, 2021, there is a “Graph Product Structure Theory” workshop in BIRS Centre in Banff (https://www.birs.ca/events/2021/5-day-workshops/21w5235), organized in a hybrid manner with 15 onsite participants and around 50 remote participants. We would like to meet in a group of 5-10 remote participants from Korea in one place, creating a secondary workshop site in Korea. This would allow joint participation in online talks and in-person discussions between local participants.

Casey Tompkins, Ramsey numbers of Boolean lattices
2021-11-23 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The poset Ramsey number $R(Q_{m},Q_{n})$ is the smallest integer $N$ such that any blue-red coloring of the elements of the Boolean lattice $Q_{N}$ has a blue induced copy of $Q_{m}$ or a red induced copy of $Q_{n}$. Axenovich and Walzer showed that $n+2le R(Q_{2},Q_{n})le2n+2$. Recently, Lu and Thompson
improved the upper bound to $frac{5}{3}n+2$. In this paper, we solve this problem asymptotically by showing that $R(Q_{2},Q_{n})=n+O(n/log n)$.
Joint work with Dániel Grósz and Abhishek Methuku.

Tuukka Korhonen, Fast FPT-Approximation of Branchwidth
2021-11-25 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Branchwidth determines how graphs, and more generally, arbitrary connectivity (basically symmetric and submodular) functions could be decomposed into a tree-like structure by specific cuts. We develop a general framework for designing fixed-parameter tractable (FPT) 2-approximation algorithms for branchwidth of connectivity functions. The first ingredient of our framework is combinatorial. We prove a structural theorem establishing that either a sequence of particular refinement operations could decrease the width of a branch decomposition or that the width of the decomposition is already within a factor of 2 from the optimum. The second ingredient is an efficient implementation of the refinement operations for branch decompositions that support efficient dynamic programming. We present two concrete applications of our general framework.

An algorithm that for a given n-vertex graph G and integer k in time $2^{2^{O(k)}} n^2$ either constructs a rank decomposition of G of width at most 2k or concludes that the rankwidth of G is more than $k$. It also yields a $(2^{2k+1}−1)$-approximation algorithm for cliquewidth within the same time complexity, which in turn, improves to $f(k) n^2$ the running times of various algorithms on graphs of cliquewidth $k$. Breaking the “cubic barrier” for rankwidth and cliquewidth was an open problem in the area.
An algorithm that for a given n-vertex graph G and integer k in time $2^{O(k)} n$ either constructs a branch decomposition of G of width at most $2k$ or concludes that the branchwidth of G is more than $k$. This improves over the 3-approximation that follows from the recent treewidth 2-approximation of Korhonen [FOCS 2021].

This is joint work with Fedor Fomin.

Seonghyuk Im (임성혁), Large clique subdivisions in graphs without small dense subgraphs
2021-11-30 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d) = Theta(sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d,d}$. However, this example contains a much smaller subgraph with the almost same average degree, for example, one copy of $K_{d,d}$.
In 2017, Liu and Montgomery proposed the study on the parameter $c_{varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $varepsilon d(G)$. In fact, they conjectured that for small enough $varepsilon>0$, every graph $G$ of average degree $d$ contains a clique subdivision of size $Omega(min{d, sqrt{frac{c_{varepsilon}(G)}{log c_{varepsilon}(G)}}})$. We prove that this conjecture holds up to a multiplicative $min{(loglog d)^6,(log log c_{varepsilon}(G))^6}$-term.
As a corollary, for every graph $F$, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term.
This is joint work with Jaehoon Kim, Youngjin Kim, and Hong Liu.

Eun-Kyung Cho (조은경), Independent domination of graphs with bounded maximum degree
2021-12-07 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The independent domination number of a graph $G$, denoted $i(G)$, is the minimum size of an independent dominating set of $G$. In this talk, we prove a series of results regarding independent domination of graphs with bounded maximum degree.
Let $G$ be a graph with maximum degree at most $k$ where $k ge 1$. We prove that if $k = 4$, then $i(G) le frac{5}{9}|V(G)|$, which is tight. Generalizing this result and a result by Akbari et al., we suggest a conjecture on the upper bound of $i(G)$ for $k ge 1$, which is tight if true.
Let $G’$ be a connected $k$-regular graph that is not $K_{k, k}$ where $kgeq 3$. We prove that $i(G’)le frac{k-1}{2k-1}|V(G’)|$, which is tight for $k in {3, 4}$, generalizing a result by Lam, Shiu, and Sun. This result also answers a question by Goddard et al. in the affirmative.
In addition, we show that $frac{i(G’)}{gamma(G’)} le frac{k^3-3k^2+2}{2k^2-6k+2}$, strengthening upon a result of Knor, Škrekovski, and Tepeh, where $gamma(G’)$ is the domination number of $G’$.
Moreover, if we restrict $G’$ to be a cubic graph without $4$-cycles, then we prove that $i(G’) le frac{4}{11}|V(G’)|$, which improves a result by Abrishami and Henning.
This talk is based on joint work with Ilkyoo Choi, Hyemin Kwon, and Boram Park.

David Munhá Correia, Rainbow matchings
2021-12-09 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
I will discuss various results for rainbow matching problems. In particular, I will introduce a ‘sampling trick’ which can be used to obtain short proofs of old results as well as to solve asymptotically some well known conjectures. This is joint work with Alexey Pokrovskiy and Benny Sudakov.

Tuan Tran, Exponential decay of intersection volume with applications on list-decodability and sphere-covering bounds
2021-12-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We give some natural sufficient conditions for balls in a metric space to have small intersection. Roughly speaking, this happens when the metric space is (i) expanding and (ii) well-spread, and (iii) certain random variable on the boundary of a ball has a small tail. As applications, we show that the volume of intersection of balls in Hamming space and symmetric groups decays exponentially as their centers drift apart. To verify condition (iii), we prove some deviation inequalities `on the slice’ for functions with Lipschitz conditions.
We then use these estimates on intersection volumes to

obtain a sharp lower bound on list-decodability of random q-ary codes, confirming a conjecture of Li and Wootters [IEEE Trans. Inf. Theory 2021]; and
improve sphere-covering bound from the 70s on constant weight codes by a factor linear in dimension, resolving a problem raised by Jiang and Vardy [IEEE Trans. Inf. Theory 2004].

Our probabilistic point of view also offers a unified framework to obtain improvements on other sphere-covering bounds, giving conceptually simple and calculation-free proofs for q-ary codes, permutation codes, and spherical codes.
This is joint work with Jaehoon Kim and Hong Liu.

2021 Combinatorics Workshop (2021 조합론 학술대회)
2021-12-20 - 2021-12-22 | The Bloomvista
The Combinatorics Workshop (조합론 학술대회) is an annual conference of combinatorialists in Korea that started in 2004 by the Yonsei University BK21 Research Group. Since 2013, this workshop has been advised by the committee of discrete mathematics of the Korean Mathematical Society. This year it will take place at The Bloomvista in Yangpyeong on December 20-22, 2021.
The aim of this workshop is to bring together active researchers with different backgrounds to discuss recent and prospective advances in combinatorics and related areas.
We plan to limit the number of participants. Registration (without a fee) will be required. General participants will be required to pay for their own accommodation.

Title: 2021 Combinatorics Workshop (2021 조합론 학술대회)
Date: December 20 – 22 (Mon-Wed), 2021
Venue: The Bloomvista, Yangpyeong
Website: https://cw2021.combinatorics.kr

Plan

Starting in the afternoon of Thursday and ending in the morning of Wednesday.
There will be 5 invited talks for 50 minutes each.
There will be contributed talks for 25 minutes each.

Using English is recommended if there are non-Korean participants in the audience.
The call for contributed talks will be announced later.

It will be an offline meeting.

Invited Speakers

Dongsu Kim, KAIST
Joonkyung Lee, Hanyang University
Hong Liu, University of Warwick, UK
Suil O, SUNY Korea
Seonjeong Park, Jeonju University

Call for Abstracts
We are looking for contributed talks! If you are interested in giving a contributed talk, then please submit your abstract until November 15, 2021.
Registration

Please fill out the registration form by November 21, 2021.

The registration is free.
The organizers will announce the price for the accommodation soon.

Due to the government COVID-19 policy, the organizers may reject some registration, even if the registration was made before November 21.

Organizing Committee

Jeong-Ok Choi, GIST
Sang-il Oum, IBS Discrete Mathematics Group and KAIST
Heesung Shin, Inha University

Advisory Committee
Committee of Discrete Mathematics, The Korean Mathematical Society (Chair: Soojin Cho, Ajou University)
Host and Sponsors
IBS Discrete Mathematics Group

Seunghun Lee (이승훈), Transversals and colorings of simplicial spheres
2022-01-04 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Motivated from the surrounding property of a point set in $mathbb{R}^d$ introduced by Holmsen, Pach and Tverberg, we consider the transversal number and chromatic number of a simplicial sphere. As an attempt to give a lower bound for the maximum transversal ratio of simplicial $d$-spheres, we provide two infinite constructions. The first construction gives infinitely many $(d+1)$-dimensional simplicial polytopes with the transversal ratio exactly $frac{2}{d+2}$ for every $dgeq 2$. In the case of $d=2$, this meets the previously well-known upper bound $1/2$ tightly. The second gives infinitely many simplicial 3-spheres with the transversal ratio greater than $1/2$. This was unexpected from what was previously known about the surrounding property. Moreover, we show that, for $dgeq 3$, the facet hypergraph $mathcal{F}(mathbf{P})$ of a $(d+1)$-dimensional simplicial polytope $mathbf{P}$ has the chromatic number $chi(mathcal{F}(mathbf{P})) in O(n^{frac{lceil d/2rceil-1}{d}})$, where $n$ is the number of vertices of $mathbf{P}$. This slightly improves the upper bound previously obtained by Heise, Panagiotou, Pikhurko, and Taraz. This is a joint work with Joseph Briggs and Michael Gene Dobbins.

Andreas Holmsen, Some recent results on geometric transversals
2022-01-11 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
A geometric transversal to a family of convex sets in $mathbb R^d$ is an affine flat that intersects the members of the family. While there exists a far-reaching theory concerning 0-dimensional transversals (intersection patterns of convex sets), much less is known when it comes to higher-dimensional transversals. In this talk, I will present some new and old results and problems regarding geometric transversals, based on joint work with Otfried Cheong and Xavier Goaoc.

Ron Aharoni, A strong version of the Caccetta-Haggkvist conjecture
2022-01-13 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
The Caccetta-Haggkvist conjecture, one of the best known in graph theory, is that in a digraph with $n$ vertices in which all outdegrees are at least $n/k$ there is a directed cycle of length at most $k$. This is known for large values of $k$, relatively to n, and asymptotically for n large. A few years ago I offered a generalization: given sets $F_1$, $ldots$, $F_n$ of sets of undirected edges, each of size at least $n/k$, there exists a rainbow undirected cycle of length at most $k$. The directed version is obtained by taking as $F_i$ the set of edges going out of the vertex $v_i$ ($i le n$), with the directions removed. I will tell about recent results on this conjecture, obtained together with He Guo, with Beger, Chudnovsky and Zerbib, and with DeVos and Holzman.

Jaehyeon Seo (서재현), A rainbow Turán problem for color-critical graphs
2022-01-18 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
For given $k$ graphs $G_1,dots, G_k$ over a common vertex set of size $n$, what conditions on $G_i$ ensures a ‘colorful’ copy of $H$, i.e. a copy of $H$ containing at most one edge from each $G_i$?
Keevash, Saks, Sudakov, and Verstraëte defined $operatorname{ex}_k(n,H)$ to be the maximum total number of edges of the graphs $G_1,dots, G_k$ on a common vertex set of size $n$ having no colorful copy of $H$. They completely determined $operatorname{ex}_k(n,K_r)$ for large $n$ by showing that, depending on the value of $k$, one of the two natural constructions is always the extremal construction. Moreover, they conjectured the same holds for every color-critical graphs and proved it for $3$-color-critical graphs.
We prove their conjecture for $4$-color-critical graphs and for almost all $r$-color-critical graphs when $r > 4$. Moreover, we show that for every non-color-critical non-bipartite graphs, none of the two natural constructions is extremal for certain values of $k$. This is a joint work with Debsoumya Chakraborti, Jaehoon Kim, Hyunwoo Lee, and Hong Liu.

Ken-ichi Kawarabayashi (河原林 健一), Toward Directed Graph Minor Theory
2022-01-20 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Graph Minor project by Robertson and Seymour is perhaps the deepest theory in Graph Theory. It gives a deep structural characterization of graphs without any graph $H$ as a minor. It also gives many exciting algorithmic consequences.
In this work, I would like to talk about our attempt to extend Graph minor project to directed graphs. Topics include
1. The directed grid theorem
2. The directed flat wall theorem
3. Tangle tree decomposition
4. Variant of the directed disjoint paths problems
5. Toward the structure (and decomposition) theorem for H-minor-free digraphs.
Joint work with Stephan Kreutzer, O-joung Kwon, Archontia Giannopoulou.

O-joung Kwon (권오정), Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
2022-01-25 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In a reduction sequence of a graph, vertices are successively identified until the graph has one vertex. At each step, when identifying $u$ and $v$, each edge incident to exactly one of $u$ and $v$ is coloured red. Bonnet, Kim, Thomassé, and Watrigant [FOCS 2020] defined the twin-width of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has maximum degree at most $k$. For any graph parameter $f$, we define the reduced-$f$ of a graph $G$ to be the minimum integer $k$ such that there is a reduction sequence of $G$ in which every red graph has $f$ at most $k$. Our focus is on graph classes with bounded reduced-bandwidth, which implies and is stronger than bounded twin-width (reduced-maximum-degree).
We show that every proper minor-closed class has bounded reduced-bandwidth, which is qualitatively stronger than a result of Bonnet et al. for bounded twin-width. In many instances, we also make quantitative improvements. For example, all previous upper bounds on the twin-width of planar graphs were at least $2^{1000}$. We show that planar graphs have reduced-bandwidth at most $466$ and twin-width at most $583$; moreover, the witnessing reduction sequence can be constructed in polynomial time. We show that $d$-powers of graphs in a proper minor-closed class have bounded reduced-bandwidth (irrespective of the degree of the vertices).
This is joint work with Édouard bonnet and David Wood.

Bo Ning (宁博), Substructures and eigenvalues of graphs: Triangles and quadrilaterals
2022-01-27 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Our talk will mainly focus on the relationship between substructures and eigenvalues of graphs. We will briefly survey recent developments on a conjecture of Bollobás and Nikiforov and a classical result of Nosal on triangles. In particular, we shall present counting results for previous spectral theorems on triangles and quadrilaterals. If time allows, we will give a sketch for the proof of one new counting result on triangles.

Pascal Gollin, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups
2022-02-08 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. We therefore say that cycles satisfy the Erdős-Pósa property. However, while odd cycles do not satisfy the Erdős-Pósa property, Reed proved in 1999 an analogue by relaxing packing to half-integral packing, where each vertex is allowed to be contained in at most two such cycles. Moreover, he gave a structural characterisation for when the Erdős-Pósa property for odd cycles fails.
We prove a far-reaching generalisation of the theorem of Reed; if the edges of a graph are labelled by finitely many abelian groups, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property, and we similarly give a structural characterisation for the failure of the Erdős-Pósa property.
A multitude of natural properties of cycles can be encoded in this setting. For example, we show that the cycles of length $ell$ modulo $m$ satisfy the half-integral Erdős-Pósa property, and we characterise for which values of $ell$ and $m$ these cycles satisfy the Erdős-Pósa property.
This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.

James Davies, Separating polynomial $chi$-boundedness from $chi$-boundedness
2022-02-10 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
We prove that there is a function $f : mathbb{N} to mathbb{N}$ such that for every function $g : mathbb{N} to mathbb{N} cup {infty}$ with $g(1)=1$ and $g ge f$, there is a hereditary class of graphs $mathcal{G}$ such that for each $omega in mathbb{N}$, the maximum chromatic number of a graph in $mathcal{G}$ with clique number $omega$ is equal to $g(omega)$. This extends a recent breakthrough of Carbonero, Hompe, Moore, and Spirk. In particular, this proves that there are hereditary classes of graphs that are $chi$-bounded but not polynomially $chi$-bounded.
Joint work with Marcin Briański and Bartosz Walczak.

Jinha Kim (김진하), Independent domination of graphs with bounded maximum degree
2022-02-15 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
An independent dominating set of a graph, also known as a maximal independent set, is a set $S$ of pairwise non-adjacent vertices such that every vertex not in $S$ is adjacent to some vertex in $S$. We prove that for $Delta=4$ or $Deltage 6$, every connected $n$-vertex graph of maximum degree at most $Delta$ has an independent dominating set of size at most $(1-frac{Delta}{ lfloorDelta^2/4rfloor+Delta })(n-1)+1$. In addition, we characterize all connected graphs having the equality and we show that other connected graphs have an independent dominating set of size at most $(1-frac{Delta}{ lfloorDelta^2/4rfloor+Delta })n$.
This is joint work with Eun-Kyung Cho, Minki Kim, and Sang-il Oum.

Manuel Lafond, Recognizing k-leaf powers in polynomial time, for constant k
2022-02-18 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
A graph G is a k-leaf power if there exists a tree T whose leaf set is V(G), and such that uv is an edge if and only if the distance between u and v in T is at most k. The graph classes of k-leaf powers have several applications in computational biology, but recognizing them has remained a challenging algorithmic problem for the past two decades. In a recent paper presented at SODA22, it was shown that k-leaf powers can be recognized in polynomial time if k is fixed.
In this seminar, I will present the algorithm that decides whether a graph G is a k-leaf power in time $O(n^{f(k)})$ for some function f that depends only on k (but has the growth rate of a power tower function). More specifically, I will discuss how the difficult k-leaf power instances contain many cutsets that have the same neighborhood layering. I will then show that these similar cutsets are redundant and that removing one of them does not lose any information, which can be exploited for algorithmic purposes.

Donggyu Kim (김동규), A stronger version of Tutte's wheel theorem for vertex-minors
2022-02-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Tutte (1961) proved that every simple $3$-connected graph $G$ has an edge $e$ such that $G setminus e$ or $G / e$ is simple $3$-connected, unless $G$ is isomorphic to a wheel. We call such an edge non-essential. Oxley and Wu (2000) proved that every simple $3$-connected graph has at least $2$ non-essential edges unless it is isomorphic to a wheel. Moreover, they proved that every simple $3$-connected graph has at least $3$ non-essential edges if and only if it is isomorphic to neither a twisted wheel nor a $k$-dimensional wheel with $kgeq2$.
We prove analogous results for graphs with vertex-minors. For a vertex $v$ of a graph $G$, let $G*v$ be the graph obtained from $G$ by deleting all edges joining two neighbors of $v$ and adding edges joining non-adjacent pairs of two neighbors of $v$. This operation is called the local complementation at $v$, and we say two graphs are locally equivalent if one can be obtained from the other by applying a sequence of local complementations. A graph $H$ is a vertex-minor of a graph $G$ if $H$ is an induced subgraph of a graph locally equivalent to $G$. A split of a graph is a partition $(A,B)$ of its vertex set such that $|A|,|B| geq 2$ and for some $A’subseteq A$ and $B’subseteq B$, two vertices $xin A$ and $yin B$ are adjacent if and only if $xin A’$ and $yin B’$. A graph is prime if it has no split.
A vertex $v$ of a graph is non-essential if at least two of three kinds of vertex-minor reductions at $v$ result in prime graphs. We prove that every prime graph with at least $5$ vertices has at least two non-essential vertices unless it is locally equivalent to a cycle. It is stronger than a theorem proved by Allys (1994), which states that every prime graph with at least $5$ vertices has a non-essential vertex unless it is locally equivalent to a cycle. As a corollary of our result, one can obtain the first result of Oxley and Wu. Furthermore, we show that every prime graph with at least $5$ vertices has at least $3$ non-essential vertices if and only if it is not locally equivalent to a graph with two specified vertices $x$ and $y$ consisting of at least two internally-disjoint paths from $x$ to $y$ in which $x$ and $y$ have no common neighbor.
This is joint work with Sang-il Oum.

Sang-il Oum (엄상일), Obstructions for matroids of path-width at most k and graphs of linear rank-width at most k
2022-02-28 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Every minor-closed class of matroids of bounded branch-width can be characterized by a minimal list of excluded minors, but unlike graphs, this list could be infinite in general. However, for each fixed finite field $mathbb F$, the list contains only finitely many $mathbb F$-representable matroids, due to the well-quasi-ordering of $mathbb F$-representable matroids of bounded branch-width under taking matroid minors [J. F. Geelen, A. M. H. Gerards, and G. Whittle (2002)]. But this proof is non-constructive and does not provide any algorithm for computing these $mathbb F$-representable excluded minors in general.
We consider the class of matroids of path-width at most $k$ for fixed $k$. We prove that for a finite field $mathbb F$, every $mathbb F$-representable excluded minor for the class of matroids of path-width at most~$k$ has at most $2^{|mathbb{F}|^{O(k^2)}}$ elements. We can therefore compute, for any integer $k$ and a fixed finite field $mathbb F$, the set of $mathbb F$-representable excluded minors for the class of matroids of path-width $k$, and this gives as a corollary a polynomial-time algorithm for checking whether the path-width of an $mathbb F$-represented matroid is at most $k$. We also prove that every excluded pivot-minor for the class of graphs having linear rank-width at most $k$ has at most $2^{2^{O(k^2)}}$ vertices, which also results in a similar algorithmic consequence for linear rank-width of graphs.
This is joint work with Mamadou M. Kanté, Eun Jung Kim, and O-joung Kwon.

Kevin Hendrey, A unified Erdős-Pósa theorem for cycles in graphs labelled by multiple abelian groups (revisited)
2022-03-07 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
This talk follows on from the recent talk of Pascal Gollin in this seminar series, but will aim to be accessible for newcomers.
Erdős and Pósa proved in 1965 that there is a duality between the maximum size of a packing of cycles and the minimum size of a vertex set hitting all cycles. By relaxing `packing’ to `half-integral packing’, Reed obtained an analogous result for odd cycles, and gave a structural characterisation of when the (integral) packing version fails.
We prove some far-reaching generalisations of these theorems. First, we show that if the edges of a graph are labelled by finitely many abelian groups, then the cycles whose values avoid a fixed finite set for each abelian group satisfy the half-integral Erdős-Pósa property. Similarly to Reed, we give a structural characterisation for the failure of the integral Erdős-Pósa property in this setting. This allows us to deduce the full Erdős-Pósa property for many natural classes of cycles.
We will look at applications of these results to graphs embedded on surfaces, and also discuss some possibilities and obstacles for extending these results.
This is joint work with Kevin Hendrey, Ken-ichi Kawarabayashi, O-joung Kwon, Sang-il Oum, and Youngho Yoo.
