Locations
All talks, the open problem session and progress reports will be held in Hörsaal 1 of Arnimallee 3, with the coffee breaks taking place in the foyer outside the Hörsaal.
During the working sessions, groups may use seminar rooms 024 and 210 in Arnimallee 3, or 031 in Arnimallee 7.
You can enjoy your lunches in any of the wonderful eateries in our neighbourhood, some of which are listed here.
Monday, August 20
10:00  10:10  Opening ceremony  

10:10  11:00  Alexey Pokrovskiy
Rainbow trees and their applicationsA subgraph of an edgecoloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. This talk will be about proving that every properly edgecoloured complete graph has a rainbow copy of every nearly spanning tree. We will also discuss applications of this result to several problems in graph theory. In particular that conjectures of Ringel and GrahamSloane hold asymptotically. This is joint work with Richard Montgomery and Benny Sudakov. 

11:00  11:30  Coffee break  
11:30  12:20  Mykhaylo Tyomkyn
Two ErdősHajnaltype theorems in hypergraphsThe ErdősHajnal Theorem asserts that nonuniversal graphs, that is, graphs that do not contain an induced copy of some fixed graph H, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of runiform hypergraphs. 1. A theorem of Rödl asserts that if an nvertex graph is nonuniversal then it contains an almost homogeneous set (i.e. one with edge density either very close to 0 or 1) of size Ω(n). We prove that if a 3uniform hypergraph is nonuniversal then it contains an almost homogeneous set of size Ω(log n). An example of Rödl from 1986 shows that this bound is tight. 2. Let R_{r}(t) denote the size of the largest nonuniversal rgraph G so that neither G nor its complement contain a complete rpartite subgraph with parts of size t. We prove an ErdősHajnaltype steppingup lemma, showing how to transform a lower bound for R_{r}(t) into a lower bound for R_{r+1}(t). As an application of this lemma, we improve a bound of ConlonFoxSudakov by showing that R_{3}(t) ≥ t^{ct}. Joint work with M. Amir and A. Shapira. 

12:20  14:00  Lunch  
14:00  14:30  Ander Lamaison
Ramsey density of infinite pathsIn a twocolouring of the edges of the complete graph on the natural numbers, what is the densest monochromatic infinite path that we can always find? We measure the density of a path by the upper asymptotic density of its vertex set. This question was first studied by Erdös and Galvin, who proved that the best density is between 2/3 and 8/9. In this talk we settle this question by proving that we can always find a monochromatic path of upper density at least (12+√8)/17=0.87226…, and constructing a twocolouring in which no denser path exists. This represents joint work with Jan Corsten, Louis DeBiasio and Richard Lang. 

14:30  15:00  Anurag Bishnoi
Extremal and near extremal constructions for Ryser's conjectureA well known conjecture of Ryser states that every rpartite hypergraph H has a vertex cover of size at most (r  1) ν(H), where ν(H) is the matching number of H. In recent years, hypergraphs meeting this conjectured bound have been studied extensively. In particular, it was proved by Haxell, Narins and Szabó that for r = 3 all such hypergraphs with ν > 1 are essentially obtained by taking disjoint copies of intersecting extremal hypergraphs. AbuKhazneh showed that such a characterisation is false for r = 4 by giving a computergenerated counterexample. We construct a new family of extremal rpartite hypergraphs (with ν = 2), for r  1 equal to a prime power q ≥ 5, whose vertex set cannot be partitioned into two sets such that on both of these parts we have an intersecting rRyser subhypergraph. We will also discuss some new finite geometric nearextremal constructions for Ryser's conjecture. 

15:00  15:30  Coffee break  
15:30  16:20  Penny Haxell
Vertexinduced list edge colouringAbstract to follow. 

