Mark Siggers, The list switch homomorphism problem for signed graphs

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

A signed graph is a graph in which each edge has a positive or negative sign. Calling two graphs switch equivalent if one can get from one to the other by the iteration of the local action of switching all signs on edges incident to a given vertex, we say that there is a switch

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

Pascal Gollin, Enlarging vertex-flames in countable digraphs

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

A rooted digraph is a vertex-flame if for every vertex v there is a set of internally disjoint directed paths from the root to v whose set of terminal edges covers all ingoing edges of v. It was shown by Lovász that every finite rooted digraph admits a spanning subdigraph which is a vertex-flame and large, where the latter means

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,

Ben Lund, Limit shape of lattice Zonotopes

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

A convex lattice polytope is the convex hull of a set of integral points. Vershik conjectured the existence of a limit shape for random convex lattice polygons, and three proofs of this conjecture were given in the 1990s by Bárány, by Vershik, and by Sinai. To state this old result more precisely, there is a

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

Doowon Koh (고두원), Mattila-Sjölin type functions: A finite field model

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

Let $\mathbb{F}_q$ be a finite field of order $q$ which is a prime power. In the finite field setting, we say that a function $\phi\colon \mathbb{F}_q^d\times \mathbb{F}_q^d\to \mathbb{F}_q$ is a Mattila-Sjölin type function in $\mathbb{F}_q^d$ if for any $E\subset \mathbb{F}_q^d$ with $|E|\gg q^{\frac{d}{2}}$, we have $\phi(E, E)=\mathbb{F}_q$. The main purpose of this talk is to present

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

O-joung Kwon (권오정), Classes of intersection digraphs with good algorithmic properties

Zoom ID: 875 9395 3555 (relay) [CLOSED]

An intersection digraph is a digraph where every vertex $v$ is represented by an ordered pair $(S_v, T_v)$ of sets such that there is an edge from $v$ to $w$ if and only if $S_v$ and $T_w$ intersect. An intersection digraph is reflexive if $S_v\cap T_v\neq \emptyset$ for every vertex $v$. Compared to well-known undirected

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

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.