Dillon Mayhew, Monadic second-order definability for gain-graphic matroids

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

Every (finite) matroid consists of a (finite) set called the ground set, and a collection of distinguished subsets called the independent sets. A classic example arises when the ground set is a finite set of vectors from a vector space, and the independent subsets are exactly the subsets that are linearly independent. Any such matroid

Amadeus Reinald, Oriented trees in $O(k \sqrt{k})$-chromatic digraphs, a subquadratic bound for Burr’s conjecture

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

In 1980, Burr conjectured that every directed graph with chromatic number $2k-2$ contains any oriented tree of order $k$ as a subdigraph. Burr showed that chromatic number $(k-1)^2$ suffices, which was improved in 2013 to $\frac{k^2}{2} - \frac{k}{2} + 1$ by Addario-Berry et al. In this talk, we give the first subquadratic bound for Burr's

Neal Bushaw, Edge-colored Extremal Problems

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

An edge-colored graph $H$ is called rainbow if all of its edges are given distinct colors.  An edge-colored graph $G$ is then called rainbow $H$-free when no copy of $H$ in $G$ is rainbow.  With this, we define a graph $G$ to be rainbow $H$-saturated when there is some proper edge-coloring of $G$ which is rainbow $H$-free,

Gábor Tardos, Extremal theory of 0-1 matrices

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

We say that a 0-1 matrix A contains another such matrix (pattern) P if P can be obtained from a submatrix of A by possibly changing a few 1 entries to 0. The main question of this theory is to estimate the maximal number of 1 entries in an n by n 0-1 matrix NOT

Mathias Schacht, Canonical colourings in random graphs

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

Rödl and Ruciński established Ramsey's theorem for random graphs. In particular, for fixed integers $r$, $\ell\geq 2$ they showed that $n^{-\frac{2}{\ell+1}}$ is a threshold for the Ramsey property that every $r$-colouring of the edges of the binomial random graph $G(n,p)$ yields a monochromatic copy of $K_\ell$. We investigate how this result extends to arbitrary colourings

Kyeongsik Nam (남경식), Random walks on percolation

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

In general, random walks on fractal graphs are expected to exhibit anomalous behaviors, for example heat kernel is significantly different from that in the case of lattices. Alexander and Orbach in 1982 conjectured that random walks on critical percolation, a prominent example of fractal graphs, exhibit mean field behavior; for instance, its spectral dimension is

Colin Geniet, Permutations, patterns, and twin-width

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

This talk will first introduce combinatorics on permutations and patterns, presenting the basic notions and some fundamental results: the Marcus-Tardos theorem which bounds the density of matrices avoiding a given pattern, and the Guillemot-Marx algorithm for pattern detection using the notion now known as twin-width. I will then present a decomposition result: permutations avoiding a

Felix Christian Clemen, Triangles in the Plane

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

A classical problem in combinatorial geometry, posed by Erdős in 1946, asks to determine the maximum number of unit segments in a set of $n$ points in the plane. Since then a great variety of extremal problems in finite planar point sets have been studied. Here, we look at such questions concerning triangles. Among others

Michał Pilipczuk, Monadic stability and monadic dependence

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

We will give an overview of the recent attempts of building a structure theory for graphs centered around First-Order transductions: a notion of containment inspired by finite model theory. Particularly, we will speak about the notions of monadic dependence and monadic stability, their combinatorial characterizations, and the developments on the algorithmic front.

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.