Noleen Köhler, Testing first-order definable properties on bounded degree graphs
2022-08-16 16:30 - 17:30 (Asia/Seoul) | 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.

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.

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.

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.

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

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.

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

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.

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

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.

Santiago Guzmán-Pro, Local expressions of graphs classes
2022-09-29 10:00 - 11:00 | 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.

Zixiang Xu (徐子翔), On the degenerate Turán problems
2022-10-04 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
For a graph $F$, the Turán number is the maximum number of edges in an $n$-vertex simple graph not containing $F$. The celebrated Erdős-Stone-Simonovits Theorem gives that [ text{ex}(n,F)=bigg(1-frac{1}{chi(F)-1}+o(1)bigg)binom{n}{2},] where $chi(F)$ is the chromatic number of $H$. This theorem asymptotically solves the problem when $chi(F)geqslant 3$. In case of bipartite graphs $F$, not even the order of magnitude is known in general. In this talk, I will introduce some recent progress on Turán numbers of bipartite graphs and related generalizations and discuss several methods developed in recent years. Finally, I will introduce some interesting open problems on this topic.

Konstantin Tikhomirov, A remark on the Ramsey number of the hypercube
2022-10-06 10:00 - 11:00 | Zoom ID: 870 0312 9412 (ibsecopro) [CLOSED]
A well-known conjecture of Burr and Erdős asserts that the Ramsey number $r(Q_n)$ of the hypercube $Q_n$ on $2^n$ vertices is of the order $O(2^n)$. In this paper, we show that $r(Q_n)=O(2^{2n−cn})$ for a universal constant $c>0$, improving upon the previous best-known bound $r(Q_n)=O(2^{2n})$, due to Conlon, Fox, and Sudakov.

Nika Salia, Exact results for generalized extremal problems forbidding an even cycle
2022-10-11 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We determine the maximum number of copies of $K_{s,s}$ in a $C_{2s+2}$-free $n$-vertex graph for all integers $s ge 2$ and sufficiently large $n$. Moreover, for $sin{2,3}$ and any integer $n$ we obtain the maximum number of cycles of length $2s$ in an $n$-vertex $C_{2s+2}$-free bipartite graph.
This is joint work with Ervin Győri (Renyi Institute), Zhen He (Tsinghua University), Zequn Lv (Tsinghua University), Casey Tompkins (Renyi Institute), Kitti Varga (Technical University of Budapest BME), and Xiutao Zhu (Nanjing University).

Xavier Goaoc, Order types and their symmetries
2022-10-13 16:15 - 17:15 | Room 1501, Bldg. E6-1, KAIST
Order types are a combinatorial classification of finite point sets used in discrete and computational geometry. This talk will give an introduction to these objects and their analogue for the projective plane, with an emphasis on their symmetry groups.
This is joint work with Emo Welzl.

Florent Koechlin, Uniform random expressions lack expressivity
2022-10-18 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
In computer science, random expressions are commonly used to analyze algorithms, either to study their average complexity, or to generate benchmarks to test them experimentally. In general, these approaches only consider the expressions as purely syntactic trees, and completely ignore their semantics — i.e. the mathematical object represented by the expression.
However, two different expressions can be equivalent (for example “0*(x+y)” and “0” represent the same expression, the null expression). Can these redundancies question the relevance of the analyses and tests that do not take into account the semantics of the expressions?
I will present how the uniform distribution over syntactic expression becomes completely degenerate when we start taking into account their semantics, in a very simple but common case where there is an absorbing element. If time permits it, I will briefly explain why the BST distribution offers more hope.
This is a joint work with Cyril Nicaud and Pablo Rotondo.

Dabeen Lee (이다빈), Non-smooth and Hölder-smooth submodular optimization
2022-10-27 16:15 - 17:15 | Room 1501, Bldg. E6-1, KAIST
We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an [(1−1/e)OPT−ϵ] guarantee when the function is monotone and Hölder-smooth, meaning that it admits a Hölder-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an [(1/2)OPT−ϵ] guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least (1/2)OPT−ϵ. For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is Hölder-smooth, for which we may apply both the continuous greedy method and the mirror-prox method.
Joint work with Duksang Lee and Nam Ho-Ngyuen.

