Discrete Mathematics Group

Santiago Guzmán-Pro, Local expressions of graphs classes
2022-09-29 10:00 - 11:00 (Asia/Seoul) | Zoom ID: 869 4632 6610 (ibsdimag)
A common technique to characterize hereditary graph classes is to exhibit their minimal obstructions. Sometimes, the set of minimal obstructions might be infinite, or too complicated to describe. For instance, for any $kge 3$, the set of minimal obstructions of the class of $k$-colourable graphs is yet unknown. Nonetheless, the Roy-Gallai-Hasse-Vitaver Theorem asserts that a graph $G$ is $k$-colourable if and only if it admits an orientation with no directed walk on $k+1$ vertices. We say that a class of graphs $mathcal{P}$ is expressible by forbidden orientations if there is a finite set $F$ of oriented graphs such that $mathcal{P}$ is the class of graphs that admit an $F$-free orientation. We are interested in understanding which graph classes are expressible by forbidden orientations (and why). In this talk, we present some limitations of this expression system. In particular, we show that the class of even-hole free graphs is not expressible by forbidden orientations.
Throughout the talk, we also mention some other related expression systems. In particular, each of these systems provides a certification method to the $mathcal{P}$-decision problem; i.e., decide if an input graph belongs to the class $mathcal{P}$. We conclude this talk by proposing a general framework to talk about these expression systems. This framework allows us to formalize the question, what can be certified this way?
Based on a joint work with César Hernández-Cruz.

Alexander Clifton, Ramsey Theory for Diffsequences
2022-09-27 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Van der Waerden’s theorem states that any coloring of $mathbb{N}$ with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number $W(r,k)$ which is the smallest $n$ such that any $r$-coloring of ${1,2,cdots,n}$ guarantees the presence of a monochromatic arithmetic progression of length $k$.
It is natural to ask what other arithmetic structures exhibit van der Waerden-type results. One notion, introduced by Landman and Robertson, is that of a $D$-diffsequence, which is an increasing sequence $a_1<a_2<cdots<a_k$ in which the consecutive differences $a_i-a_{i-1}$ all lie in some given set $D$. We say that $D$ is $r$-accessible if every $r$-coloring of $mathbb{N}$ contains arbitrarily long monochromatic $D$-diffsequences. When $D$ is $r$-accessible, we define $Delta(D,k;r)$ as the smallest $n$ such that any $r$-coloring of ${1,2,cdots,n}$ guarantees the presence of a monochromatic $D$-diffsequence of length $k$.
One question of interest is to determine the possible behaviors of $Delta$ as a function of $k$. In this talk, we will demonstrate that is possible for $Delta(D,k;r)$ to grow faster than polynomial in $k$. We will also discuss a broad class of $D$’s which are not $2$-accessible.

Mehtaab Sawhney, Anticoncentration in Ramsey graphs and a proof of the Erdős-McKay conjecture
2022-09-21 16:30 - 17:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
An $n$-vertex graph is called $C$-Ramsey if it has no clique or independent set of size $Clog_2 n$ (i.e., if it has near-optimal Ramsey behavior). We study edge-statistics in Ramsey graphs, in particular obtaining very precise control of the distribution of the number of edges in a random vertex subset of a $C$-Ramsey graph. One of the consequences of our result is the resolution of an old conjecture of Erdős and McKay, for which Erdős offered one of his notorious monetary prizes and the proof involves a wide range of different tools from Fourier analysis, random matrix theory, the theory of Boolean functions, probabilistic combinatorics, and low-rank approximation.
Joint w. Matthew Kwan, Ashwin Sah, and Lisa Sauermann

Sebastian Wiederrecht, Killing a vortex
2022-09-13 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
The Structural Theorem of the Graph Minors series of Robertson and Seymour asserts that, for every $tinmathbb{N},$ there exists some constant $c_{t}$ such that every $K_{t}$-minor-free graph admits a tree decomposition whose torsos can be transformed, by the removal of at most $c_{t}$ vertices, to graphs that can be seen as the union of some graph that is embeddable to some surface of Euler genus at most $c_{t}$ and “at most $c_{t}$ vortices of depth $c_{t}$”. Our main combinatorial result is a “vortex-free” refinement of the above structural theorem as follows: we identify a (parameterized) graph $H_{t}$, called shallow vortex grid, and we prove that if in the above structural theorem we replace $K_{t}$ by $H_{t},$ then the resulting decomposition becomes “vortex-free”. Up to now, the most general classes of graphs admitting such a result were either bounded Euler genus graphs or the so called single-crossing minor-free graphs. Our result is tight in the sense that, whenever we minor-exclude a graph that is not a minor of some $H_{t},$ the appearance of vortices is unavoidable. Using the above decomposition theorem, we design an algorithm that, given an $H_{t}$-minor-free graph $G$, computes the generating function of all perfect matchings of $G$ in polynomial time. This algorithm yields, on $H_{t}$-minor-free graphs, polynomial algorithms for computational problems such as the {dimer problem, the exact matching problem}, and the computation of the permanent. Our results, combined with known complexity results, imply a complete characterization of minor-closed graphs classes where the number of perfect matchings is polynomially computable: They are exactly those graph classes that do not contain every $H_{t}$ as a minor. This provides a sharp complexity dichotomy for the problem of counting perfect matchings in minor-closed classes.
This is joint work with Dimitrios M. Thilikos.

