28.08.2019

Alexandra Wesolek
(Simon Fraser University)

14.08.2019

Hiệp Hàn
(University of Santiago de Chile)

10.06.2019

Hao Huang
(Emory University)

03.07.2019

Nina Kamcev
(Monash University)

26.06.2019

Mara Nehring
(FU Berlin)

19.06.2019

Tamás Mészáros
(FU Berlin)

13.06.2019

Tibor Szabó
(FU Berlin)

05.06.2019

Anurag Bishnoi
(FU Berlin)

22.05.2019

William T. Trotter
(Georgia Institute of Technology)

15.05.2019

Piotr Micek
(Jagellonian University Krakow and TU Berlin)

08.05.2019

Tuan Tran
(ETH Zürich)

02.05.2019

Joonkyung Lee
(Universität Hamburg)

24.04.2019

Ander Lamaison
(FU Berlin)

17.04.2019

Simona Boyadzhiyska
(FU Berlin)

10.04.2019

Andrew Treglown
(University of Birmingham)

06.03.2019

Tibor Szabó
(FU Berlin)

Jan van den Heuvel
(LSE)

Ferdinand Ihringer
(Ghent University)

Rank Bounds on the Independence Number

David Fabian
(FU Berlin)

Rainbow arithmetic progressions and anti-van der Waerden numbers

László Kozma
(FU Berlin)

Hamiltonicity below Dirac's condition

Anurag Bishnoi
(FU Berlin)

Non-intersecting Ryser hypergraphs

Jan Corsten
(LSE)

Erdős-Rothschild problem for five and six colours

Péter Pál Pach
(BME)

Polynomial Schur's theorem

Christoph Spiegel
(UPC)

Intervals in the Hales-Jewett Theorem

Jozef Skokan
(LSE)

The k-colour Ramsey number of odd cycles via non-linear optimisation

Alexandra Wesolek
(FU Berlin)

Bootstrap percolation in Ore-type graphs

Hong Liu
(Warwick)

Enumeration in arithmetic setting

Andrew Newman
(TU Berlin)

Small simplicial complexes with large torsion in homology

Sophia Elia
(FU Berlin)

A comparison of Quotient Posets

Patrick Morris
(FU Berlin)

On the discrepancy of permutation families

Tamás Mészáros
(FU Berlin)

Sample compression schemes

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Abstract: Rainbow saturation asks for the minimum number of edges in a t-edge-coloured graph G such that it does not contain a rainbow copy of some fixed graph H but adding any missing edge in any colour from [t] completes a rainbow copy of H. It is an extension of the uncoloured saturation problem which was first studied by Erdős, Hajnal and Moon in 1964. Surprisingly, if H=K_s, the complete graph on s vertices, and G is a graph on n vertices, the minimum number of edges that we need is Θ(n log n) while in the uncoloured saturation problem we only need a linear number of edges. In this work we investigate weak versions of rainbow saturation. In the usual rainbow saturation problem we can choose an arbitrary ordering of the missing edges and add all the missing edges back to the graph in that order and in arbitrary colours completing a rainbow copy each time we add an edge. Instead of being able to add the edges in any ordering to the graph, in a weaker setting we ask for only one specific ordering in which we need to be able to add them back. Is the behaviour for the minimum sets in this case still Θ(n log n)? In the uncoloured setting the bound for this weakened version is linear, so the answer needs to be between these bounds. Moreover, we investigate how the problem changes if we are allowed to choose a colour for every edge that we add. What if we can choose the colours and an ordering? We give answers to those questions. This represents joint work with Shagnik Das.

Abstract: Words are finite sequences of letters over a finite alphabet and in this talk we address two intimately related topics for this object: quasi-randomness and limit theory.With respect to the first topic we study the notion of uniform distribution of letters over intervals, and in the spirit of the famous Chung-Graham-Wilson theorem we provide a list of word properties which are equivalent to this property. This investigation naturally gives rise to a notion of convergent word sequences, and in the second part of our work we develop a limit theory for such sequences. Via this theory we address several problems such as property testing and finite forcibility and obtain as a byproduct a new model of random word sequences.Joint work with Matias Pavez-Signe and Marcos Kiwi.

