2016/2017
Talks take place at
Arnimallee 3, 14195 Berlin, room SR 210/A3, on Wednesdays, and
Arnimallee 3, 14195 Berlin, room SR 210/A3 , on Thursdays.
| Date | Speaker | Title |
|---|---|---|
| 31.05.2017 16:15 |
Shagnik Das (Berlin) |
Some of my favourite problems from Sanya |
| 27.04.2017 10:15 |
Hong Liu (University of Warwick) |
Edges not in any monochromatic copy of a fixed graph. |
| 19.04.2017 16:15 |
Jan Corsten (London School of Economics) |
Grid Ramsey Problem. |
| 30.03.2017 10:15 |
Adam Zsolt Wagner (University of Illinois at Urbana-Champaign) |
Families with few k-chains |
| 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 JenssenLondon School of Econmics | Exact Ramsey numbers of odd cycles via nonlinear optimisation |
| 4.01.2017 16:15 |
Bartosz WalczakJagiellonian 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. |
| 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. |
| 30.03.2017 |
| Adam Zsolt Wagner (University of Illinois at Urbana-Champaign) |
| Families with few k-chains |
| Abstract: A central theorem in combinatorics is Sperner’s Theorem, which determines the maximum size of a family in the Boolean lattice that does not contain a 2-chain. Erdos later extended this result and determined the largest family not containing a k-chain. Erdos and Katona and later Kleitman asked how many such chains must appear in families whose size is larger than the corresponding extremal result. This question was resolved for 2-chains by Kleitman in 1966, who showed that amongst families of size M in the Boolean lattice, the number of 2-chains is minimized by a family whose sets are taken as close to the middle layer as possible. He also conjectured that the same conclusion should hold for all k, not just 2. The best result on this question is due to Das, Gan and Sudakov who showed roughly that Kleitman’s conjecture holds for families whose size is at most the size of the k+1 middle layers of the Boolean lattice. Our main result is that for every fixed k and epsilon, if n is sufficiently large then Kleitman’s conjecture holds for families of size at most (1-epsilon)2^n, thereby establishing Kleitman’s conjecture asymptotically. Our proof is based on ideas of Kleitman and Das, Gan and Sudakov. |
| 19.04.2017 |
| Jan Corsten (London School of Economics) |
| Grid Ramsey Problem |
| Abstract: The grid Ramsey number $ G(r) $ is the smallest number $ n $ such that every edge-colouring of the grid graph $\Gamma_{n,n} := K_n \times K_n$ with $r$ colours induces a rectangle whose parallel edges receive the same colour. We show $ G(r) \leq r^{\binom{r+1}{2}} - \left( 1/4 - o(1) \right) r^{\binom{r}{2}+1} $, slightly improving the currently best known upper bound due to Gyárfás. |
| 27.04.2017 |
| Hong Liu (University of Warwick) |
| Edges not in any monochromatic copy of a fixed graph |
| Abstract: For a sequence $(H_i)_{i=1}^k$ of graphs, let $\nim(n;H_1,\ldots, H_k)$ denote the maximum number of edges not contained in any monochromatic copy of $H_i$ in colour $i$, over all $k$-edge-colourings of $K_n$. When each $H_i$ is connected and non-bipartite, we introduce a variant of Ramsey number that determines the limit of $\nim(n;H_1,\ldots, H_k)/{n\choose 2}$ as $n\to\infty$ and prove the corresponding stability result. Also, we obtain an exact result if each $H_i$ is strongly-colour-critical (in particular if each $H_i$ is a clique) and $n$ is sufficiently large. The special case $\nim(n;K_3,K_3,K_3)$ of our result answers a question of Ma. For bipartite graphs, we mainly concentrate on the two-colour symmetric case (i.e., when $k=2$ and $H_1=H_2$). It is trivial to see that $\nim(n;H,H)$ is at least $\ex(n,H)$, the maximum size of an $H$-free graph on $n$ vertices. Keevash and Sudakov showed that equality holds if $H$ is the $4$-cycle and $n$ is large; recently Ma extended their result to an infinite family of bipartite graphs. We provide a larger family of bipartite graphs for which $\nim(n;H,H)=\ex(n,H)$. For a general bipartite graph $H$, we show that $\nim(n;H,H)$ is always within a constant additive error from $\ex(n,H)$, i.e.,~$\nim(n;H,H)= \ex(n,H)+O_H(1)$. This is joint work with Oleg Pikhurko and Maryam Sharifzadeh. |
| 31.05.2017 |
| Shagnik Das (FU Berlin) |
| Some of my favourite problems from Sanya |
| Abstract: Just as, some centuries ago, Marco Polo returned from China with wondrous tales of all that he had seen during his travels, so too shall I shower you with the fruits of my trip to Sanya. Not literal fruits – the scrumptious assortment of exotic fruits we consumed during the tea breaks will live long, but only in memory – but metaphorical ones, in the form of open problems presented by fellow workshop attendees. There were many problems on offer, and I shall share with you a carefully curated selection of those that I found most appealing. Bring an open mind and an empty notebook (a writing implement would be advisable as well). |