Dömötör Pálvölgyi, C-P3O: Orientation of convex sets and other good covers
2022-09-07 16:30 - 17:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a natural interiority condition. Such systems, P3O (partial 3-order), are a natural generalization of posets, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets, p-P3O, and P3O that emerge from convex sets, C-P3O, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O’s.
Based on joint work with Agoston, Damasdi, and Keszegh:
https://arxiv.org/abs/2206.01721
https://arxiv.org/abs/2206.01723

Bjarne Schülke, A local version of Katona's intersection theorem
2022-09-06 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Katona’s intersection theorem states that every intersecting family $mathcal Fsubseteq[n]^{(k)}$ satisfies $vertpartialmathcal Fvertgeqvertmathcal Fvert$, where $partialmathcal F={Fsetminus x:xin Finmathcal F}$ is the shadow of $mathcal F$.
Frankl conjectured that for $n>2k$ and every intersecting family $mathcal Fsubseteq [n]^{(k)}$, there is some $iin[n]$ such that $vert partial mathcal F(i)vertgeq vertmathcal F(i)vert$, where $mathcal F(i)={Fsetminus i:iin Finmathcal F}$ is the link of $mathcal F$ at $i$.
Here, we prove this conjecture in a very strong form for $n> binom{k+1}{2}$.
In particular, our result implies that for any $jin[k]$, there is a $j$-set ${a_1,dots,a_j}in[n]^{(j)}$ such that [ vert partial mathcal F(a_1,dots,a_j)vertgeq vertmathcal F(a_1,dots,a_j)vert.]A similar statement is also obtained for cross-intersecting families.

Raphael Steiner, Congruence-constrained subdivisions in digraphs
2022-08-31 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
I will present the short proof from [1] that for every digraph F and every assignment of pairs of integers $(r_e,q_e)_{ein A(F)}$ to its arcs, there exists an integer $N$ such that every digraph D with dichromatic number at least $N$ contains a subdivision of $F$ in which $e$ is subdivided into a directed path of length congruent to $r_e$ modulo $q_e$ for every $e in A(F)$. This generalizes to the directed setting the analogous result by Thomassen for undirected graphs and at the same time yields a novel proof of his result. I will also talk about how a hypergraph coloring result from [2] may help to obtain good bounds on $N$ in the special case when $F$ is subcubic.
[1] https://arxiv.org/abs/2208.06358
[2] https://arxiv.org/abs/2206.13635

Jun Gao, Number of (k-1)-cliques in k-critical graph
2022-08-30 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We prove that for $n>kgeq 3$, if $G$ is an $n$-vertex graph with chromatic number $k$ but any its proper subgraph has smaller chromatic number, then $G$ contains at most $n-k+3$ copies of cliques of size $k-1$. This answers a problem of Abbott and Zhou and provides a tight bound on a conjecture of Gallai.
This is joint work with Jie Ma.

Brett Leroux, Expansion of random 0/1 polytopes
2022-08-25 10:00 - 11:00 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
A conjecture of Milena Mihail and Umesh Vazirani states that the edge expansion of the graph of every $0/1$ polytope is at least one. Any lower bound on the edge expansion gives an upper bound for the mixing time of a random walk on the graph of the polytope. Such random walks are important because they can be used to generate an element from a set of combinatorial objects uniformly at random. A weaker form of the conjecture of Mihail and Vazirani says that the edge expansion of the graph of a $0/1$ polytope in $mathbb{R}^d$ is greater than 1 over some polynomial function of $d$. This weaker version of the conjecture would suffice for all applications. Our main result is that the edge expansion of the graph of a random $0/1$ polytope in $mathbb{R}^d$ is at least $frac{1}{12d}$ with high probability.
After discussing this result and the proof, we will mention some possible extensions. To conclude, we will discuss some related questions about the combinatorics of random polytopes, including the diameter problem.
This is joint work with Luis Rademacher.

