Abstract: Consider the complete bipartite graph on n+n vertices equipped with i.i.d. edge weights. The random assignment or minimum matching problem is to find a perfect matching that minimizes the total weight $M_n$ of included edges.
If F is the common cdf of the edge weights, it turns out that the scaling of F near 0 determine the asymptotics of M_n. We say that F has pseudo-dimension q if F(t)~t^q near t=0.
The Mézard-Parisi conjecture states that the limit (in probability) of M_n is π^2/6 for q=1, and more generally that the limit of n^(-1+1/q) M_n exists. This conjecture was confirmed for q=1 by Aldous in ’01 and for q>1 by Wästlund in ’12. We extend those results to all q>0.

Abstract: Given an integer-valued matrix A of dimension lxk and an integer-valued vector b of dimension l, the Maker-Breaker (A,b)-game on a set of integers X is the game where Maker and Breaker take turns claiming previously unclaimed integers from X, and Maker's aim is to obtain a solution to the system Ax=b, whereas Breaker's aim is to prevent this. When X is a random subset of {1,...,n} where each number is included with probability p independently of all others, we determine the threshold probability p_0 for when the game is Maker or Breaker's win, for a large class of matrices and vectors. This class includes but is not limited to all pairs (A,b) for which Ax=b corresponds to a single linear equation. The Maker's win statement also extends to a much wider class of matrices which include those which satisfy Rado's partition theorem.

Abstract: A classical result of Mantel states that every graph of density larger than 1/2 contains a triangle, and this result is best possible. In this talk, we study two Mantel-inspired problems: The first one asks what is the minimum d such that any triple of graphs G1,G2,G3 on the same vertex-set all of density larger than d contains a transversal triangle, i.e., there exist three edges uv,vw,wu in G1,G2,G3, respectively. We show that d = (52 - 4*Sqrt[7]) / 81, which is asymptotically best possible witnessed by a construction discovered by Aharoni and DeVos. Moreover, their construction is asymptotically the only extremal configuration. The second problem, which is due to DeVos, McDonald and Montejano, states that every k-edge-colored graph where each color class has density more than 1/(2k-1) contains a non-monochromatic triangle.
This talk is based on joint works with E. Culver, B. Lidicky, F. Pfender and S. Norin.

Abstract: The Oberwolfach problem, posed by Ringel in 1967, asks for a decomposition of the complete graph of odd order n into edge-disjoint copies of a given cycle factor. We show that this can be achieved for all large n. We actually prove a more general result, which allows for decompositions into more general types of factors. In particular, this also resolves the Hamilton--Waterloo problem for large n. This is joint work with Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus.

Abstract: Given a (fixed) graph H, let X be the number of copies of H in the random binomial graph G(n,p). In this talk we recall the results on the asymptotic behaviour of X, as the number n of vertices grows and p is allowed to depend on n. In particular we will focus on the problem of estimating probability that X is significantly larger than its expectation, which earned the name of 'the infamous upper tail'. (Includes joint work with L. Warnke.)

Abstract: A set S is sum-free if it does not contain a triple x,y,z such that x+y=z (note x,y may not necessarily be distinct). We say that S⊆ [n] is a maximal sum-free subset of [n] if it is sum-free and it is not properly contained in another sum-free subset of [n]. Cameron and Erdős asked whether the number of maximal sum-free subsets of [n] is much smaller than the number of sum-free sets. They also gave a lower bound of 2^{⌊ n/4 ⌋} for the number of maximal sum-free sets. Together with József Balogh, Hong Liu, and Andrew Treglown, we give an exact solution to the problem: For each 1≤ i ≤ 4, there is a constant C_i such that, given any n≡ i mod 4, [n] contains (C_i+o(1)) 2^n/4. maximal sum-free sets. In this talk, I will outline the ideas and techniques used in the proof. I will also discuss some new results on the number of maximal sum-free sets in abelian groups, which are joint work with Hong Liu.

Abstract: In this talk we will consider a variety of extensions of the classical theorems of Erdős and Gallai about graphs without long paths or cycles. I will discuss recent hypergraph analogues for so-called Berge paths and cycles, generalized Turán problems where we try to maximize various subgraph counts in P_k-free graphs, and if time permits a colored analogue. The results presented will be joint work with different groups from the following: Beka Ergemlidze, Ervin Győri, Abhishek Methuku, Nika Salia, Oscar Zamora.

Abstract: We say that a family (H_1,H_2,..H_k) of graphs packs into a graph G, when there are pairwise edges disjoint copies of H_i in G. Motivated by the famous tree-packing conjecture and Ringel conjecture, we consider packing spanning D-degenerate graphs with unbounded (but still sublinear) maximal degree into the complete graph. Our proof proceeds by analysing a natural random greedy packing algorithm.
This is joint work with Peter Allen, Julia Böttcher, Jan Hladký

Abstract:A circulant graph H is a graph on n vertices that can be numbered from 0 to n-1 in such a way that, if two vertices x and ( x+d ) mod n are adjacent, then every two vertices z and ( z+d ) mod n are adjacent. The labelling in the definition is what we call the layout. Now a random circulant graph results from deleting edges of H with probability 1-p.
The general question we intend to address is how to recover the layout of a random circulant graph. In this talk I will explain how it can be done by means of eigenvectors and present a polynomial time algorithm that approximates the solution with high probability. This is a joint work with Sebastian Richter.