16:20  18:00  Open problem session 
Tuesday, August 21
10:10  11:00  Michael Krivelevich
Clique coloring in dense random graphsThe clique chromatic number of a graph G = (V,E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G(n,1/2) is, with high probability, of asymptotic order logarithmic in n. Joint work with Noga Alon. 


11:00  11:30  Coffee break  
11:30  12:00  Patrick Morris
Finding any given 2factor in sparse pseudorandom graphs efficientlyGiven an nvertex pseudorandom graph G and a potential 2factor H (that is, a union of disjoint cycles whose lengths sum to n), we wish to find a copy of H in G, i.e. an embedding φ: V(H) → V(G) so that φ(u)φ(v) ∈ E(G) for all uv ∈ E(H). Particular instances of this problem include finding a trianglefactor and finding a Hamilton cycle in G. In this talk, after giving the relevant context and history in this field, we will sketch how to find a given H in any suitably pseudorandom graph G. The graphs we will consider will be (n,d,λ) graphs i.e. n vertex dregular graphs whose second eigenvalue in absolute value is λ. Our condition λ = O(d^{2}/(n log n)) is within a log factor from being tight and provides a positive answer to a recent question of Nenadov (arXiv:1805.09710). This represents joint work with Jie Han, Yoshiharu Kohayakawa and Yury Person. 

12:00  12:30  Lior Gishboliner
Efficient removal without efficient regularityObtaining an efficient bound for the triangle removal lemma is one of the most outstanding open problems of extremal combinatorics. Perhaps the main bottleneck for achieving this goal is that trianglefree graphs can be highly unstructured. For example, trianglefree graphs might have only regular partitions (in the sense of Szemerédi) of towertype size. And indeed, essentially all the graph properties P for which removal lemmas with reasonable bounds were obtained, are such that every graph satisfying P has a small regular partition. So in some sense, a barrier for obtaining an efficient removal lemma for property P was having an efficient regularity lemma for graphs satisfying P. In this work we consider the property of being induced C_{4}free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of towertype size. By developing a new approach for this problem we manage to overcome this barrier and thus obtain a merely exponential bound for the induced C_{4} removal lemma. We thus obtain the first efficient removal lemma that does not rely on an efficient version of the regularity lemma. This is the first substantial progress on a problem raised by Alon in 2001, and more recently by Alon, Conlon and Fox. Joint work with Asaf Shapira. 

12:30  14:00  Lunch  
14:00  15:00  Splitting into groups  
15:00  15:30  Coffee break  
15:30  18:00  Working session  
19:00  late  Workshop dinner
DetailsDid you know that "Berlin" literally translates to "Beer village"? You shouldn't, because that's not true. Nevertheless, we will visit the Stone Brewing World Bistro & Gardens for dinner (map). We will meet at 7pm for dinner, but some might be interested in reaching the venue earlier: they have guided tours of their brewery at 5:30pm (English) and 6:30pm (German).. 
Wednesday, August 22
10:00  10:30  Michal Amir
Ramseynice families of graphsFor a finite family ℑ of fixed graphs let R_{k}(ℑ) be the smallest integer n for which every kcoloring of the edges of the complete graph K_{n} yields a monochromatic copy of some F ∈ ℑ. We say that ℑ is knice if for every graph G with χ(G)=R_{k}(ℑ) and for every kcoloring of E(G) there exists a monochromatic copy of some F ∈ ℑ. It is easy to see that if ℑ contains no forest, then it is not knice for any k. It seems plausible to conjecture that a (weak) converse holds, namely, for any finite family of graphs ℑ that contains at least one forest, and for all k ≥ k_{0}(ℑ) (or at least for infinitely many values of k), ℑ is knice. We prove several (modest) results in support of this conjecture, showing, in particular, that it holds for each of the three families consisting of two connected graphs with 3 edges each. 


10:30  11:00  Shagnik Das
Perturbed Ramsey problemsWe say a graph G is Ramsey for a pair of graphs (H_{1}, H_{2}) if any red/bluecolouring of E(G) contains either a red H_{1} or a blue H_{2}. Much research has been devoted to determining the thresholds at which the ErdősRényi random graph G(n,p) becomes Ramsey for (H_{1}, H_{2}). In this talk, we instead consider the perturbed random graph model, where one sprinkles some random edges on top of a deterministic dense graph, and ask how much less randomness is needed to ensure the resulting graph is Ramsey. This line of research was initiated by Krivelevich, Sudakov and Tetali in 2006, who determined the thresholds for the pairs (K_{3}, K_{t}) with t ≥ 3. Here we extend their work, considering pairs of larger cliques. We also present results for cycles, and cycles versus cliques. This is joint work with Andrew Treglown. 

11:00  11:30  Coffee break  
11:30  12:30  Working session  
12:30  14:00  Lunch  
14:00  15:00  Working session  
15:00  15:30  Coffee break  
15:30  18:00  Working session 
Thursday, August 23
10:00  11:00  Progress reports  

11:00  11:30  Coffee break  
11:30  12:30  Working session  
12:30  14:00  Lunch  
14:00  15:00  Working session  
15:00  15:30  Coffee break  
15:30  18:00  Working session 
Friday, August 24
10:00  11:00  Working session  

11:00  11:30  Coffee break  
11:30  12:30  Working session  
12:30  14:00  Lunch  
14:00  15:00  Working session  
15:00  15:30  Coffee break  
15:30  16:30  Progress reports  
16:30  late  Social program 