Jungho Ahn (안정호), Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
2022-11-08 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Let $mathcal{F}$ be a family of graphs, and let $p$ and $r$ be nonnegative integers.
The $(p,r,mathcal{F})$-Covering problem asks whether for a graph $G$ and an integer $k$, there exists a set $D$ of at most $k$ vertices in $G$ such that $G^psetminus N_G^r[D]$ has no induced subgraph isomorphic to a graph in $mathcal{F}$, where $G^p$ is the $p$-th power of $G$ and $N^r_G[D]$ is the set of all vertices in $G$ at distance at most $r$ from $D$ in $G$. The $(p,r,mathcal{F})$-Packing problem asks whether for a graph $G$ and an integer $k$, $G^p$ has $k$ induced subgraphs $H_1,ldots,H_k$ such that each $H_i$ is isomorphic to a graph in $mathcal{F}$, and for distinct $i,jin {1, ldots, k}$, the distance between $V(H_i)$ and $V(H_j)$ in $G$ is larger than $r$. The $(p,r,mathcal{F})$-Covering problem generalizes Distance-$r$ Dominating Set and Distance-$r$ Vertex Cover, and the $(p,r,mathcal{F})$-Packing problem generalizes Distance-$r$ Independent Set and Distance-$r$ Matching. By taking $(p’,r’,mathcal{F}’)=(pt, rt, mathcal{F})$, we may formulate the $(p,r,mathcal{F})$-Covering and $(p, r, mathcal{F})$-Packing problems on the $t$-th power of a graph. Moreover, $(1,0,mathcal{F})$-Covering is the $mathcal{F}$-Free Vertex Deletion problem, and $(1,0,mathcal{F})$-Packing is the Induced-$mathcal{F}$-Packing problem.
We show that for every fixed nonnegative integers $p,r$ and every fixed nonempty finite family $mathcal{F}$ of connected graphs, the $(p,r,mathcal{F})$-Covering problem with $pleq2r+1$ and the $(p,r,mathcal{F})$-Packing problem with $pleq2lfloor r/2rfloor+1$ admit almost linear kernels on every nowhere dense class of graphs, and admit linear kernels on every class of graphs with bounded expansion, parameterized by the solution size $k$. We obtain the same kernels for their annotated variants. As corollaries, we prove that Distance-$r$ Vertex Cover, Distance-$r$ Matching, $mathcal{F}$-Free Vertex Deletion, and Induced-$mathcal{F}$-Packing for any fixed finite family $mathcal{F}$ of connected graphs admit almost linear kernels on every nowhere dense class of graphs and linear kernels on every class of graphs with bounded expansion. Our results extend the results for Distance-$r$ Dominating Set by Drange et al. (STACS 2016) and Eickmeyer et al. (ICALP 2017), and the result for Distance-$r$ Independent Set by Pilipczuk and Siebertz (EJC 2021).
This is joint work with Jinha Kim and O-joung Kwon.

Hugo Jacob, On the parameterized complexity of computing tree-partitions
2022-11-09 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
Following some recent FPT algorithms parameterized by the width of a given tree-partition due to Bodlaender, Cornelissen, and van der Wegen, we consider the parameterized problem of computing a decomposition. We prove that computing an optimal tree-partition is XALP-complete, which is likely to exclude FPT algorithms. However, we prove that computing a tree-partition of approximate width is tractable using a relatively simple sketch. This is sufficient to remove the requirement of having a given tree-partition for FPT algorithms. Our simple sketch can be adapted for several regimes within polynomial time and FPT time. Furthermore, we adapt some simple structural results about the tree-partition-width of subdivisions, and use them to compare tree-cut width and tree-partition-width.
Based on joint work with Hans Bodlaender and Carla Groenland.