Abstract: A classical theorem of Kleitman in extremal combinatorics states that a collection of binary vectors in {0,1}ⁿ with diameter d has cardinality at most that of a Hamming ball of radius d/2.

In this talk, we present a new proof of Kleitman's diametric theorem via spectral methods, and discuss some extensions and generalizations of Kleitman's Theorem, as well as a few other related extremal problems.

Joint work with Oleksiy Klurman (KTH) and Cosmin Pohoata (Caltech).

Abstract: We prove an asymptotic formula for the number of k-uniform hypergraphs with a given degree sequence, for a wide range of parameters. In particular, we can asymptotically enumerate d-regular k-graphs of density O(1/k) for 3 ≤ k< n^1/10. This extends the recent results for graphs of Liebenau and Wormald.

It follows that within our scope, the distribution of the degree sequence of a random k-uniform hypergraph can be approximated by a sequence of independent random variables with the appropriate binomial distribution. This is joint work with Anita Liebenau and Nick Wormald. 

Abstract: The Online Ramsey Game is a game on an unbounded number of vertices played by two players, Builder and Painter. Builder builds an edge between two vertices and Painter paints it immediately red or blue. Builder's goal is to build a monochromatic red copy of K_m or a monochromatic blue copy of K_n while Painter tries to delay this for as long as possible. The online Ramsey number is the minimum number of edges Builder needs to guarantee a win regardless of Painter's strategy. We will show new lower and upper bounds for the online Ramsey number.

Work by David Conlon, Jacob Fox, Andrey Ginshpun and Xiaoyu He.

Abstract: I will be presenting recent work by Chalopin, Chepoi, Moran and Warmuth.

"We examine connections between combinatorial notions that arise in machine learning and topological notions in cubical/simplicial geometry. These connections enable to export results from geometry to machine learning. Our first main result is based on a geometric construction by Tracy Hall (2004) of a partial shelling of the cross polytope which can not be extended. We use it to derive a maximum class of VC dimension 3 that has no corners. This refutes several previous works in machine learning from the past 11 years. In particular, it implies that all previous constructions of optimal unlabeled sample compression schemes for maximum classes are erroneous.
On the positive side we present a new construction of an unlabeled sample compression scheme for maximum classes. We leave as open whether our unlabaled sample compression scheme extends to ample (a.k.a. lopsided or extremal) classes, which represent a natural and far-reaching generalization of maximum classes. Towards resolving this question, we provide a geometric characterization in terms of unique sink orientations of the 1-skeletons of associated cubical complexes."

Abstract: A construction of Alon and Krivelevich gives highly pseudorandom K_k-free graphs on n vertices with edge density equal to Θ(n^-1/(k-2)). In this talk I will give a construction of an infinite family of highly pseudorandom K_k-free graphs with a higher edge density of Θ(n^-1/(k-1)), for all k≥3, using the geometry of quadratic forms over finite fields. 

(Joint work with Ferdinand Ihringer and Valentina Pepe.)

Abstract: Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges E₀, and infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges E_t ⊆ E(K_n), we infect a non-infected edge e if it completes a new copy of H in G=([n], E_t ∪ e). A question raised by Bollobás asks for the maximum time the process can run before it stabilizes.  Bollobás,  Przykucki,  Riordan, and  Sahasrabudhe considered this problem for the most natural case where H=K_r. They answered the question for r ≤ 4 and gave a non-trivial  lower bound for every r ≤ 5. They also conjectured that the maximal running time is o(n²) for every integer r. In a joint work with József Balogh, Gal Kronenberg, and Alexey Pokrovskiy we disprove their conjecture for every r ≥ 6 and we give a better lower bound for the case that r=5 using Behrend's construction of large 3-term arithmetic progression-free sets of integers.

Abstract: The maximum degree of a poset is the maximum degree in the associated comparability graph. For an integer k, let f(k) denote the maximum dimension of a poset P with maximum degree k. It was shown in 1991 by Erdős, Kierstead and Trotter that f(k) = Ω(k logk). In 1986, Füredi and Kahn showed that f(k) = O(k log²k). Just in 2018, Scott and Wood made the following subtle but dramatic improvement: f(k) = O(log^1+o(1)k). We outline the proof which uses an iterated application of the Lovász Local Lemma.

