2016/2017

Talks take place at
Arnimallee 3, 14195 Berlin, room SR 210/A3, on Wednesdays, and
Takustr. 9, 14195 Berlin, room SR 046 , on Thursdays.

DateSpeakerTitle
4.01.2017
10:15

Bartosz Walczak
Jagiellonian University
tba.
14.12.2016
16:15

Jarek Grytczuk
Jagiellonian University
tba.
7.12.2016
16:15
Gwenaël Joret
Université Libre de Bruxelles
Orthogonal graph decomposition.
1.12.2016
10:15
Veit Wiechert
TU Berlin
On the boxicity of graphs with no K_t minor.
23.11.2016
16:15
Torsten Mütze
TU Berlin
Trimming and gluing Gray codes.
17-18.11.2016
BMS 10 Year Anniversary
BMS10
9.11.2016
16:15
Tamás Mészáros
FU Berlin
Some combinatorial applications of Gröbner bases and standard monomials.
27.10.2016
10:15
Tibor Szabó
FU Berlin
Vertex Folkman Numbers.
19.10.2016
16:15
Piotr Micek
FU Berlin
Weak coloring numbers and poset's dimension.
19.10.2016
Piotr Micek (FU Berlin)
Weak coloring numbers and poset's dimension.
Abstract: We will discuss the notion and applications of (weak-)coloring numbers introduced by Kierstead and Yang. Coloring numbers become popular nowadays mainly because they give an important characterization of sparse classes. We will make a quick overview of the topic and then present a new application for poset dimension topic. Joint work with Gwenael Joret and Veit Wiechert.
27.10.2016
Tibor Szabó (FU Berlin)
Minimal Ramsey graphs and Folkman numbers.
Abstract: A graph G is a minimal Ramsey-graph for H if every r-colouring of the edges of G contains a monochromatic copy of H, but no proper subgraph of G has this property. Burr, Erdos and Lovasz determined the smallest possible minimum degree of two-color minimal Ramsey-graphs for the k-clique. Here we obtain a bound for the smallest minimum degree, tight up to a logarithmic factor, for any number of colors. Our proof relies on a reformulation of the corresponding extremal function by Fox et al, and refines methods used by Dudek, Eaton, and Rodl for vertex Folkman numbers. This represents joint work with Hiep Han and Vojta Rodl.
3.11.2016
Tamás Mészáros (FU Berlin)
Some combinatorial applications of Gröbner bases and standard monomials.
Abstract: Let F be a field, V ⊆ F^n be a (combinatorially interesting) finite set of points. As an example think about V being the collection of characteristic vectors of sets belonging to some set system V ⊆ P([n]). Several important properties of V are reflected by the polynomial functions on V . To study these, one often considers I(V), the vanishing ideal of V in the polynomial ring F[x_1,...,x_n]. Gröbner bases and standard monomials of I(V) appear to be useful in this context, leading to structural results on V . In my talk, after an introduction to Gröbner bases and standard monomials, I will give some results of the above type.
23.11.2016
Torsten Mütze (TU Berlin)
Trimming and gluing Gray codes.
Abstract: We consider the algorithmic problem of generating each subset of [n]:={1,2,...,n} whose size is in some interval [a,b], 0 \leq a \leq b \leq n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For a=0 and b=n this is the classical problem of generating all 2^n subsets of [n] by element additions/removals, and for a=b this is the classical problem of generating all \binom{n}{a} subsets of [n] by element exchanges. In graph theoretical terms, we ask for the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q_n induced by all levels [a,b]. We prove the existence of such cycles for a large range of values n, a, and b, and provide corresponding optimal generation algorithms, improving upon and generalizing several previous results. This is joint work with Petr Gregor.
1.12.2016
Veit Wiechert (TU Berlin)
On the boxicity of graphs with no K_t minor.
Abstract: A d-box is the Cartesian product of d closed intervals of the real line. The boxicity of a graph G is the least d such that G is the intersection graph of a collection of d-boxes. (Note that graphs with boxicity one are simply interval graphs.) The concept of boxicity was introduced by Roberts in 1969 and has been studied since then on several minor-closed graph classes. For instance, Thomassen proved that the boxicity of planar graphs is at most 3. In this talk, we show that graphs with no K_t minor have boxicity O(t^2 log(t)). This is an improvement upon an O(t^4 log^2(t)) bound due to Esperet and Joret.
7.12.2016
Gwenaël Joret (Université Libre de Bruxelles)
Orthogonal graph decomposition.
Abstract: tba
Jarek Grytczuk
14.12.2016
Jarek Grytczuk (Jagiellonian University)
tba.
Abstract: tba
4.01.2017
Bartosz Walczak (Jagiellonian University)
tba .
Abstract: tba