Florent Koechlin, Uniform random expressions lack expressivity
2022-10-18 16:30 - 17:30 (Asia/Seoul) | 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.

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é.

Pedro Montealegre, A Meta-Theorem for Distributed Certification
2023-01-19 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
Distributed certification, whether it be proof-labeling schemes, locally checkable proofs, etc., deals with the issue of certifying the legality of a distributed system with respect to a given boolean predicate. A certificate is assigned to each process in the system by a non-trustable oracle, and the processes are in charge of verifying these certificates, so that two properties are satisfied: completeness, i.e., for every legal instance, there is a certificate assignment leading all processes to accept, and soundness, i.e., for every illegal instance, and for every certificate assignment, at least one process rejects. The verification of the certificates must be fast, and the certificates themselves must be small.
A large quantity of results have been produced in this framework, each aiming at designing a distributed certification mechanism for specific boolean predicates. In this talk, I will present a “meta-theorem”, applying to many boolean predicates at once. Specifically, I will show that, for every boolean predicate on graphs definable in the monadic second-order (MSO) logic of graphs, there exists a distributed certification mechanism using certificates on $O(log^2 n)$ bits in n-node graphs of bounded treewidth, with a verification protocol involving a single round of communication between neighbors.

Jan Hladký, Invitation to graphons
2023-01-25 16:30 - 17:30 | Zoom ID: 224 221 2686 (ibsecopro)
The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very fruitful limit perspective on graphs. The central objects of this theory, so-called graphons, are suitable measurable counterparts to graphs. In the talk, I will outline the syllabus of a hypothetical first course in graphon theory, in particular introducing versions of all the aforementioned concepts in the graphon setting. Based on work with Doležal, Hu, Máthé, Piguet, Rocha.

Abhishek Methuku, A proof of the Erdős–Faber–Lovász conjecture
2023-01-31 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
The Erdős–Faber–Lovász conjecture (posed in 1972) states that the chromatic index of any linear hypergraph on n vertices is at most n. In this talk, I will sketch a proof of this conjecture for every large n. Joint work with D. Kang, T. Kelly, D. Kühn and D. Osthus.

Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width
2023-02-01 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
We show that there is no $2^{o(k^2)} n^{O(1)}$ time algorithm for Independent Set on $n$-vertex graphs with rank-width $k$, unless the Exponential Time Hypothesis (ETH) fails. Our lower bound matches the $2^{O(k^2)} n^{O(1)}$ time algorithm given by Bui-Xuan, Telle, and Vatshelle [Discret. Appl. Math., 2010] and it answers the open question of Bergougnoux and Kanté [SIAM J. Discret. Math., 2021]. We also show that the known $2^{O(k^2)} n^{O(1)}$ time algorithms for Weighted Dominating Set, Maximum Induced Matching and Feedback Vertex Set parameterized by rank-width $k$ are optimal assuming ETH. Our results are the first tight ETH lower bounds parameterized by rank-width that do not follow directly from lower bounds for $n$-vertex graphs.
This is a joint work with Tuukka Korhonen and Jesper Nederlof.
Accepted to STACS 2023 and available on arXiv https://arxiv.org/abs/2210.02117

Raphael Steiner, Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs
2023-02-14 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Hadwiger’s famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd [Bull. London Math. Soc. 29, (1997), pp. 139-144] conjectured the following strengthening of Hadwiger’s conjecture: If G is a t-chromatic graph and S⊆V(G) takes all colors in every t-coloring of G, then G contains a $K_t$-minor rooted at S. We prove this conjecture in the first open case of t=4. Notably, our result also directly implies a stronger version of Hadwiger’s conjecture for 5-chromatic graphs as follows: Every 5-chromatic graph contains a $K_5$-minor with a singleton branch-set. In fact, in a 5-vertex-critical graph we may specify the singleton branch-set to be any vertex of the graph. Joint work with Anders Martinsson (ETH).