Abstract: A p-centered coloring of a graph G is a coloring of its vertices such that for every connected subgraph H of G either H receives more than p colors or there is a color that appears exactly once in H. Very recently, we have shown that every planar graph admits a p-centered coloring with O(p³ log(p)) colors. This improves an O(p¹⁹) bound by Pilipczuk&Siebertz. We also know that some planar graphs require Omega(p² log(p)) colors. We have tight bounds for outerplanar graphs, stacked triangulations, and graphs of bounded treewidth.

Ongoing work with Stefan Felsner and Felix Schröder.

Abstract: The problem of finding dense induced bipartite subgraphs in H-free graphs has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer. We obtain several results in this direction. First we prove that any H-free graph with minimum degree at least d contains an induced bipartite subgraph of minimum degree at least c_H log d/log log d, confirming (asymptotically) several conjectures by Esperet, Kang and Thomassé. Complementing this result, we further obtain optimal bounds for this problem in the case of dense triangle-free graphs, and we also answer a question of Erdős, Janson, Luczak and Spencer.

Joint work with Kwan, Letzter and Sudakov.

Abstract: The extremal number ex(n, H) is the maximum number of edges in an H-free graph with n vertices. When H has chromatic number at least three, the asymptotic behaviour of the extremal number is well understood, but when H is bipartite, the function remains mysterious. We give new estimates for the extremal numbers of various bipartite graphs H, especially if H can be obtained by subdividing edges of another graph H' in certain ways. Joint work with David Conlon and Oliver Janzer.

Abstract: Let H be an infinite graph. In a two-coloring of the edges of the complete graph on the natural numbers, what is the densest monochromatic subgraph isomorphic to H that we are guaranteed to find? We measure the density of a subgraph by the upper density of its vertex set. This question, in the particular case of the infinite path, was introduced by Erdős and Galvin. Following a recent result for the infinite path, we present bounds on the maximum density for other choices of H, including exact values for a wide class of bipartite graphs.

Abstract: After the question of existence of a combinatorial structure satisfying given properties, a natural and important problem is to determine how many such objects there are. In this talk, we will consider some counting questions related to (mutually) orthogonal Latin squares. We will prove an upper bound on the number of ways to extend a set of k mutually orthogonal Latin squares to a set of k+1 mutually orthogonal Latin squares and discuss some applications, comparing the resulting bounds to previously known lower and upper bounds.

This talk is based on joint work with Shagnik Das and Tibor Szabó.

Abstract: A classical topic is graph theory concerns finding minimum degree conditions that force a given spanning subgraph in a graph. There has also been interest in generalising such results via degree sequence conditions. Komlós' theorem determines the minimum degree that forces an H-tiling in a graph G covering a given proportion of the vertices in G. (An H-tiling is simply a collection of vertex-disjoint copies of H in G.) In this talk we will discuss a degree sequence generalisation of this result. This is joint work with Hong Liu and Joseph Hyde.

Abstract: We introduce the list colouring extension of classical Ramsey numbers, investigate when the two Ramsey numbers are equal, and in general, how far apart they can be from each other. We find graph sequences where the two are equal and where they are far apart. For l-uniform cliques we prove that the list Ramsey number is bounded by an exponential function, while it is well-known that the Ramsey number is super-exponential for uniformity at least 3. This is in great contrast to the graph case where we cannot even decide the question of equality for cliques. Joint work with Noga Alon, Matija Bucic, Tom Kalvari, and Eden Kuperwasser.

Abstract: Hadwiger's Conjecture (1943) asserts that every graph without the complete graph K_t+1 as a minor has a proper vertex-colouring using at most t colours. Since the conjecture is stubbornly refusing to be proved, we might look at relaxed versions of it. In the talk we discuss some results around the following question: If we are given t colours to colour a graph without K_t+1-minor, what kind of vertex-colourings can we guarantee with those t colours?

Abstract: Recently, the breakthrough results by Croot, Lev, and Pach on progression-free sets in ℤ₄ⁿ and by Ellenberg and Gijswijt on cap sets brought new attention to rank arguments for bounding sets in combinatorial problems. We discuss several traditional applications of rank arguments to bound the independence number of a graph. The examples include the orthogonality graph on {-1,1}ⁿ, generalized quadrangles, Hermitian dual polar graphs, and quasisymmetric designs.