Sebastian Wiederrecht, Excluding single-crossing matching minors in bipartite graphs
2022-11-15 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
By a seminal result of Valiant, computing the permanent of (0, 1)-matrices is, in general, #P-hard. In 1913 Pólya asked for which (0, 1)-matrices A it is possible to change some signs such that the permanent of A equals the determinant of the resulting matrix. In 1975, Little showed these matrices to be exactly the biadjacency matrices of bipartite graphs excluding $K_{3,3}$ as a matching minor. This was turned into a polynomial time algorithm by McCuaig, Robertson, Seymour, and Thomas in 1999. However, the relation between the exclusion of some matching minor in a bipartite graph and the tractability of the permanent extends beyond K3,3. Recently it was shown that the exclusion of any planar bipartite graph as a matching minor yields a class of bipartite graphs on which the permanent of the corresponding (0, 1)-matrices can be computed efficiently.
In this paper we unify the two results above into a single, more general result in the style of the celebrated structure theorem for single-crossing minor-free graphs. We identify a class of bipartite graphs strictly generalising planar bipartite graphs and $K_{3,3}$ which includes infinitely many non-Pfaffian graphs. The exclusion of any member of this class as a matching minor yields a structure that allows for the efficient evaluation of the permanent. Moreover, we show that the evaluation of the permanent remains #P-hard on bipartite graphs which exclude $K_{5,5}$ as a matching minor. This establishes a first computational lower bound for the problem of counting perfect matchings on matching minor closed classes. As another application of our structure theorem, we obtain a strict generalisation of the algorithm for the k-vertex disjoint directed paths problem on digraphs of bounded directed treewidth.
This is joint work with Archontia Giannopoulou and Dimitrios Thilikos.

Chong Shangguan (上官冲), On the sparse hypergraph problem of Brown, Erdős and Sós
2022-11-17 10:00 - 11:00 | Zoom ID: 224 221 2686 (ibsecopro)
For fixed integers $rge 3, ege 3$, and $vge r+1$, let $f_r(n,v,e)$ denote the maximum number of edges in an $n$-vertex $r$-uniform hypergraph in which the union of arbitrary $e$ distinct edges contains at least $v+1$ vertices. In 1973, Brown, Erdős and Sós initiated the study of the function $f_r(n,v,e)$ and they proved that $Omega(n^{frac{er-v}{e-1}})=f_r(n,v,e)=O(n^{lceilfrac{er-v}{e-1}rceil})$. We will survey the state-of-art results about the study of $f_r(n,er-(e-1)k+1,e)$ and $f_r(n,er-(e-1)k,e)$, where $r>kge 2$ and $ege 3$. Although these two functions have been extensively studied, many interesting questions remain open.

Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems
2022-11-22 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
A linear $3$-graph is called a (3-)hypertree if there exists exactly one path between each pair of two distinct vertices. A linear $3$-graph is called a Steiner triple system if each pair of two distinct vertices belong to a unique edge.
A simple greedy algorithm shows that every $n$-vertex Steiner triple system $G$ contains all hypertrees $T$ of order at most $frac{n+3}{2}$. On the other hand, it is not immediately clear whether one can always find larger hypertrees in $G$. In 2011, Goodall and de Mier proved that a Steiner triple system $G$ contains at least one spanning tree. However, one cannot expect the Steiner triple system to contain all possible spanning trees, as there are many Steiner triple systems that avoid numerous spanning trees as subgraphs. Hence it is natural to wonder how much one can improve the bound from the greedy algorithm.
Indeed, Elliott and Rödl conjectured that an $n$-vertex Steiner triple system $G$ contains all hypertrees of order at most $(1-o(1))n$. We prove the conjecture by Elliott and Rödl.
This is joint work with Jaehoon Kim, Joonkyung Lee, and Abhishek Methuku.

The 2nd Workshop on Developments in Combinatorics
2022-11-28 - 2022-11-29 | Zoom ID: 346 934 4087 (202209)
Official website (with the abstract)
Online workshop “Developments in Combinatorics”

Invited Speakers
Nov. 28 Monday
Jie Han, Beijing Institute of Technology
15:30 Seoul, 14:30 Beijing, 06:30 UK, 07:30 EU
Joonkyung Lee (이준경), Hanyang University
16:10 Seoul, 15:10 Beijing, 07:10 UK, 08:10 EU
Lior Gishboliner, ETH Zürich
16:50 Seoul, 15:50 Beijing, 07:50 UK, 08:50 EU
Alex Scott, University of Oxford
17:40 Seoul, 16:40 Beijing, 08:40 UK, 09:40 EU
Dongyeap Kang (강동엽), University of Birmingham
18:20 Seoul, 17:20 Beijing, 09:20 UK, 10:20 EU
Nov. 29 Tuesday
Chong Shangguan, Shandong University
15:30 Seoul, 14:30 Beijing, 06:30 UK, 07:30 EU
Zdeněk Dvořák, Charles University
16:10 Seoul, 15:10 Beijing, 07:10 UK, 08:10 EU
Andrzej Grzesik, Jagiellonian University
16:50 Seoul, 15:50 Beijing, 07:50 UK, 08:50 EU
Imre Leader, University of Cambridge
17:40 Seoul, 16:40 Beijing, 08:40 UK, 09:40 EU
Jozef Skokan, The London School of Ecnomics and Political Science
18:20 Seoul, 17:20 Beijing, 09:20 UK, 10:20 EU
Organizers

