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: 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.