Events Search and Views Navigation

Event Views Navigation

Today

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 …

Continue Reading

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 …

Continue Reading

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 …

Continue Reading

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 …

Continue Reading

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 …

Continue Reading

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 …

Continue Reading

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 …

Continue Reading

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 …

Continue Reading

Tianchi Yang, On the maximum number of edges in k-critical graphs

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 …

Continue Reading
DIMAG on YouTube

We use YouTube Live to broadcast seminar talks live if the speaker agrees.

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.