Hong Liu
Guanghui Wang
Bingyu Luan

Sponsors

IBS Extremal Combinatorics and Probability Group
Shandong University

Cosmin Pohoata, Convex polytopes from fewer points
2022-12-01 10:00 - 11:00 | Zoom ID: 224 221 2686 (ibsecopro)
Finding the smallest integer $N=ES_d(n)$ such that in every configuration of $N$ points in $mathbb{R}^d$ in general position, there exist $n$ points in convex position is one of the most classical problems in extremal combinatorics, known as the Erdős-Szekeres problem. In 1935, Erdős and Szekeres famously conjectured that $ES_2(n)=2^{n−2}+1$ holds, which was nearly settled by Suk in 2016, who showed that $ES_2(n)≤2^{n+o(n)}$. We discuss a recent proof that $ES_d(n)=2^{o(n)}$ holds for all $d≥3$. Joint work with Dmitrii Zakharov.

Giannos Stamoulis, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes
2022-12-06 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
The disjoint paths logic, FOL+DP, is an extension of First Order Logic (FOL) with the extra atomic predicate $mathsf{dp}_k(x_1,y_1,ldots,x_k,y_k),$ expressing the existence of internally vertex-disjoint paths between $x_i$ and $y_i,$ for $iin {1,ldots, k}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every minor-closed graph class, model-checking for FOL+DP can be done in quadratic time. We also introduce an extension of FOL+DP, namely the scattered disjoint paths logic, FOL+SDP, where we further consider the atomic predicate $mathsf{s-sdp}_k(x_1,y_1,ldots,x_k,y_k),$ demanding that the disjoint paths are within distance bigger than some fixed value $s$. Using the same technique we prove that model-checking for FOL+SDP can be done in quadratic time on classes of graphs with bounded Euler genus.
Joint work with Petr A. Golovach and Dimitrios M. Thilikos.

Maya Sankar, Homotopy and the Homomorphism Threshold of Odd Cycles
2022-12-15 10:00 - 11:00 | Zoom ID: 224 221 2686 (ibsecopro)
Fix $r ge 2$ and consider a family F of $C_{2r+1}$-free graphs, each having minimum degree linear in its number of vertices. Such a family is known to have bounded chromatic number; equivalently, each graph in F is homomorphic to a complete graph of bounded size. We disprove the analogous statement for homomorphic images that are themselves $C_{2r+1}$-free. Specifically, we construct a family of dense $C_{2r+1}$-free graphs with no $C_{2r+1}$-free homomorphic image of bounded size. This provides the first nontrivial lower bound on the homomorphism threshold of longer odd cycles and answers a question of Ebsen and Schacht.
Our proof relies on a graph-theoretic analogue of homotopy equivalence, which allows us to analyze the relative placement of odd closed walks in a graph. This notion has surprising connections to the neighborhood complex, and opens many further interesting questions.

Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets
2022-12-28 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Various types of independent sets have been studied for decades. As an example, the minimum number of maximal independent sets in a connected graph of given order is easy to determine (hint; the answer is written in the stars). When considering this question for twin-free graphs, it becomes less trivial and one discovers some surprising behaviour. The minimum number of maximal independent sets turns out to be;

logarithmic in the number of vertices for arbitrary graphs,
linear for bipartite graphs
and exponential for trees.

Finally, we also have a sneak peek on the 69-conjecture, part of an unpublished work on an inverse problem on the number of independent sets.
In this talk, we will focus on the basic concepts, the intuition behind the statements and sketch some proof ideas.
The talk is based on joint work with Stephan Wagner, with the main chunk being available at arXiv:2211.04357.