Raul Lopes, Temporal Menger and related problems
2022-08-23 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
A temporal graph is a graph whose edges are available only at specific times. In this scenario, the only valid walks are the ones traversing adjacent edges respecting their availability, i.e. sequence of adjacent edges whose appearing times are non-decreasing.
Given a graph G and vertices s and t of G, Menger’s Theorem states that the maximum number of (internally) vertex disjoint s,t-paths is equal to the minimum size of a subset X for which G-X contains no s,t-path. This is a classical result in Graph Theory, taught in most basic Graph Theory courses, and it holds also when G is directed and when edge disjoint paths and edge cuts are considered instead. A direct translation of Menger’s Theorem to the temporal context has been known not to hold since an example was shown in the seminal paper by Kempe, Kleinberg and Kumar (STOC’00). In this talk, an overview of possible temporal versions of Menger’s Theorem will be discussed, as well as the complexity of the related problems.

Noleen Köhler, Testing first-order definable properties on bounded degree graphs
2022-08-16 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Property testers are probabilistic algorithms aiming to solve a decision problem efficiently in the context of big-data. A property tester for a property P has to decide (with high probability correctly) whether a given input graph has property P or is far from having property P while having local access to the graph. We study property testing of properties that are definable in first-order logic (FO) in the bounded-degree model. We show that any FO property that is defined by a formula with quantifier prefix ∃*∀* is testable, while there exists an FO property that is expressible by a formula with quantifier prefix ∀*∃* that is not testable. In the dense graph model, a similar picture is long known (Alon, Fischer, Krivelevich, Szegedy, Combinatorica 2000), despite the very different nature of the two models. In particular, we obtain our lower bound by a first-order formula that defines a class of bounded-degree expanders, based on zig-zag products of graphs.
This is joint work with Isolde Adler and Pan Peng.

Akash Kumar, Random walks and Forbidden Minors
2022-08-10 16:30 - 17:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
Random walks and spectral methods have had a strong influence on modern graph algorithms as evidenced by the extensive literature on the subject. In this talk, I will present how random walks helped make progress on algorithmic problems on planar graphs.
In particular, I show how random walk based (i.e., spectral) approaches led to progress on finding forbidden minors [K.-Seshadhri-Stolman, FOCS 2018] as well as on deciding planarity [K.-Seshadhri-Stolman, STOC 2019] in bounded degree graphs within the property testing framework. I will also cover how these approaches eventually led to progress on the so-called “efficient partition oracle” problem [K.-Seshadhri-Stolman, FOCS 2021].
The talk will assume minimal background by presenting a stand-alone story that should be of interest to students/researchers in computer science.