Robert Hickingbotham, Treewidth, Circle Graphs and Circular Drawings
2023-02-15 16:30 - 17:30 | Zoom ID: 869 4632 6610 (ibsdimag)
A circle graph is an intersection graph of a set of chords of a circle. In this talk, I will describe the unavoidable induced subgraphs of circle graphs with large treewidth. This includes examples that are far from the `usual suspects’. Our results imply that treewidth and Hadwiger number are linearly tied on the class of circle graphs, and that the unavoidable induced subgraphs of a vertex-minor-closed class with large treewidth are the usual suspects if and only if the class has bounded rank-width. I will also discuss applications of our results to the treewidth of graphs $G$ that have a circular drawing whose crossing graph is well-behaved in some way. In this setting, our results show that if the crossing graph is $K_t$-minor-free, then $G$ has treewidth at most $12t-23$ and has no $K_{2,4t}$-topological minor. On the other hand, I’ll present a construction of graphs with arbitrarily large Hadwiger number that have circular drawings whose crossing graphs are $2$-degenerate. This is joint work with Freddie Illingworth, Bojan Mohar, and David R. Wood

Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation
2023-02-21 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We show fixed-parameter tractability of the Directed Multicut problem with three terminal pairs (with a randomized algorithm). This problem, given a directed graph $G$, pairs of vertices (called terminals) $(s_1,t_1)$, $(s_2,t_2)$, and $(s_3,t_3)$, and an integer $k$, asks to find a set of at most $k$ non-terminal vertices in $G$ that intersect all $s_1t_1$-paths, all $s_2t_2$-paths, and all $s_3t_3$-paths. The parameterized complexity of this case has been open since Chitnis, Cygan, Hajiaghayi, and Marx proved fixed-parameter tractability of the 2-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlström proved the W[1]-hardness of the 4-terminal-pairs case at SODA 2016.
On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlström, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomassé, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendez, Simon, Thomassé, Toruńczyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced.

Daniel Altman, On an arithmetic Sidorenko conjecture, and a question of Alon
2023-02-22 17:00 - 18:00 | Zoom ID: 224 221 2686 (ibsecopro)
Let $G=mathbb{F}_p^n$. Which systems of linear equations $Psi$ have the property that amongst all subsets of $G$ of fixed density, random subsets minimise the number of solutions to $Psi$? This is an arithmetic analogue of a well-known conjecture of Sidorenko in graph theory, which has remained open and of great interest since the 1980s. We will discuss some recent results along these lines, with particular focus on some of the ideas behind a negative answer to a related question of Alon.

Maya Sankar, The Turán Numbers of Homeomorphs
2023-02-28 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Let $X$ be a 2-dimensional simplicial complex. Denote by $text{ex}_{hom}(n,X)$ the maximum number of 2-simplices in an $n$-vertex simplicial complex that has no sub-simplicial complex homeomorphic to $X$. The asymptotics of $text{ex}_{hom}(n,X)$ have recently been determined for all surfaces $X$. I will discuss these results, as well as ongoing work bounding $text{ex}_{hom}(n,X)$ for arbitrary 2-dimensional simplicial complexes $X$.

Eunjin Oh (오은진), Parameterized algorithms for the planar disjoint paths problem
2023-03-07 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Given an undirected planar graph $G$ with $n$ vertices and a set $T$ of $k$ pairs $(s_i,t_i)_{i=1}^k$ of vertices, the goal of the planar disjoint paths problem is to find a set $mathcal P$ of $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all indices $iin{1,ldots,k}$. This problem has been studied extensively due to its numerous applications such as VLSI layout and circuit routing. However, this problem is NP-complete even for grid graphs. This motivates the study of this problem from the viewpoint of parameterized algorithms.
In this talk, I will present a $2^{O(k^2)}n$-time algorithm for the planar disjoint paths problem. This improves the two previously best-known algorithms: $2^{2^{O(k)}}n$-time algorithm [Discrete Applied Mathematics 1995] and $2^{O(k^2)}n^6$-time algorithm [STOC 2020].
This is joint work with Kyungjin Cho and Seunghyeok Oh.

Marcelo Sales, On Pisier type problems
2023-03-09 10:00 - 11:00 | Zoom ID: 224 221 2686 (ibsecopro)
A subset $Asubseteq mathbb Z$ of integers is free if for every two distinct subsets $B, B’subseteq A$ we have [ sum_{bin B}b
eq sum_{b’in B’} b’.]Pisier asked if for every subset $Asubseteq mathbb Z$ of integers the following two statement are equivalent:
(i) $A$ is a union of finitely many free sets.
(ii) There exists $epsilon>0$ such that every finite subset $Bsubseteq A$ contains a free subset $Csubseteq B$ with $|C|geq epsilon |B|$.
In a more general framework, the Pisier question can be seen as the problem of determining if statements (i) and (ii) are equivalent for subsets of a given structure with prescribed property. We study the problem for several structures including $B_h$-sets, arithmetic progressions, independent sets in hypergraphs and configurations in the euclidean space. This is joint work with Jaroslav Nešetřil and Vojtech Rödl.

Stijn Cambie, Recent progress on the Union-closed conjecture and related
2023-03-14 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
We give a summary on the work of the last months related to Frankl’s Union-Closed conjecture and its offsprings. The initial conjecture is stated as a theorem in extremal set theory; when a family F is union-closed (the union of sets of F is itself a set of $mathcal F$), then $mathcal F$ contains an (abundant) element that belongs to at least half of the sets. Meanwhile, there are many related versions of the conjecture due to Frankl. For example, graph theorists may prefer the equivalent statement that every bipartite graph has a vertex that belongs to no more than half of the maximal independent sets. While even proving the ε-Union-Closed Sets Conjecture was out of reach, Poonen and Cui & Hu conjectured already stronger forms.
At the end of last year, progress was made on many of these conjectures. Gilmer proved the ε-Union-Closed Sets Conjecture using an elegant entropy-based method which was sharpened by many others. Despite a sharp approximate form of the union-closed conjecture as stated by Chase and Lovett, a further improvement was possible. In a different direction, Kabela, Polak and Teska constructed union-closed family sets with large sets and few abundant elements.
This talk will keep the audience up-to-date and give them insight in the main ideas.
People who would like more details, can join the Ecopro-reading session on the 14th of March (10 o’clock, B332) as well. Here we go deeper in the core of the proofs and discuss possible directions for the full resolution.

Paul Seymour, A loglog step towards the Erdős-Hajnal conjecture
2023-03-16 10:00 - 11:00 | Zoom ID: 869 4632 6610 (ibsdimag)
In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{csqrt{log |G|}}$.
There has no improvement on this result (for general $H$) until now, but now we have an improvement: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|ge 2$ has a clique or stable set of size at least $$2^{csqrt{log |G|loglog|G|}}.$$ This talk will outline the proof.
Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

Younjin Kim (김연진), Problems on Extremal Combinatorics
2023-03-21 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
Extremal Combinatorics studies the maximum or minimum size of finite objects (numbers, sets, graphs) satisfying certain properties. In this talk, I introduce the conjectures I solved on Extremal Combinatorics, and also introduce recent extremal problems.

Qizhong Lin, Two classical Ramsey-Turán numbers involving triangles
2023-03-22 16:30 - 17:30 | Zoom ID: 224 221 2686 (ibsecopro)
In 1993, Erdős, Hajnal, Simonovits, Sós and Szemerédi proposed to determine the value of Ramsey-Turán density $rho(3,q)$ for $qge3$. Erdős et al. (1993) and Kim, Kim and Liu (2019) proposed two corresponding conjectures. However, we only know four values of this Ramsey-Turán density by Erdős et al. (1993). There is no progress on this classical Ramsey-Turán density since then. In this talk, I will introduce two new values of this classical Ramsey-Turán density. Moreover, the corresponding asymptotically extremal structures are weakly stable, which answers a problem of Erdős et al. (1993) for the two cases. Joint work with Xinyu Hu.

Tianchi Yang, On the maximum number of edges in k-critical graphs
2023-03-28 16:30 - 17:30 | Room B332, IBS (기초과학연구원)
In this talk, we will discuss the problem of determining the maximum number of edges in an n-vertex k-critical graph. A graph is considered k-critical if its chromatic number is k, but any proper subgraph has a chromatic number less than k. The problem remains open for any integer k ≥ 4. Our presentation will showcase an improvement on previous results achieved by employing a combination of extremal graph theory and structural analysis. We will introduce a key lemma, which may be of independent interest, as it sheds light on the partial structure of dense k-critical graphs. This is joint work with Cong Luo and Jie Ma.