Abstract: Given a colouring of a set in an ambient abelian group, a rainbow arithmetic progression is an arithmetic progression whose elements receive pairwise distinct colours. We are going to consider two related problems that have been studied over the last years: First we ask whether any k-colouring of [n] with equally sized colour classes admits a rainbow arithmetic progression of length k. The second problem is to find the smallest positive integer r, for which every r-colouring of [n] contains a rainbow k-AP. We shall also have a look at the analogous problems when [n] is replaced by a finite abelian group.

Abstract: Dirac's theorem (1952) is a classical result of graph theory, stating that an n-vertex graph (n≥3) is Hamiltonian if every vertex has degree at least n/2. Both the value n/2 and the requirement for every vertex to have high degree are necessary for the theorem to hold. In this work we give efficient algorithms to determine whether a graph is Hamiltonian when either of the two conditions are relaxed.

Joint work with Bart Jansen and Jesper Nederlof.

Abstract: A famous conjecture of Ryser states that every r-partite hypergraph has vertex cover number at most r − 1 times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as r-Ryser hypergraphs, have been studied extensively. It was proved by Haxell, Narins and Szabó that all 3-Ryser hypergraphs with matching number ν > 1 are essentially obtained by taking ν disjoint copies of intersecting 3-Ryser hypergraphs. In this talk we will see new infinite families of r-Ryser hypergraphs, for any given matching number ν > 1, that do not contain two vertex disjoint intersecting r-Ryser subhypergraphs.

Abstract: Given positive integers n,r,k, the Erdős-Rothschild problem asks to determine the largest number of r-edge-colourings without monochromatic k-cliques a graph on n vertices can have. In the case of triangles, i.e. when k=3, the solution is known for r = 2,3,4. We investigate the problem for five and six colours.

Abstract: We consider the Ramsey problem for the equation x+y=p(z), where p is a polynomial with integer coefficients. Under the assumption that p(1)p(2) is even we show that for any 2-colouring of ℕ the equation x+y=p(z) has infinitely many monochromatic solutions. Indeed, we show that the number of monochromatic solutions with x,y,z∈ {1,2,\dots,n} is at least n^{2/d^3-o(1)}, where d=deg p.

On the other hand, when p(1)p(2) is odd, that is, when p attains only odd values, then there might not be any monochromatic solution, e.g., this is the case when we colour the integers according to their parity. We give a characterization of all 2-colourings avoiding monochromatic solutions to x+y=p(z).

This is a joint work with Hong Liu and Csaba Sándor.

Abstract:  The Hales–Jewett Theorem states that any r–colouring of [m]ⁿ contains a monochromatic combinatorial line if n is large enough. Shelah’s proof of the theorem implies that for m = 3 there always exists a monochromatic combinatorial lines whose set of active coordinates is the union of at most r intervals. I will present some recent findings relating to this observation. This is joint work with Nina Kamcev.

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. We show that for fixed k > 2  and n odd and sufficiently large, 

R_k(C_n) = 2^_k-1(n-1) + 1.

This generalises a result of Kohayakawa, Simonovits and Skokan and resolves a conjecture of Bondy and Erdős for large n. We also establish a surprising correspondence between extremal k-colourings for this problem and perfect matchings in the hypercube Q_k. This allows us to in fact prove a stability-type generalisation of the  above. The proof is analytic in nature, the first step of which is to use the Regularity Lemma to relate this problem in Ramsey theory to one in convex optimisation.

This is joint work with Matthew Jenssen.

Abstract: In the r-neighbour bootstrap process on a graph G we start with an initial set of infected vertices A₀ ⊆ V(G) and a new vertex gets infected as soon as it has r infected neighbours. We call A₀ percolating if an infection of A₀ infects all of our graph. Under which conditions on G can we find a small percolating set A₀? In general, the denser our graph is the easier it is to infect new vertices as the initially infected vertices share potentially more neighbours. If v(G) ≤ r then we need to infect at least r vertices initially to infect all of our graph otherwise we will not be able to infect any new vertices during the bootstrap process. Gunderson showed that if a graph G on n vertices has minimum degree δ(G) ≤ ⌊ n/2 ⌋ + r - 3 then we can always find a percolating set of size r (if r ≤ 4 and n is big enough). How much can we decrease the minimum degree conditions if we are initially allowed to infect r+k vertices for k ∈ ℕ? What if we consider more general graphs where the sum of the degrees of any two non-adjacent vertices x and y is deg(x) + deg(y) ≤ D? This is more general because if a graph G has δ(G) = D/2 then for any two vertices in G it holds that deg(x) + deg(y) ≤ D. In this talk we give conditions on D=D(r,k) that guarantee a percolating set of size r + k, answering both open questions at once for small enough k=k(r).

