Discrete Mathematics Group

Hongseok Yang (양홍석), Learning Symmetric Rules with SATNet
2022-05-30 16:30 - 17:30 (Asia/Seoul) | Room B332, IBS (기초과학연구원)
SATNet is a differentiable constraint solver with a custom backpropagation algorithm, which can be used as a layer in a deep-learning system. It is a promising proposal for bridging deep learning and logical reasoning. In fact, SATNet has been successfully applied to learn, among others, the rules of a complex logical puzzle, such as Sudoku, just from input and output pairs where inputs are given as images. In this paper, we show how to improve the learning of SATNet by exploiting symmetries in the target rules of a given but unknown logical puzzle or more generally a logical formula. We present SymSATNet, a variant of SATNet that translates the given symmetries of the target rules to a condition on the parameters of SATNet and requires that the parameters should have a particular parametric form that guarantees the condition. The requirement dramatically reduces the number of parameters to learn for the rules with enough symmetries, and makes the parameter learning of SymSATNet much easier than that of SATNet. We also describe a technique for automatically discovering symmetries of the target rules from examples. Our experiments with Sudoku and Rubik’s cube show the substantial improvement of SymSATNet over the baseline SATNet.
This is joint work with Sangho Lim and Eungyeol Oh.

KSIAM 2022 Spring Meeting
2022-05-27 13:20 - 17:40 | IBS Science Culture Center
KSIAM (Korean Society for Industrial and Applied Mathematics) will have the KSIAM 2022 Spring Conference at the Institute for Basic Science (IBS). Its academic session for Combinatorics decided to have an invited talk by Joonkyung Lee at the Hanyang University, a special session “Graph Theory” organized by Sang-il Oum and the IBS DIMAG, a special session “Enumerative Combinatorics” organized by Dongsu Kim at KAIST, and a poster session, all on May 27 afternoon. The deadline for the abstract submission is May 2 and the deadline for the early registration is May 9.
Invited talk (May 27 Friday, 16:40-17:40)

Joonkyung Lee이준경 (Hanyang University), Graph homomorphism inequalities and their applications
Counting (weighted) homomorphisms between graphs relates to a wide variety of areas, in- cluding graph theory, probability, statistical physics and theoretical computer science. In recent years, various new applications of inequalities between graph homomorphism counts have been found.
We will discuss some of the examples, including a simple proof of the Bondy–Simonovits theorem and a new estimate for the rainbow Turán numbers of even cycles. If time permits, we will also touch upon some recent progress on Sidorenko’s conjecture and related questions, in particular their applications on the bipartite Turán problems.
Based on joint work with David Conlon, Jaehoon Kim, Hong Liu, and Tuan Tran.

Special session “Graph Theory” (May 27, 13:20-14:40)
Organized by Sang-il Oum엄상일 (IBS Discrete Mathematics Group & KAIST).
Speakers

Boram Park박보람 (Ajou University), Odd Coloring of Graphs
An odd $c$-coloring of a graph is a proper $c$-coloring such that each non-isolated vertex has a color appearing an odd number of times on its neighborhood. Recently, Cranston investigated odd colorings of graphs with bounded maximum average degree, and conjectured that every graph $G$ with $operatorname{mad}(G)leq frac{4c-4}{c+1}$ has an odd $c$-coloring for $cgeq 4$, and proved the conjecture for $cin{5, 6}$. In particular, planar graphs with girth at least $7$ and $6$ have an odd $5$-coloring and an odd $6$-coloring, respectively.
We completely resolve Cranston’s conjecture. For $cgeq 7$, we show that the conjecture is true, in a stronger form that was implicitly suggested by Cranston, but for $c=4$, we construct counterexamples, which all contain $5$-cycles. On the other hand, we show that a graph $G$ with $operatorname{mad}(G)<frac{22}{9}$ and no induced $5$-cycles has an odd $4$-coloring. This implies that a planar graph with girth at least 11 has an odd $4$-coloring. We also prove that a planar graph with girth at least 5 has an odd $6$-coloring.
Joint work with Eun-Kyung Cho, Ilkyoo Choi, and Hyemin Kown.

