Abstract: A graph G is r-Ramsey for H if for any r-coloring of its edges there is a monochromatic copy of H. G is called r-Ramsey minimal for H if it is r-Ramsey for H, but no subgraph of it is r-Ramsey for H.

We study the smallest minimum degree an r-Ramsey-minimal graph for the clique K_k can have. This function was introduced and determined for two colors by Burr, Erdős and Lovász in 1975. We extend their theorem for r colors and connect the function to the so-called Erdős-Rogers function, which was introduced and studied more than a decade earlier.

Abstract: Given natural numbers n, k with 2 ≤ k < n/2. We write ([n] choose k) for the family of all subsets of size k of [n]. The Kneser graph K(n, k) is the graph whose vertex set is ([n] choose k ) where two sets A, B ∈ ([n] choose k ) are adjacent if and only if A ∩ B = ∅. The celebrated theorem of Erdős-Ko-Rado from 1961 says that every independent set in K(n, k) has size at most (n - 1 choose k - 1), and the only independent sets of this size are stars.

We prove a removal lemma for these graphs. Loosely speaking, it tells us that every subfamily of ([n] choose k) of size roughly (n - 1 choose k - 1) with few disjoint pairs must be very close to a star. Armed with this lemma, we establish a sparse version of the Erdős-Ko-Rado theorem. This settles a question of Bollobás, Narayanan and Raigorodskii (2014).

Abstract: A problem mentioned by Chung in 1987: given a plane graph and an integer d, is it possible to reduce the diameter of the graph to at most d by adding non-edges, while conserving planarity? Fellows and Dejter have shown in an unpublished paper in 1993 that the oriented case was NP-Complete and that both the oriented and undirected cases were FPT (FIxed Parameter Tractable). But their proof is mostly based on the Robertson and Seymour theorem and is therefore non-constructive as of yet.

This type of result is in essence theoretical, but it gives us good hopes of finding efficient FPT algorithms. We will focus on a natural variant of this problem in the undirected case, where the number of edges that can be added per face is upper-bounded by an integer k. We will then give an FPT algorithm (parameterized by d and k) for this variant, build on dynamic programming.

Abstract: A class of graphs C satisfies the Erdős–Pósa property if there exists a function f such that, for every integer k and every graph G, either G contains k vertex-disjoint subgraphs each isomorphic to a graph in C, or there is a subset S of V(G) of at most f(k) vertices such that G ∖ S has no subgraph in C. Erdős and Pósa (1965) proved that the set of all cycles satisfies this property for all graphs with f(k) = O(k log k). Given a connected graph H, let M(H) be the class of graphs that contain H as a minor. Robertson and Seymour (1986) proved that M(H) satisfies the Erdős-Pósa property if and only if H is planar. When H is planar, finding the smallest possible function f_M(H) has been an active area of research in the last years. In this talk we will survey some recent combinatorial and algorithmic results in this direction, and we will particularly focus on other variants of the Erdős–Pósa property such as the case where the k subgraphs have to be edge-disjoint or the case where M(H) is the class of graphs that contain a graph H as a topological minor.

Abstract: In the last years, several authors have studied sparse and random analogues of a wide variety of results in extremal combinatorics. Very recently, due to the work of Balogh, Morris, and Samotij, and the work of Saxton and Thomasson on the structure of independent sets on hypergraphs, several of these questions have been addressed in a new framework by using the so-called containers in hypergraphs.

In this talk I will present how to use this technology together with arithmetic removal lemmas due to Serra, Vena and Kral in the context of arithmetic combinatorics. We will show how to get sparse (and random) analogues of well-known additive combinatorial results even in the non-abelian situation.

Abstract: One of the most classic results in Extremal Graph Theory is Turán's Theorem, which guarantees the existence of cliques of given order r in a graph G, provided that its edge density d exceeds a certain threshold. Naturally, one may wonder how many such cliques must necessarily be contained in G when the edge density d becomes larger than this threshold. Lovász and Simonovits [1] conjectured their number to be at least F_r(d)n^r + O(n^r-2), where F describes a certain piecewise concave function. After some partial results in the last decades, the conjecture was proven by Christian Reiher [2] recently, by using weighted graphs and Lagrange multipliers which help to transfer this discrete problem into a continuous setting. In the talk we will see a construction showing that the above bound is tight asymptotically and then we will see an overview on the proof by Christian Reiher.

[1] L. Lovász and M. Simonovits: On the number of complete subgraphs in a graph II, Studies in pure mathematics, pages 459-495, Birkhäuser, 1983.

Abstract: A selection of fascinating open problems in all areas of Ramsey Theory will be presented. These problems were collected at the AIM Graph Ramsey Theory workshop, San Jose, January 2015.

Abstract: The (hyper)graph removal lemma says that if a large (hyper)graph K does not have many copies of a given (hyper)graph H, then K can be made free of copies of H by deleting a small number of edges.

An arithmetic removal lemma says the following. Given a group G and some subset X_i of G, if a linear system Ax = 0 does not have many solutions with x_i in X_i, then we can obtain new sets X_i' where the linear system Ax = 0 does not have any solutions if the variables x_i take values in X_i'. The sets X_i' have been obtained from X_i by removing few of its elements.

One of the applications of the arithmetic removal lemmas is a more direct proof of Szemerédi's Theorem, regarding finding arbitrarily long arithmetic progressions on the integers (or in other groups), and its multidimensional counterpart, regarding finding k-dimensional simplicies in Z^k.

Abstract: Aharoni and Berger conjectured that every bipartite graph which is the union of n matchings of size n + 1 contains a rainbow matching of size n. This conjecture is a generalization of several old conjectures of Ryser, Brualdi, and Stein about transversals in Latin squares.