Abstract: I will discuss several recent extremal results on enumerating subsets of integers/groups with various additive and multiplicative constraints.

Abstract: From the work of Kalai on ℚ-acyclic complexes it is known that for d ≥ 2 a d-dimensional simplicial complex on n vertices can have enormous torsion, on the order of exp(Θ_d(n^d)), in its (d-1)st homology group. However, explicit constructions of complexes which realize this enormous-torsion phenomenon have been somewhat rare. Therefore, in this talk we consider and affirmatively answer the following inverse question: Given a finite abelian group of order m, can one always construct a d-dimensional simplicial complex on Θ_d((log m)^_1/d) vertices which realizes the given group in its (d - 1)st homology group? 

Abstract: Given an equivalence relation on the elements of a poset, place a new relation on the equivalence classes of elements. If this new relation is reflexive, antisymmetric, and transitive, then a quotient poset is created. We survey different types of quotient posets and see how they compare. In particular, we look at quotient posets that arise from lattice congruences, order-preserving group actions, and as images of surjective maps. We characterize quotient posets that correspond to a certain relation on equivalence classes by defining a sequence related to transitivity. Then we look at an application of quotient posets arising from order-preserving group actions. Let Hom(P,n) be the set of order-preserving maps from a poset P to a chain with  elements. Stanley showed that |Hom(P,n)| is given by a polynomial in . Given an order-preserving group action on P, there is an induced group action on Hom(P,n). Katharina Jochemko showed that the number of maps in Hom(P,n)up to equivalence under the induced group action is also polynomial in  using quotient posets. We touch on an alternative approach to the proof through the Ehrhart theory of order polytopes.

Abstract: For a set family S⊆ 2ⁿ, the discrepancy of S is 

disc(S):=min_χ:[n]→±1 max_S∈ S |∑_x∈S χ(x)|.

One can think of this as a colouring problem. Given a set system, we are interested in colouring the ground set red/blue such that in every set the difference between the number of red and number of blue points is as small as possible. Given a set of permutations π₁,...,π_k on [n], we can define a set family S(π₁,...,π_k) by taking all sets that occur as intervals in each of the permutations. Formally, 

S(π₁,...,π_k):={ {π_j(x),π_j(x+1),...,π_j(y)} : 1≤x≤y≤n, j∈[k] }.

How large can the discrepancy of such a family be?

It turns out that for any n∈ ℕ and two permutations, π,σ on [n], we have that disc(S(π,σ))≤ 2. What about three permutations?  Beck conjectured (around 1987) that this should also be bounded by a constant. In 2009, Matoušek described this as ``one of the most tantalising questions in combinatorial discrepancy". In this talk, we will present the eventual resolution of this conjecture by Newman and Nikolov in 2011. The talk will end with an invitation to an open problem. 

Abstract: In this talk we concentrate on two fundamental concepts of classical machine learning theory: learning and compression. Motivated by the fact that if a concept class admits a small sample compression scheme then it is efficiently learnable (Littlestone and Warmuth), we propose to study the relationship between the size of sample compression schemes and the combinatorial notion of VC dimension. In particular, we propose several directions to tackle the compression scheme conjecture which states that the smallest possible size of a sample compression scheme is linear in the VC dimension of the underlying concept class.

Abstract: Consider the random process in which the edges of a graph G are added one by one in a random order. A classical result states that if G is the complete graph K_2n or the complete bipartite graph K_n,n, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary k-regular bipartite graphs G on 2n vertices for all k=Ω(n). Surprisingly, this is not the case for smaller values of k. We construct sparse bipartite k-regular graphs in which the last isolated vertex disappears long before a perfect matching appears.  Joint work with Zur Luria and Michael Simkin.