Jean-Florent Raymond, Long induced paths in minor-closed graph classes and beyond

Zoom ID: 869 4632 6610 (ibsdimag)

In 1982 Galvin, Rival, and Sands proved that in $K_{t,t}$-subgraph free graphs (t being fixed), the existence of a path of order n guarantees the existence of an induced path of order f(n), for some (slowly) increasing function f. The problem of obtaining good lower-bounds for f for specific graph classes was investigated decades later

Jakub Gajarský, Model Checking on Interpretations of Classes of Bounded Local Clique-Width

Zoom ID: 869 4632 6610 (ibsdimag)

The first-order model checking problem for finite graphs asks, given a graph G and a first-order sentence $\phi$ as input, to decide whether $\phi$ holds on G. Showing the existence of an efficient algorithm for this problem implies the existence of efficient parameterized algorithms for various commonly studied problems, such as independent set, distance-r dominating

Boram Park (박보람), Odd coloring of sparse graphs

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

We introduce an odd coloring of a graph, which was introduced very recently, motivated by parity type colorings of graphs. A proper vertex coloring of graph $G$ is said to be odd if for each non-isolated vertex $x \in V (G)$ there exists a color $c$ such that $c$ is used an odd number of

Cheolwon Heo (허철원), The complexity of the matroid-homomorphism problems

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

In this talk, we introduce homomorphisms between binary matroids that generalize graph homomorphisms. For a binary matroid $N$, we prove a complexity dichotomy for the problem $\rm{Hom}_\mathbb{M}(N)$ of deciding if a binary matroid $M$ admits a homomorphism to $N$. The problem is polynomial-time solvable if $N$ has a loop or has no circuits of odd

Kyeongsik Nam (남경식), Large deviations for subgraph counts in random graphs

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

The upper tail problem for subgraph counts in the Erdos-Renyi graph, introduced by Janson-Ruciński, has attracted a lot of attention. There is a class of Gibbs measures associated with subgraph counts, called exponential random graph model (ERGM). Despite its importance, lots of fundamental questions have remained unanswered owing to the lack of exact solvability. In

Andreas Holmsen, A colorful version of the Goodman-Pollack-Wenger transversal theorem

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

Hadwiger's transversal theorem gives necessary and sufficient conditions for the existence of a line transversal to a family of pairwise disjoint convex sets in the plane. These conditions were subsequently generalized to hyperplane transversals in $\mathbb{R}^d$ by Goodman, Pollack, and Wenger. Here we establish a colorful extension of their theorem, which proves a conjecture of

Jan Kurkofka, Canonical Graph Decompositions via Coverings

Zoom ID: 869 4632 6610 (ibsdimag)

We present a canonical way to decompose finite graphs into highly connected local parts. The decomposition depends only on an integer parameter whose choice sets the intended degree of locality. The global structure of the graph, as determined by the relative position of these parts, is described by a coarser model. This is a simpler

Gil Kalai, The Cascade Conjecture and other Helly-type Problems

Zoom ID: 868 7549 9085

For a set $X$ of points $x(1)$, $x(2)$, $\ldots$, $x(n)$ in some real vector space $V$ we denote by $T(X,r)$ the set of points in $X$ that belong to the convex hulls of r pairwise disjoint subsets of $X$. We let $t(X,r)=1+\dim(T(X,r))$. Radon's theorem asserts that If $t(X,1)< |X|$, then $t(X, 2) >0$. The first

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.