Youngho Yoo (유영호), Approximating TSP walks in subcubic graphs
2023-01-03 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
The Graphic Travelling Salesman Problem is the problem of finding a spanning closed walk (a TSP walk) of minimum length in a given connected graph. The special case of the Graphic TSP on subcubic graphs has been studied extensively due to their worst-case behaviour in the famous $frac{4}{3}$-integrality-gap conjecture on the “subtour elimination” linear programming relaxation of the Metric TSP.
We prove that every simple 2-connected subcubic graph on $n$ vertices with $n_2$ vertices of degree 2 has a TSP walk of length at most $frac{5n+n_2}{4}-1$, confirming a conjecture of Dvořák, Král’, and Mohar. This bound is best possible and we characterize the extremal subcubic examples meeting this bound. We also give a quadratic time combinatorial algorithm to find such a TSP walk. In particular, we obtain a $frac{5}{4}$-approximation algorithm for the Graphic TSP on cubic graphs. Joint work with Michael Wigal and Xingxing Yu.

Mamadou Moustapha Kanté, MSOL-Definable decompositions
2023-01-10 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
I will first introduce the notion of recognisability of languages of terms and then its extensions to sets of relational structures. In a second step, I will discuss relations with decompositions of graphs/matroids and why their MSOL-definability is related to understanding recognisable sets. I will finally explain how to define in MSOL branch-decompositions for finitely representable matroids of bounded path-width. This is joint work with Rutger Campbell, Bruno Guillon, Eun Jung Kim, and Sang-il Oum.

Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins
2023-01-17 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We introduce the notion of delineation. A graph class $mathcal C$ is said delineated by twin-width (or simply, delineated) if for every hereditary closure $mathcal D$ of a subclass of $mathcal C$, it holds that $mathcal D$ has bounded twin-width if and only if $mathcal D$ is monadically dependent. An effective strengthening of delineation for a class $mathcal C$ implies that tractable FO model checking on $mathcal C$ is perfectly understood: On hereditary closures of subclasses $mathcal D$ of $mathcal C$, FO model checking on $mathcal D$ is fixed-parameter tractable (FPT) exactly when $mathcal D$ has bounded twin-width. Ordered graphs [BGOdMSTT, STOC ’22] and permutation graphs [BKTW, JACM ’22] are effectively delineated, while subcubic graphs are not. On the one hand, we prove that interval graphs, and even, rooted directed path graphs are delineated. On the other hand, we observe or show that segment graphs, directed path graphs (with arbitrarily many roots), and visibility graphs of simple polygons are not delineated.
In an effort to draw the delineation frontier between interval graphs (that are delineated) and axis-parallel two-lengthed segment graphs (that are not), we investigate the twin-width of restricted segment intersection classes. It was known that (triangle-free) pure axis-parallel unit segment graphs have unbounded twin-width [BGKTW, SODA ’21]. We show that $K_{t,t}$-free segment graphs, and axis-parallel $H_t$-free unit segment graphs have bounded twin-width, where $H_t$ is the half-graph or ladder of height $t$. In contrast, axis-parallel $H_4$-free two-lengthed segment graphs have unbounded twin-width. We leave as an open question whether unit segment graphs are delineated.
More broadly, we explore which structures (large bicliques, half-graphs, or independent sets) are responsible for making the twin-width large on the main classes of intersection and visibility graphs. Our new results, combined with the FPT algorithm for first-order model checking on graphs given with $O(1)$-sequences [BKTW, JACM ’22], give rise to a variety of algorithmic win-win arguments. They all fall in the same framework: If $p$ is an FO definable graph parameter that effectively functionally upperbounds twin-width on a class C, then $p(G) ge k$ can be decided in FPT time $f(k)cdot |V (G)|O(1)$. For instance, we readily derive FPT algorithms for k-Ladder on visibility graphs of 1.5D terrains, and k-Independent Set on visibility graphs of simple polygons. This showcases that the theory of twin-width can serve outside of classes of bounded twin-width.
Joint work with Édouard Bonnet, Dibyayan Chakraborty, Eun Jung Kim, Raul Lopes and Stéphan Thomassé.