Abstract: Given n positive numbers a_1, ..., a_n in R consider all 2^n possible sums of them with signs + and -. How many of them can be equal? This is a variant of the so-called Littlewood-Offord problem, which was solved by Erdős in 1945 using Sperner's inequality. Since then the problem was considered in a more general setting when the numbers a_i are replaced by non-zero vectors in a R^k, the research culminating in a theorem by Kleitman (1970) for vectors a_i in arbitrary normed spaces. We consider a natural extension of the problem to the setting when a_i's are elements of a group: how many elements of the form g_1 * ... * g_n, where g_i is either a_i or a_i^{-1}, can coincide? Strengthening and generalizing some very recent results by Tiep and Vu, we establish several optimal inequalities, which, among other things, imply that the Erdős' bound for real numbers is still best possible for any torsion-free group. (Joint work with G. Šemetulskis)

Abstract: A famous conjecture of Erdős and Sós from 1963 states that every graph with average degree greater than k-1 contains any tree on k+1 vertices. A proof of the conjecture for large values of k by Ajtai, Komlós, Simonovits, and Szemerédi was announced in the early 1990's. A similar conjecture is the Loebl-Komlós-Sós conjecture stating that every graph such that at least half of its vertices have degree at least k contains any tree on k+1 vertices. Hladký, Komlós, Piguet, Simonovits, Stein, and Szemerédi proved the conjecture is asymptotically correct for large values of k.
We investigate some variations of these problems. Specifically, we partially answer a question of Simonovits by proving that a certain strengthening of the Loebl-Komlós-Sós conjecture is asymptotically correct for dense graphs. This is joint work with T. Klimošová and D. Piguet. Another result implies that the Erdős-Sós conjecture is asymptotically correct for dense graphs and trees with sublinear maximum degree. Both results are based on the celebrated Szemerédi's regularity lemma.

Abstract: We study the following bootstrap percolation process: given a connected graph G, we infect an initial set A of vertices, and in each step a vertex v becomes infected if at least a ρ-proportion of its neighbours are infected. Once infected, a vertex remains infected forever. A set A which infects the whole graph is called a contagious set. It is natural to ask for the minimal size of a contagious set.
Our main result states that for every ρ between 0 and 1, every connected graph G on n vertices has a contagious set of size less than 2ρn or a contagious set of size 1 (note that allowing the latter possibility is necessary since every contagious set has size at least one). This result is best-possible and improves previous results of Chang, Chang and Lyuu, and Gentner and Rautenbach. We also provide a stronger bound in the case of graphs of girth at least five. Both proofs exploit the structure of a minimal counterexample in a randomised fashion.
This is joint work with Andrew McDowell and Richard Mycroft.

Abstract: The theory of combinatorial limits offers analytic tools to study large combinatorial objects. In this theory, an analytic object representing large dense graphs is called a graphon. A graphon is finitely forcible if its structure is determined by finitely many subgraph densities, i.e., the asymptotic structure of graphs represented by such a graphon depends only on finitely many density constraints. Finitely forcible graphons appear in various scenarios, particularly in extremal combinatorics.
Lovász and Szegedy conjectured that all finitely forcible graphons possess a simple structure. This was disproved in a strong sense by Cooper, Král' and Martins, who showed that any graphon is a subgraphon of a finitely forcible graphon. We strenghten this result by showing for every ε > 0 that any graphon spans a 1 - ε proportion of a finitely forcible graphon.
Joint work with Daniel Král', László M. Lovász and Jonathan A. Noel.

Abstract: In this talk we consider a generalisation of Kelly's conjecture which is due Alspach, Mason, and Pullman from 1976. Kelly's conjecture states that every regular tournament has an edge decomposition into Hamilton cycles, and this was proved by K{\"u}hn and Osthus for all sufficiently large tournaments. The conjecture of Alspach, Mason, and Pullman concerns general tournaments and asks for the minimum number of paths needed in an edge decomposition of each tournament into paths. There is a natural lower bound for this number in terms of the degree sequence of the tournament and they conjecture this bound is correct for tournaments of even order.
Almost all cases of the conjecture are open and we prove many of them.
This is joint work with Allan Lo, Jozef Skokan, and John Talbot.

Abstract: Motivated by Caccetta-Haggkvist conjecture, Kelly, Kuhn and Osthus initiated the study of minimum out-degree and semi-degree conditions that force an oriented graph to contain an oriented cycle of a given length. In particular, they proved for every l>=4 that if G is a sufficiently large n-vertex oriented graph with semi-degree > n/3, then G contains an oriented cycle of length l. It is easy to show that the bound is sharp for every l not divisible by 3. However, they conjectured that for l>=4 which is a multiple of 3, one can always do better. The smallest open case, which has drawn quite some attention and was a few times mentioned in open problem sessions by Kuhn and Osthus, is the one when l=6, i.e., the case of 6-cycles.
In this talk, we will mainly focus on the 6-cycle threshold and prove that if G is a sufficiently large n-vertex oriented graph with semi-degrees > n/4+1, then it contains an oriented 6-cycle. Since the natural lower-bound n/4 coming from a blow-up of oriented 4-cycle could be improved by one when n=4k+3, our lower-bound is best possible. We also determine the semi-degree thresholds for closed walks of length l for every l>=9 which is a multiple of 3, which provides an asymptotic solution to the conjecture of Kelly, Kuhn and Osthus.
This is a joint work with Roman Glebov and Andrzej Grzesik