Jongyook Park박종육 (Kyungpook National University), On the Delsarte bound
We study the order of a maximal clique in an amply regular graph with a fixed smallest eigenvalue by considering a vertex that is adjacent to some (but not all) vertices of the maximal clique. As a consequence, we show that if a strongly regular graph contains a Delsarte clique, then the parameter μ is either small or large. Furthermore, we obtain a cubic polynomial that assures that a maximal clique in an amply regular graph is either small or large (under certain assumptions). Combining this cubic polynomial with the claw-bound, we rule out an infinite family of feasible parameters (v, k, λ, μ) for strongly regular graphs. Lastly, we provide tables of parameters (v, k, λ, μ) for nonexistent strongly regular graphs with smallest eigenvalue −4,−5,−6 or −7. This is joint work with Gary Greaves and Jack Koolen.

O-joung Kwon권오정 (Hanyang University and IBS Discrete Mathematics Group), Well-partitioned chordal graphs
We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph $G$ is a well-partitioned chordal graph if there exist a partition $mathcal{P}$ of the vertex set of $G$ into cliques and a tree $mathcal{T}$ having $mathcal{P}$ as a vertex set such that for distinct $X,Yin mathcal{P}$, (1) the edges between $X$ and $Y$ in $G$ form a complete bipartite subgraph whose parts are some subsets of $X$ and $Y$, if $X$ and $Y$ are adjacent in $mathcal{T}$, and (2) there are no edges between $X$ and $Y$ in $G$ otherwise. A split graph with vertex partition $(C, I)$ where $C$ is a clique and $I$ is an independent set is a well-partitioned chordal graph as witnessed by a star $mathcal{T}$ having $C$ as the center and each vertex in $I$ as a leaf, viewed as a clique of size $1$. We characterize well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given a graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal.
We observe that there are problems, for instance Densest $k$-Subgraph and $b$-Coloring, that are polynomial-time solvable on split graphs but become NP-hard on well-partitioned chordal graphs. On the other hand, we show that the Geodetic Set problem, known to be NP-hard on chordal graphs, can be solved in polynomial time on well-partitioned chordal graphs. We also answer two combinatorial questions on well-partitioned chordal graphs that are open on chordal graphs, namely that each well-partitioned chordal graph admits a polynomial-time constructible tree $3$-spanner, and that each ($2$-connected) well-partitioned chordal graph has a vertex that intersects all its longest paths (cycles). Joint work with Jungho Ahn, Lars Jaffke, and Paloma T. Lima.

Stijn Cambie (IBS Extremal Combinatorics and Probability Group), Regular Cereceda’s Conjecture
The reconfiguration graph $mathcal C_k(G)$ for the $k$-colourings of a graph $G$ has a vertex for each proper $k$-colouring of $G$, and two vertices of $mathcal C_k(G)$ are adjacent precisely when those $k$-colourings differ on a single vertex of $G$. Much work has focused on bounding the maximum value of $operatorname{diam} mathcal C_k(G)$ over all $n$-vertex graphs $G$. One of the most famous conjectures related related to $mathcal C_k(G)$ is Cereceda’s conjecture, which says that if $k ge operatorname{degen}(G) + 2$, the diameter of $mathcal C_k(G)$ is $O(n^2)$. In this talk, we give some ideas towards a precise form for Cereceda’s conjecture, when restricting to regular graphs.
This is based on joint work with Wouter Cames van Batenburg (TU Delft, the Netherlands) and Daniel Cranston (Virginia Commonwealth University, USA), which originates from the online workshop Graph Reconfiguration of the Sparse Graphs Coalition.

Special session “Enumerative Combinatorics” (May 27, 15:00-16:20)
Organized by Dongsu Kim김동수 (KAIST).
Speakers

