## February 2023

### Robert Hickingbotham, Treewidth, Circle Graphs and Circular Drawings

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

### Meike Hatzel, Fixed-Parameter Tractability of Directed Multicut with Three Terminal Pairs Parametrised by the Size of the Cutset: Twin-Width Meets Flow-Augmentation

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

### Daniel Altman, On an arithmetic Sidorenko conjecture, and a question of Alon

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

### Maya Sankar, The Turán Numbers of Homeomorphs

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

## March 2023

### Eunjin Oh (오은진), Parameterized algorithms for the planar disjoint paths problem

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 $i\in\{1,\ldots,k\}$. This problem has been studied extensively due to

### Marcelo Sales, On Pisier type problems

Zoom ID: 224 221 2686 (ibsecopro)

A subset $A\subseteq \mathbb Z$ of integers is free if for every two distinct subsets $B, B'\subseteq A$ we have \Pisier asked if for every subset $A\subseteq \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

### Stijn Cambie, Recent progress on the Union-closed conjecture and related

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

### Paul Seymour, A loglog step towards the Erdős-Hajnal conjecture

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^{c\sqrt{\log |G|}}$. There has no improvement on this result (for general

### Younjin Kim (김연진), Problems on Extremal Combinatorics

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

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 $q\ge3$. 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

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209