## November 2022

### Seonghyuk Im (임성혁), A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

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

## December 2022

### Giannos Stamoulis, Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes

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,$

### Stijn Cambie, The 69-conjecture and more surprises on the number of independent sets

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

## January 2023

### Youngho Yoo (유영호), Approximating TSP walks in subcubic graphs

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

### Mamadou Moustapha Kanté, MSOL-Definable decompositions

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

### Noleen Köhler, Twin-Width VIII: Delineation and Win-Wins

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

### Abhishek Methuku, A proof of the Erdős–Faber–Lovász conjecture

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

## February 2023

### Raphael Steiner, Strengthening Hadwiger’s conjecture for 4- and 5-chromatic graphs

Room B332 IBS (기초과학연구원)

Hadwiger's famous coloring conjecture states that every t-chromatic graph contains a $K_t$-minor. Holroyd conjectured the following strengthening of Hadwiger's conjecture: If G is a t-chromatic graph and S⊆V(G) takes all

### 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)$,

### 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

기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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