Meesue Yoo류미수 (Chungbuk National University), Combinatorial description for the Hall-Littlewood expansion of unicellular LLT and chromatic quasisymmetric polynomials
In this work, we obtain a Hall–Littlewood expansion of the chromatic quasisymmetric functions by using a Dyck path model and linked rook placements. By using the Carlsson–Mellit relation between the chromatic quasisymmetric functions and the unicellular LLT polynomials, this combinatorial description for the Hall–Littlewood coefficients of the chromatic quasisymmetric functions also gives the coefficients of the unicellular LLT polynomials expanded in terms of the modified transformed Hall–Littlewood polynomials. Joint work with Seung Jin Lee.

Donghyun Kim김동현 (Sungkyunkwan University), Combinatorial formulas for the coefficients of the Al-Salam-Chihara polynomials
The Al-Salam-Chihara polynomials are an important family of orthogonal polynomials in one variable $x$ depending on 3 parameters $alpha$, $beta$ and $q$. They are closely connected to a model from statistical mechanics called the partially asymmetric simple exclusion process (PASEP) and they can be obtained as a specialization of the Askey-Wilson polynomials. We give two different combinatorial formulas for the coefficients of the (transformed) Al-Salam-Chihara polynomials. Our formulas make manifest the fact that the coefficients are polynomials in $alpha$, $beta$ and $q$ with positive coefficients.

Jisun Huh허지선 (Ajou University), Combinatorics on bounded Motzkin paths and its applications
A free Motzkin path of length (n) is a lattice path which starts at ((0,0)) or ((0,1)), ends at ((n,0)), and has only up steps (u=(1,1)), down steps (d=(1,-1)), and flat steps (f=(1,0)). In addition, if a free Motzkin path starts at ((0,0)) and stays weakly above the (x)-axis, then it is called a Motzkin path. In this talk, we construct a bijection between (F(m,r,k)) and (M(m,r,k)), where (F(m,r,k)) is the set of free Motzkin paths of length (m+r) with (r) flat steps that are contained in the strip (-lfloor k/2 rfloor leq y leq lfloor (k+1)/2 rfloor) and (M(m,r,k)) is the set of Motzkin prefixed of length (m+r) with (r) flat steps that are contained in the strip (0 leq y leq k). Furthermore, we provide path interpretations of ordinary/self-conjugate (t)-core partitions with (m)-corners as an application.
This is joint work with Hyunsoo Cho, Hayan Nam, and Jaebum Sohn.

Jihyeug Jang장지혁 (Sungkyunkwan University), A combinatorial model for the transition matrix between the Specht and web bases
We introduce a new class of permutations, called web permutations. Using these permutations, we provide a combinatorial interpretation for entries of the transition between the Specht and web bases, which answers Rhoades’s question. Furthermore, we study enumerative properties of these permutations. Joint work with Byung-Hak Hwang and Jaeseong Oh.

Sebastian Siebertz, Transducing paths in graph classes with unbounded shrubdepth
2022-05-25 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from C one cannot FO-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the MSO-transduction quasi-order, even in the stronger form that concerns FO-transductions instead of MSO-transductions.
The backbone of our proof is a graph-theoretic statement that says the following: If a graph G excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of G can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly chi-bounded.
This is joint work with Patrice Ossona de Mendez and Michał Pilipczuk.

Stijn Cambie, The precise diameter of reconfiguration graphs
2022-05-23 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Reconfiguration is about changing instances in small steps. For example, one can perform certain moves on a Rubik’s cube, each of them changing its configuration a bit. In this case, in at most 20 steps, one can end up with the preferred result. One could construct a graph with as nodes the possible configurations of the Rubik’s cube (up to some isomorphism) and connect two nodes if one can be obtained by applying only one move to the other. Finding an optimal solution, i.e. a minimum number of moves to solve a Rubik’s cube is now equivalent to finding the distance in the graph.
We will wonder about similar problems in reconfiguration, but applied to list- and DP-colouring. In this case, the small step consists of recolouring precisely one vertex. Now we will be interested in the diameter of the reconfiguration graph and show that sometimes we can determine the precise diameters of these.
As such, during this talk, we present some main ideas of [arXiv:2204.07928].

