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 applications

A subgraph of an edge-coloured 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 edge-coloured 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 Graham-Sloane 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ős-Hajnal-type theorems in hypergraphs

The Erdős-Hajnal Theorem asserts that non-universal 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 r-uniform hypergraphs.

1. A theorem of Rödl asserts that if an n-vertex graph is non-universal 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 3-uniform hypergraph is non-universal 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 Rr(t) denote the size of the largest non-universal r-graph G so that neither G nor its complement contain a complete r-partite subgraph with parts of size t. We prove an Erdős-Hajnal-type stepping-up lemma, showing how to transform a lower bound for Rr(t) into a lower bound for Rr+1(t). As an application of this lemma, we improve a bound of Conlon-Fox-Sudakov by showing that R3(t) ≥ tct.

Joint work with M. Amir and A. Shapira.

12:20 - 14:00 Lunch
14:00 - 14:30 Ander Lamaison
Ramsey density of infinite paths

In a two-colouring 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 two-colouring 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 conjecture

A well known conjecture of Ryser states that every r-partite 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. Abu-Khazneh showed that such a characterisation is false for r = 4 by giving a computer-generated counterexample.

We construct a new family of extremal r-partite 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 r-Ryser subhypergraph. We will also discuss some new finite geometric near-extremal constructions for Ryser's conjecture.

15:00 - 15:30 Coffee break
15:30 - 16:20 Penny Haxell
Vertex-induced list edge colouring

Abstract to follow.

16:20 - 18:00 Open problem session

Tuesday, August 21

10:10 - 11:00 Michael Krivelevich
Clique coloring in dense random graphs

The 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 2-factor in sparse pseudorandom graphs efficiently

Given an n-vertex pseudorandom graph G and a potential 2-factor 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 triangle-factor 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 d-regular graphs whose second eigenvalue in absolute value is λ. Our condition λ = O(d2/(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 regularity

Obtaining 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 triangle-free graphs can be highly unstructured. For example, triangle-free graphs might have only regular partitions (in the sense of Szemerédi) of tower-type 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 C4-free, which also suffers from the fact that a graph might satisfy this property but still have only regular partitions of tower-type 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 C4 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

Did 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
Ramsey-nice families of graphs

For a finite family ℑ of fixed graphs let Rk(ℑ) be the smallest integer n for which every k-coloring of the edges of the complete graph Kn yields a monochromatic copy of some F ∈ ℑ. We say that ℑ is k-nice if for every graph G with χ(G)=Rk(ℑ) and for every k-coloring 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 k-nice 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 ≥ k0(ℑ) (or at least for infinitely many values of k), ℑ is k-nice.

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 problems

We say a graph G is Ramsey for a pair of graphs (H1, H2) if any red-/blue-colouring of E(G) contains either a red H1 or a blue H2. Much research has been devoted to determining the thresholds at which the Erdős-Rényi random graph G(n,p) becomes Ramsey for (H1, H2). 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 (K3, Kt) 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