Johannes Carmesin, Open problems in graph theory

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

Since the proof of the graph minor structure theorem by Robertson and Seymour in 2004, its underlying ideas have found applications in a much broader range of settings than their original context. They have driven profound progress in areas such as vertex minors, pivot minors, matroids, directed graphs, and 2-dimensional simplicial complexes. In this talk,

Michał Seweryn, Dimension and standard examples in planar posets

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

The dimension of a poset is the least integer $d$ such that the poset is isomorphic to a subposet of the product of $d$ linear orders. In 1983, Kelly constructed planar posets of arbitrarily large dimension. Crucially, the posets in his construction involve large standard examples, the canonical structure preventing a poset from having small

Hyunwoo Lee (이현우), Reconstructing hypergraph matching polynomials

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

By utilizing the recently developed hypergraph analogue of Godsil's identity by the second author, we prove that for all $n \geq k \geq 2$, one can reconstruct the matching polynomial of an $n$-vertex $k$-uniform hypergraph from the multiset of all induced sub-hypergraphs on $\lfloor \frac{k-1}{k}n \rfloor + 1$ vertices. This generalizes the well-known result of

Marcelo Garlet Milani, Cycles of Well-Linked Sets and an Elementary Bound for the Directed Grid Theorem

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

In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem. The theorem states the existence of a function f such that every digraph of directed tree-width f(k) contains a cylindrical grid of order k as a butterfly minor, but the given function grows non-elementarily with the size of the grid minor. We present an alternative

Daniel McGinnis, A necessary and sufficient condition for $k$-transversals

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

We solve a long-standing open problem posed by Goodman and Pollack in 1988 by establishing a necessary and sufficient condition for a finite family of convex sets in $\mathbb{R}^d$ to admit a $k$-transversal (a $k$-dimensional affine subspace that intersects each set) for any $0 \le k \le d-1$. This result is a common generalization of

Nicola Lorenz, A Minor Characterisation of Normally Spanned Sets of Vertices

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

A rooted spanning tree of a graph $G$ is called normal if the endvertices of all edges of $G$ are comparable in the tree order. It is well known that every finite connected graph has a normal spanning tree (also known as depth-first search tree). Also, all countable graphs have normal spanning trees, but uncountable

Marcin Briański, Burling Graphs as (almost) universal obstacles to $\chi$-boundedness

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

What causes a graph to have high chromatic number? One obvious reason is containing a large clique (a set of pairwise adjacent vertices). This naturally leads to investigation of \(\chi\)-bounded classes of graphs --- classes where a large clique is essentially the only reason for large chromatic number. Unfortunately, many interesting graph classes are not

Pascal Schweitzer, Recent insights surrounding combinatorial approaches to isomorphism and symmetry problems

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

Modern practical software libraries that are designed for isomorphism tests and symmetry computation rely on combinatorial techniques combined with techniques from algorithmic group theory. The Weisfeiler-Leman algorithm is such a combinatorial technique. When taking a certain view from descriptive complexity theory, the algorithm is universal. After an introduction to problems arising in symmetry computation and

Eunjin Oh (오은진), Approximation Algorithms for the Geometric Multimatching Problem

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

Let S and T be two sets of points in a metric space with a total of n points. Each point in S and T has an associated value that specifies an upper limit on how many points it can be matched with from the other set. A multimatching between S and T is a way of pairing points such that each point in S is matched with at least as many

Seokbeom Kim (김석범), The structure of △(1, 2, 2)-free tournaments

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

Given a tournament $S$, a tournament is $S$-free if it has no subtournament isomorphic to $S$. Until now, there have been only a small number of tournaments $S$ such that the complete structure of $S$-free tournaments is known. Let $\triangle(1, 2, 2)$ be a tournament obtained from the cyclic triangle by substituting two-vertex tournaments for

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.