Gil Kalai, The Cascade Conjecture and other Helly-type Problems
2022-05-19 16:15 - 17:15 | Zoom ID: 868 7549 9085
[Colloquium, Department of Mathematical Sciences, KAIST]
For a set $X$ of points $x(1)$, $x(2)$, $ldots$, $x(n)$ in some real vector space $V$ we denote by $T(X,r)$ the set of points in $X$ that belong to the convex hulls of r pairwise disjoint subsets of $X$.
We let $t(X,r)=1+dim(T(X,r))$.
Radon’s theorem asserts that
If $t(X,1)< |X|$, then $t(X, 2) >0$.
The first open case of the cascade conjecture asserts that
If $t(X,1)+t(X,2) < |X|$, then $t(X,3) >0$.
In the lecture, I will discuss connections with topology and with various problems in graph theory. I will also mention questions regarding dimensions of intersection of convex sets.
Some related material:
1) A lecture (from 1999): An invitation to Tverberg Theorem: https://youtu.be/Wjg1_QwjUos
2) A paper on Helly type problems by Barany and me https://arxiv.org/abs/2108.08804
3) A link to Barany’s book: Combinatorial convexity https://www.amazon.com/Combinatorial-Convexity-University-Lecture-77/dp/1470467097

Jan Kurkofka, Canonical Graph Decompositions via Coverings
2022-05-18 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. The global structure of the graph, as determined by the relative position of these parts, is described by a coarser model. This is a simpler graph determined entirely by the decomposition, not imposed.
The model and decomposition are obtained as projections of the tangle-tree structure of a covering of the given graph that reflects its local structure at the intended level of locality while unfolding its global structure.
Our theorem extends to locally finite quasi-transitive graphs and in particular to locally finite Cayley graphs. It thereby offers a canonical decomposition theorem for finitely generated groups into local parts, whose relative structure is displayed by a graph.
Joint work with Reinhard Diestel, Raphael W. Jacobs and Paul Knappe.

Andreas Holmsen, A colorful version of the Goodman-Pollack-Wenger transversal theorem
2022-05-16 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Hadwiger’s transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently generalized to hyperplane transversals in $mathbb{R}^d$ by Goodman, Pollack, and Wenger. Here we establish a colorful extension of their theorem, which proves a conjecture of Arocha, Bracho, and Montejano. The proof uses topological methods, in particular the Borsuk-Ulam theorem. The same methods also allow us to generalize some colorful transversal theorems of Montejano and Karasev.

Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs
2022-05-09 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts, called exponential random graph model (ERGM). Despite its importance, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In this talk, I will talk about a brief overview on the upper tail problem and the concentration of measure results for the ERGM. Joint work with Shirshendu Ganguly and Ella Hiesmayr.

Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems
2022-05-02 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $rm{Hom}_mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd length, and is otherwise $rm{NP}$-complete. We also get dichotomies for the list, extension, and retraction versions of the problem.
This is joint work with Hyobin Kim and Mark Siggers at Kyungpook National University.

Michael Savery, Induced subgraphs of induced subgraphs of large chromatic number
2022-04-27 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
We prove that for every graph F with at least one edge there are graphs H of arbitrarily large chromatic number and the same clique number as F such that every F-free induced subgraph of H has chromatic number at most c=c(F). (Here a graph is F-free if it does not contain an induced copy of F.) This generalises recent theorems of Briański, Davies and Walczak, and of Carbonero, Hompe, Moore and Spirkl. We further show an analogous statement where clique number is replaced by odd girth. This is joint work with Antonio Girão, Freddie Illingworth, Emil Powierski, Alex Scott, Youri Tamitegama and Jane Tan.

