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

Zoom ID: 934 3222 0374 (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

Jungho Ahn (안정호), Well-partitioned chordal graphs with the obstruction set and applications

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

We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the leaves of which are of size one. Well-partitioned chordal graphs are a generalization of

Extremal and Probabilistic Combinatorics (2021 KMS Spring Meeting)

A special session "Extremal and Probabilistic Combinatorics" at the 2021 KMS Spring Meeting is organized by Tuan Tran. URL: https://www.kms.or.kr/meetings/spring2021/ Speakers and Schedule All talks are on April 30. Joonkyung Lee (이준경), University College London Majority dynamics on sparse random graphs Dong Yeap Kang (강동엽), Unversity of Birmingham The Erdős-Faber-Lovász conjecture and related results  Jinyoung

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

Zoom ID: 934 3222 0374 (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 .

Mark Siggers, TBA

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

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

Zoom ID: 934 3222 0374 (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

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

Zoom ID: 934 3222 0374 (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,

MATRIX-IBS Workshop: Structural Graph Theory Downunder II

MATRIX, Australia

This program consists of a short intensive workshop, where mathematicians from across the globe will come together to work on open problems in structural graph theory. We will consider the following research themes: graph minors, graph colouring, Hadwiger’s Conjecture, bounded expansion classes, graph product structure theory, generalised colouring numbers, VC dimension, induced subgraphs, Erdös-Hajnal conjecture,

Postponed

Seymour is Seventy

ENS de Lyon, Lyon, France

A conference honouring the seventieth birthday of Paul Seymour To be held in ENS de Lyon, France, June 15 - 19, 2020. Due to the COVID-19, the organizers decided to postpone the conference “Seymour is Seventy”. We hope to run this event in the summer of 2022 instead. Specific decisions on the dates are to

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.