Virtual Discrete Math Colloquium

  1. Events
  2. Virtual Discrete Math Colloquium

Events Search and Views Navigation

Event Views Navigation

Today

Reinhard Diestel, Tangles of set separations: a novel clustering method and type recognition in machine learning

Zoom ID: 869 4632 6610 (ibsdimag)

Traditional clustering identifies groups of objects that share certain qualities. Tangles do the converse: they identify groups of qualities that typically occur together. They can thereby discover, relate, and structure types: of behaviour, political views, texts, or proteins. Tangles offer a new, quantitative, paradigm for grouping phenomena rather than things. They can identify key phenomena …

Continue Reading

Raul Lopes, Adapting the Directed Grid Theorem into an FPT Algorithm

Zoom ID: 869 4632 6610 (ibsdimag)

The Grid Theorem of Robertson and Seymour is one of the most important tools in the field of structural graph theory, finding numerous applications in the design of algorithms for undirected graphs. An analogous version of the Grid Theorem in digraphs was conjectured by Johnson et al. , and proved by Kawarabayashi and Kreutzer . …

Continue Reading

Johannes Carmesin, A Whitney type theorem for surfaces: characterising graphs with locally planar embeddings

Zoom ID: 869 4632 6610 (ibsdimag)

Given a graph, how do we construct a surface so that the graph embeds in that surface in an optimal way? Thomassen showed that for minimum genus as optimality criterion, this problem would be NP-hard. Instead of minimum genus, here we use local planarity -- and provide a polynomial algorithm. Our embedding method is based …

Continue Reading

Benjamin Bumpus, Directed branch-width: A directed analogue of tree-width

Zoom ID: 869 4632 6610 (ibsdimag)

Many problems that are NP-hard in general become tractable on `structurally recursive’ graph classes. For example, consider classes of bounded tree- or clique-width. Since the 1990s, many directed analogues of tree-width have been proposed. However, many natural problems (e.g. directed HamiltonPath and MaxCut) remain intractable on such digraph classes of `bounded width’. In this talk, …

Continue Reading

Dimitrios M. Thilikos, Bounding Obstructions sets: the cases of apices of minor closed classes

Zoom ID: 869 4632 6610 (ibsdimag)

Given a minor-closed graph class ${\cal G}$, the (minor) obstruction of ${\cal G}$ is the set of all minor-minimal graphs not in ${\cal G}$. Given a non-negative integer $k$, we define the $k$-apex of ${\cal A}$ as the class containing every graph $G$ with a set $S$ of vertices whose removal from $G$ gives a graph …

Continue Reading

Adam Zsolt Wagner, Constructions in combinatorics via neural networks

Zoom ID: 869 4632 6610 (ibsdimag)

Recently, significant progress has been made in the area of machine learning algorithms, and they have quickly become some of the most exciting tools in a scientist’s toolbox. In particular, recent advances in the field of reinforcement learning have led computers to reach superhuman level play in Atari games and Go, purely through self-play. In …

Continue Reading

Alan Lew, Representability and boxicity of simplicial complexes

Zoom ID: 869 4632 6610 (ibsdimag)

An interval graph is the intersection graph of a family of intervals in the real line. Motivated by problems in ecology, Roberts defined the boxicity of a graph G to be the minimal k such that G can be written as the intersection of k interval graphs. A natural higher-dimensional generalization of interval graphs is …

Continue Reading

Stefan Weltge, Integer programs with bounded subdeterminants and two nonzeros per row

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

We give a strongly polynomial-time algorithm for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row. The core of our approach is the first polynomial-time algorithm for the weighted stable set problem on graphs that do not contain …

Continue Reading

Maria Chudnovsky, Induced subgraphs and tree decompositions

Zoom ID: 869 4632 6610 (ibsdimag)

Tree decompositions are a powerful tool in structural graph theory; they are traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has until recently remained out of reach. Tree decompositions are closely related to the existence of "laminar collections of separations" in a graph, which roughly means that …

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.