Boram Park (박보람), Odd coloring of sparse graphs
2022-04-25 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x in V (G)$ there exists a color $c$ such that $c$ is used an odd number of times in the neighborhood of $x$. The recent work on this topic will be presented, and the work is based on Eun-Kyung Cho, Ilkyoo Choi, and Hyemin Kown.

Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width
2022-04-13 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $phi$ as input, to decide whether $phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems, such as independent set, distance-r dominating set, and many others.
While the first-order model-checking problem is likely not efficiently solvable in general, efficient algorithms exist for various restricted graph classes, such as graphs of bounded degree, planar graphs etc. After the existence of an efficient model checking algorithm was shown for nowhere dense classes of graphs (which include most of commonly studied classes of sparse graphs), the attention turned to the more general setting of graph classes which can be obtained from sparse graphs using graph transformations called interpretations/transductions. However, despite efforts of several groups of researchers, no positive algorithmic result has been achieved since 2016, when the existence of an efficient algorithm was shown for graph classes interpretable in graphs of bounded degree.
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local clique-width. Notably, this includes interpretations of planar graphs (and more generally, of locally bounded treewidth) and vastly generalizes the result for interpretations of graphs of bounded degree. To obtain this result we developed a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future.
This is joint work with Édouard Bonnet, Jan Dreier, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Toruńczyk.

Younjin Kim (김연진), On the extremal problems related to Szemerédi's theorem
2022-04-11 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
In 1975, Szemerédi proved that for every real number $delta > 0 $ and every positive integer $k$, there exists a positive integer $N$ such that every subset $A$ of the set ${1, 2, cdots, N }$ with $|A| geq delta N$ contains an arithmetic progression of length $k$. There has been a plethora of research related to Szemerédi’s theorem in many areas of mathematics. In 1990, Cameron and Erdős proposed a conjecture about counting the number of subsets of the set ${1,2, dots, N}$ which do not contain an arithmetic progression of length $k$. In the talk, we study a natural higher dimensional version of this conjecture, and also introduce recent extremal problems related to Szemerédi’s theorem.

IBS ECOPRO Opening conference
2022-04-04 - 2022-04-06 | Zoom ID: 878 0445 3986 (ibsecopro) [CLOSED]
To celebrate the opening of the IBS ECOPRO (Extremal Combinatorics and Probability) Group, we will organize a 3-day online conference from April 4 to April 6.
Official Website: https://www.ibs.re.kr/ecopro/event/opening/
Invited Speakers

Noga Alon
Princeton University

József Balogh
University of Illinois at Urbana-Champaign

Jeff Kahn
Rutgers University

Mihyun Kang
Graz University of Technology

Jeong Han Kim
KIAS

Nati Linial
Hebrew University of Jerusalem

Oleg Pikhurko
University of Warwick

Benny Sudakov
ETH Zürich

Tibor Szabó
Freie Universität Berlin

Van Vu
Yale

Program

Time in Korea
Monday
Tuesday
Wednesday

7:15 PM
Kim

8:00 PM
Pikhurko
Kang
Vu

8:45 PM
Kahn
Balogh
Szabó

9:30 PM
Alon
Sudakov
Linial

Organizers

Jaehoon Kim, KAIST
Hong Liu, IBS Extremal Combinatorics and Probability Group
Sang-il Oum, IBS Discrete Mathematics Group / KAIST
Tuan Tran, IBS Discrete Mathematics Group

Jean-Florent Raymond, Long induced paths in minor-closed graph classes and beyond
2022-03-30 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path of order f(n), for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later and logarithmic bounds have been obtained for planar graphs (more generally for graphs of bounded genus) and for interval graphs.
In this talk I will show that every graph of pathwidth less than k that has a path of order n also has an induced path of order $Ω(n^{1/k})$. I will then explain how this result can be used to prove the two following generalizations:

every graph of treewidth less than k that has a path of order n contains an induced path of order $Ω((log n)^{1/k})$;
for every non-trivial graph class that is closed under topological minors there is a constant d∈(0,1) such that every graph from this class that has a path of order n contains an induced path of order $Ω((log n)^d)$.

Joint work with Claire Hilaire.

