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
9.02.2017
10:15
Frank Mousset
ETH Zürich
Covering sparse graphs by monochromatic cycles
26.01.2017
10:15
Christopher Kusch
FU Berlin
Random Strategies are nearly optimal for generalised van der Waerden games
19.01.2017
10:15
William T. Trotter
Georgia Institute of Technology
Dimension and Cut Vertices
12.01.2017
10:15
Tibor Szabó
FU Berlin
The Oberwolfach problems
11.01.2017
16:15
Matthew Jenssen
London School of Econmics
Exact Ramsey numbers of odd cycles via nonlinear optimisation
4.01.2017
16:15
Bartosz Walczak
Jagiellonian University
Coloring curves that cross a fixed curve.
15.12.2016
10:15
Jaroslaw Grytczuk
Jagiellonian University and Warsaw University of Technology
Majority Choosability of Digraphs.
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: A simple but useful property of planar graphs is that one can find a BFS layering of the vertices and a tree decomposition such that each layer intersects each bag in a bounded number of vertices (at most 3 in fact). This easily implies classic facts such as the existence of O(sqrt(n)) separators and the diameter-treewidth property of planar graphs. The layering can be seen as a decomposition of the graph that is "orthogonal" to the tree decomposition: The layers can be big, and similarly the bags of tree decomposition can be big, but they have bounded intersections. In this talk I will give an introduction to this new area of research, and explain some recent applications.
Jarek Grytczuk
15.12.2016
Jaroslaw Grytczuk (Jagiellonian University and Warsaw University of Technology)
Majority Choosability of Digraphs.
Abstract: A majority coloring of a digraph is a coloring of its vertices such that for each vertex v, at most half of out-neighbors of v have the same color as v. A digraph D is majority k-choosable if for any assignment of lists of colors of size k to the vertices there is a majority coloring of D from these lists. We prove that every digraph is majority 4-choosable. This gives a positive answer to a question posed recently in [1]. We also conjecture that every digraph is majority 3-choosable, which would be best possible.
Joint work with Marcin Anholcer and Bartlomiej Bosek.
[1] S. Kreutzer, S. Oum, P. Seymour, D. van der Zypen, D. R. Wood, Majority Colourings of Digraphs, arXiv:1608.03040.
4.01.2017
Bartosz Walczak (Jagiellonian University)
Coloring curves that cross a fixed curve.
Abstract: A class of graphs is χ-bounded if the chromatic number of all graphs in the class is bounded by some function of their clique number. String graphs are intersection graphs of curves in the plane. Significant research in combinatorial geometry has been devoted to understanding the classes of string graphs that are χ-bounded. In particular, it is known since 2012 that the class of all string graphs is not χ-bounded. We prove that for every integer t≥1, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most t points is χ-bounded. This result is best possible in several aspects; for example, the upper bound t on the number of crossings with the fixed curve cannot be dropped. As a corollary, we obtain new upper bounds on the number of edges in so-called k-quasi-planar topological graphs. This is joint work with Alexandre Rok.
11.01.2017
Matthew Jenssen (London School of Economics)
Exact Ramsey numbers of odd cycles via nonlinear optimisation.
Abstract: For a graph G, the k-colour Ramsey number R_k(G) is the least integer N such that every k-colouring of the edges of the complete graph K_N contains a monochromatic copy of G. Let C_n denote the cycle on n vertices. For all k, we determine the exact value of R_k(C_n) for n odd and sufficiently large. This resolves a conjecture of Bondy and Erdős for large n. The proof is analytic in nature, the first step of which is to use the regularity method to relate this problem in Ramsey theory to one in nonlinear optimisation. This allows us to prove a stability-type generalisation of the above and establish a correspondence between extremal k-colourings for this problem and perfect matchings in the k-dimensional hypercube Q_k. This is joint work with Jozef Skokan.
12.01.2017
Tibor Szabó (FU Berlin)
The Oberwolfach problems
Abstract:In the talk I describe the problems that were raised in the open problem session of last week's Combinatorics Workshop in Oberwolfach.
19.01.2017
William T. Trotter (Georgia Institute of Technologie)
Dimension and Cut Vertices
Abstract: Motivated by quite recent research involving the relationship between the dimension of a poset and graph theoretic properties of its cover graph, we show that for every $d\ge 1$, if $P$ is a poset and the dimension of a subposet $B$ of $P$ is at most~$d$ whenever the cover graph of $B$ is a block of the cover graph of $P$, then the dimension of $P$ is at most $d+2$. We also construct examples which show that this inequality is best possible. We consider the proof of the upper bound to be fairly elegant and relatively compact. However, we know of no simple proof for the lower bound, and our argument requires a powerful tool known as the Product Ramsey Theorem. As a consequence, our constructions involve posets of enormous size. Joint research with Bartosz Walczak and Ruidong Wang.
26.01.2017
Christopher Kusch (FU Berlin)
Random Strategies are nearly optimal for generalised van der Waerden games.
Abstract: In this talk we shall discuss the hypergraph generalisation of the biased Maker-Breaker H-games previously studied by Bednarska and Luczak as well as a strong generalisation of the van der Waerden games introduced by Beck. Generalising the arguments of Bednarska and Luczak, we present two general winning criteria for Maker and Breaker that can be used to determine the threshold biases of the above games up to constant factors. As in the Maker-Breaker H-games, a random strategy for Maker is the best known strategy in these games. Joint work with J. Rué, C. Spiegel and T. Szabó.
9.02.2017
Frank Mousset (ETH Zürich)
Covering sparse graphs by monochromatic cycles.
Abstract: This talk is about the following type of question: suppose that we colour the edges of a graph (say, the complete graph on n vertices) with a small amount of colours (say, red and blue). How many monochromatic cycles are needed to cover the vertices of the graph? It is known that for the complete graph (and several other very dense types of graphs), this number depends only on the number of colours, and not on n. I am going to present a result showing that the random graph G(n,p) with p = omega(n^{-1/r+epsilon}) whp has the property that any colouring by r colours admits a vertex cover by constantly many monochromatic cycles. This is whp not the case if p = o(n^{-1/r}). This is joint work with Daniel Korandi, Rajko Nenadov, Nemanja Skoric, and Benny Sudakov.