Eun Jung Kim (김은정), Directed flow-augmentation
2022-08-09 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We show a flow-augmentation algorithm in directed graphs: There exists a polynomial-time algorithm that, given a directed graph G, two integers $s,tin V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal st-cut $Z$ in $G$ of size at most $k$, with probability $2^{−operatorname{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph.
The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems:
(1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17],
(2) a number of weighted variants of classic directed cut problems, such as Weighted st-Cut, Weighted Directed Feedback Vertex Set, or Weighted Almost 2-SAT.
By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the List H-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable.
Joint work with Stefan Kratsch, Marcin Pilipczuk, Magnus Wahlström.

Lars Jaffke, Taming graphs with no large creatures and skinny ladders
2022-08-03 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $mathcal{G}$ there exists a constant $k$ such that no member of $mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor, then there exists a polynomial $p$ such that every $G in mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from $mathcal{G}$. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).
Joint work with Jakub Gajarský, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Paweł Rzążewski, and Uéverton S. Souza.

Seunghun Lee (이승훈), Inscribable order types
2022-08-01 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We call an order type inscribable if it is realized by a point configuration where all extreme points are all on a circle. In this talk, we investigate inscribability of order types. We first show that every simple order type with at most 2 interior points is inscribable, and that the number of such order types is $Theta(frac{4^n}{n^{3/2}})$. We further construct an infinite family of minimally uninscribable order types. The proof of uninscribability mainly uses Möbius transformations. We also suggest open problems around inscribability. This is a joint work with Michael Gene Dobbins.

Noam Lifshitz, Product free sets in the alternating group
2022-07-27 16:30 - 17:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
A subset of a group is said to be product free if it does not contain the product of two elements in it. We consider how large can a product free subset of $A_n$ be?
In the talk we will completely solve the problem by determining the largest product free subset of $A_n$.
Our proof combines a representation theoretic argument due to Gowers, with an analytic tool called hypercontractivity for global functions. We also make use of a dichotomy between structure and a pseudorandomness notion of functions over the symmetric group known as globalness.
Based on a joint work with Peter Keevash and Dor Minzer.

Jinyoung Park (박진영), Thresholds 2/2
2022-07-19 14:00 - 16:00 | Room B332, IBS (기초과학연구원)
Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its “expectation-threshold,” which is a natural (and often easy to calculate) lower bound on the threshold.
In the first talk on Monday, I will introduce the Kahn-Kalai Conjecture with some motivating examples and then briefly talk about the recent resolution of the Kahn-Kalai Conjecture due to Huy Pham and myself.
In the second talk on Tuesday, I will discuss our proof of the conjecture in detail.

Jinyoung Park (박진영), Thresholds 1/2
2022-07-18 16:30 - 17:30 | Room B332, IBS (기초과학연구원)

Kevin Hendrey, Product Structure of Graph Classes with Bounded Treewidth
2022-07-11 16:30 - 17:30 | Room B232, IBS (기초과학연구원)
The strong product $Gboxtimes H$ of graphs $G$ and $H$ is the graph on the cartesian product $V(G)times V(H)$ such that vertices $(v,w)$ and $(x,y)$ are adjacent if and only if $max{d_G(v,x),d_H(w,y)}=1$. Graph product structure theory aims to describe complicated graphs in terms of subgraphs of strong products of simpler graphs. This area of research was initiated by Dujmović, Joret, Micek, Morin, Ueckerdt and Wood, who showed that every planar graph is a subgraph of the strong product of a $Hboxtimes Pboxtimes K_3$ for some path $P$ and some graph $H$ of treewidth at most $3$. In this talk, I will discuss the product structure of various graph classes of bounded treewidth. As an example, we show that there is a function $f:mathbb{N}rightarrow mathbb{N}$ such that every planar graph of treewidth at most $k$ is a subgraph of $Hboxtimes K_{f(k)}$ for some graph $H$ of treewidth at most $3$.
This is based on joint work with Campbell, Clinch, Distel, Gollin, Hickingbotham, Huynh, Illingworth, Tamitegama, Tan and Wood.

Sepehr Hajebi, Holes, hubs and bounded treewidth
2022-07-07 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
A hole in a graph $G$ is an induced cycle of length at least four, and for every hole $H$ in $G$, a vertex $hin Gsetminus H$ is called a $t$-hub for $H$ if $h$ has at least $t$ neighbor in $H$. Sintiari and Trotignon were the first to construct graphs with arbitrarily large treewidth and no induced subgraph isomorphic to the “basic obstructions,” that is, a fixed complete graph, a fixed complete bipartite graph (with parts of equal size), all subdivisions of a fixed wall and line graphs of all subdivisions of a fixed wall. They named their counterexamples “layered wheels” for a good reason: layered wheels contain wheels in abundance, where a wheel means a hole with a $3$-hub. In accordance, one may ask whether graphs with no wheel and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. This was also disproved by a recent construction due to Davies. But holes with a $2$-hub cannot be avoided in graphs with large treewidth: graphs containing no hole with a $2$-hub and no induced subgraph isomorphic to the basic obstructions have bounded treewidth. I will present a proof of this result, and will also give an overview of related works.
Based on joint work with Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sophie Spirkl and Kristina Vušković.

Eric Vigoda, Computational phase transition and MCMC algorithms
2022-07-04 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
This talk will highlight recent results establishing a beautiful computational phase transition for approximate counting/sampling in (binary) undirected graphical models (such as the Ising model or on weighted independent sets). The computational problem is to sample from the equilibrium distribution of the model or equivalently approximate the corresponding normalizing factor known as the partition function. We show that when correlations die off on the infinite D-regular tree then the Gibbs sampler has optimal mixing time of $O(n log n)$ on any graph of maximum degree D, whereas when the correlations persist (in the limit) then the sampling/counting problem are NP-hard to approximate. The Gibbs sampler is a simple Markov Chain Monte Carlo (MCMC) algorithm. Key to these mixing results are a new technique known as spectral independence which considers the pairwise influence of vertices. We show that spectral independence implies an optimal convergence rate for a variety of MCMC algorithms.

Xizhi Liu, Hypergraph Turán problem: from 1 to ∞
2022-06-29 16:30 - 17:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
One interesting difference between (nondegenerate) Graph Turán problem and Hypergraph Turán problem is that the hypergraph families can have at least two very different extremal constructions. In this talk, we will look at some recent progress and approaches to constructing hypergraph families with at least two different extremal constructions.
Based on some joint work with Dhruv Mubayi, Christian Reiher, Jianfeng Hou, Heng Li, and Yixiao Zhang.

Ben Lund, Radial projections in finite space
2022-06-27 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Given a set $E$ and a point $y$ in a vector space over a finite field, the radial projection $pi_y(E)$ of $E$ from $y$ is the set of lines that through $y$ and points of $E$. Clearly, $|pi_y(E)|$ is at most the minimum of the number of lines through $y$ and $|E|$. I will discuss several results on the general question: For how many points $y$ can $|pi_y(E)|$ be much smaller than this maximum?
This is motivated by an analogous question in fractal geometry. The Hausdorff dimension of a radial projection of a set $E$ in $n$ dimensional real space will typically be the minimum of $n-1$ and the Hausdorff dimension of $E$. Several recent papers by authors including Matilla, Orponen, Liu, Shmerikin, and Wang consider the question: How large can the set of points with small radial projections be? This body of work has several important applications, including recent progress on the Falconer distance conjecture.
This is joint with Thang Pham and Vu Thi Huong Thu.

Chengfei Xie, On the packing densities of superballs in high dimensions
2022-06-22 16:30 - 17:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
The sphere packing problem asks for the densest packing of nonoverlapping equal-sized balls in the space. This is an old and difficult problem in discrete geometry. In this talk, we give a new proof for the result that for $ 1<p<2 $, the translative packing density of superballs (a generalization of $ell^p$ balls) in $mathbb{R}^n$ is $Omega(n/2^n)$.
This is joint work with Gennian Ge.

Amadeus Reinald, Twin-width and forbidden subdivisions
2022-06-13 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Twin-width is a recently introduced graph parameter based on vertex contraction sequences. On classes of bounded twin-width, problems expressible in FO logic can be solved in FPT time when provided with a sequence witnessing the bound. Classes of bounded twin-width are very diverse, notably including bounded rank-width, $Omega ( log (n) )$-subdivisions of graphs of size $n$, and proper minor closed classes. In this talk, we look at developing a structural understanding of twin-width in terms of induced subdivisions.
Structural characterizations of graph parameters have mostly looked at graph minors, for instance, bounded tree-width graphs are exactly those forbidding a large wall minor. An analogue in terms of induced subgraphs could be that, for sparse graphs, large treewidth implies the existence of an induced subdivision of a large wall. However, Sintiari and Trotignon have ruled out such a characterization by showing the existence of graphs with arbitrarily large girth avoiding any induced subdivision of a theta ($K_{2,3}$). Abrishami, Chudnovsky, Hajebi and Spirkl have recently shown that such (theta, triangle)-free classes have nevertheless logarithmic treewidth.
After an introduction to twin-width and its ties to vertex orderings, we show that theta-free graphs of girth at least 5 have bounded twin-width.
Joint work with Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé and Rémi Watrigant.

O-joung Kwon (권오정), Graph minor theory and beyond
2022-06-02 16:15 - 17:15 | Room 1501, Bldg. E6-1, KAIST
[Colloquium, Department of Mathematical Sciences, KAIST]
One of the important work in graph theory is the graph minor theory developed by Robertson and Seymour in 1980-2010. This provides a complete description of the class of graphs that do not contain a fixed graph H as a minor. Later on, several generalizations of H-minor free graphs, which are sparse, have been defined and studied. Also, similar topics on dense graph classes have been deeply studied. In this talk, I will survey topics in graph minor theory, and discuss related topics in structural graph theory.

Jeck Lim, Sums of linear transformations
2022-06-02 10:30 - 11:30 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
We show that if $L_1$ and $L_2$ are linear transformations from $mathbb{Z}^d$ to $mathbb{Z}^d$ satisfying certain mild conditions, then, for any finite subset $A$ of $mathbb{Z}^d$, [ |L_1 A+L_2 A|geq (|det(L_1)|^{1/d}+|det(L_2)|^{1/d})^d |A|- o(|A|).] This result corrects and confirms the two-summand case of a conjecture of Bukh and is best possible up to the lower-order term for many choices of $L_1$ and $L_2$. As an application, we prove a lower bound for $|A + lambda cdot A|$ when $A$ is a finite set of real numbers and $lambda$ is an algebraic number.
Joint work with David Conlon.

Hongseok Yang (양홍석), Learning Symmetric Rules with SATNet
2022-05-30 16:30 - 17:30 | 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.