Ben Lund, Thresholds for incidence properties in finite vector spaces
2022-03-28 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
Suppose that $E$ is a subset of $mathbb{F}_q^n$, so that each point is contained in $E$ with probability $theta$, independently of all other points. Then, what is the probability that there is an $m$-dimensional affine subspace that contains at least $ell$ points of $E$? What is the probability that $E$ intersects all $m$-dimensional affine subspaces? We give Erdős-Renyi threshold functions for these properties, in some cases sharp thresholds. Our results improve previous work of Chen and Greenhill. This is joint work with Jeong Han Kim, Thang Pham, and Semin Yoo.

Jaehoon Kim (김재훈), Ramsey numbers of cycles versus general graphs
2022-03-21 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The Ramsey number $R(F,H)$ is the minimum number $N$ such that any $N$-vertex graph either contains a copy of $F$ or its complement contains $H$. Burr in 1981 proved a pleasingly general result that for any graph $H$, provided $n$ is sufficiently large, a natural lower bound construction gives the correct Ramsey number involving cycles: $R(C_n,H)=(n-1)(chi(H)-1)+sigma(H)$, where $sigma(H)$ is the minimum possible size of a colour class in a $chi(H)$-colouring of $H$. Allen, Brightwell and Skokan conjectured that the same should be true already when $ngeq |H|chi(H)$.
We improve this 40-year-old result of Burr by giving quantitative bounds of the form $ngeq C|H|log^4chi(H)$, which is optimal up to the logarithmic factor. In particular, this proves a strengthening of the Allen-Brightwell-Skokan conjecture for all graphs $H$ with large chromatic number.
This is joint work with John Haslegrave, Joseph Hyde and Hong Liu

MATRIX-IBS Workshop: Structural Graph Theory Downunder II
2022-03-20 - 2022-03-27 | MATRIX, Australia
This program consists of a short intensive workshop, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors, graph colouring, Hadwiger’s Conjecture, bounded expansion classes, graph product structure theory, generalised colouring numbers, VC dimension, induced subgraphs, Erdős-Hajnal conjecture, Gyárfás-Sumner conjecture, twin-width, asymptotic dimension. The majority of the time will be allocated to collaborative research (with only a few talks). The goal is to create an environment where mathematicians at all career stages work side-by-side. We anticipate that open problems will be solved, and lasting collaborations will be initiated.
URL: https://www.matrix-inst.org.au/events/structural-graph-theory-downunder-ll/
Registration is by invitation only. If you are interested to participate in this research program, please contact one of the organisers with your CV and research background.

Tuan Anh Do, Rank- and tree-width of supercritical random graphs
2022-03-14 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
It is known that the rank- and tree-width of the random graph $G(n,p)$ undergo a phase transition at $p = 1/n$; whilst for subcritical $p$, the rank- and tree-width are bounded above by a constant, for supercritical $p$, both parameters are linear in $n$. The known proofs of these results use as a black box an important theorem of Benjamini, Kozma, and Wormald on the expansion of supercritical random graphs. We give a new, short, and direct proof of these results, leading to more explicit bounds on these parameters, and also consider the rank- and tree-width of supercritical random graphs closer to the critical point, showing that this phase transition is smooth.
This is joint work with Joshua Erde and Mihyun Kang.

Fedor Fomin, Long cycles in graphs: Extremal Combinatorics meets Parameterized Algorithms
2022-03-10 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
We examine algorithmic extensions of two classic results of extremal combinatorics. First, the theorem of Dirac from 1952 asserts that a 2-connected graph G with the minimum vertex degree d>1, is either Hamiltonian or contains a cycle of length at least 2d. Second, the theorem of Erdős-Gallai from 1959, states that a 2-connected graph G with the average vertex degree D>1, contains a cycle of length at least D.
We discuss the recent progress in parameterized complexity of computing long cycles “above” the guarantees established by these classical theorems: cycles of lengths at least 2d+k and D+k.
The talk is based on the joint works with Petr Golovach, Danil Sagunov, and Kirill Simonov.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.
