Benjamin Bergougnoux, Tight Lower Bounds for Problems Parameterized by Rank-width

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 and it answers the open question of Bergougnoux and Kanté . We also show

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

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

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

IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 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
Copyright © IBS 2018. All rights reserved.