Discrete Math Seminar

Events Search and Views Navigation

Event Views Navigation

Today

  • 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,$ for $i\in \{1,\ldots, k\}$. This logic can express a wide variety of problems that escape the expressibility potential of FOL. We prove that for every …

    Continue Reading

  • 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 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 …

    Continue Reading

  • 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 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 …

    Continue Reading

  • 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 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 …

    Continue Reading

  • 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 $\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 …

    Continue Reading

  • 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 of this conjecture for every large n. Joint work with D. Kang, T. Kelly, D. Kühn and D. Osthus.

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

    Continue Reading

  • 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

  • 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
DIMAG on YouTube

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