Abstract: Consider the uniform random graph G(n, M) with n vertices and M edges. Erdős and Rényi (1960) conjectured that the limit lim P[G(n, n/2) is planar] exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability.

In this work we determine the exact probability of a random graph being planar near the critical point M = n/2. More precisely, for each u, we find an exact analytic expression for

p(u) = lim P[G(n, n/2(1 + u n^-1/3) is planar]

In particular, we obtain p(0) is approximately equal to 0.99780. Additionally, we are also capable to extend these results to classes of graphs closed under taking minors.

Abstract: Let H be a non-bipartite graph. Pfender conjectured that for large ℓ depending on H, every balanced ℓ-partite graph whose parts have pairwise edge density greater than (χ(H) - 2)/(χ(H) - 1) contains a copy of H. He verified the conjecture for cliques. In this work, we show that the same premise implies the existence of much larger graphs. As a consequence, we confirm the conjecture for a family of graphs. Finally, we disprove the conjecture in general by constructing several families of counterexamples.

Abstract: Growing sequences of dense graphs have a limit object in terms of a symmetric measurable 2-variable function. A typical use of this fact in graph theory is the following: we want to prove a result, say an inequality between subgraph densities. We look at a sequence of counterexamples, and consider their limit. Often this allows clean formulations and arguments that would be awkward or impossible in the finite setting.

Abstract: A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets L₁, ..., L_n there exists a nonrepetitive sequence s₁, ..., s_n with s_i ∈ L_i. We propose a new non-constructive way to build long nonrepetitive sequences and provide an elementary proof that sets of size 4 suffice confirming the best known bound. The simple double counting (entropy compression method) in the heart of the argument is inspired by the recent algorithmic proof of the Lovász local lemma due to Moser and Tardos.

We will discuss recent results concerning nonrepetitive colorings of graphs with a special emphasis on applications of entropy compression method.

Abstract: Let A and B be subsets of a finite abelian group G. We say that A + B contains a unique sum if there exists g ∈ G such that g = a + b for exactly one pair (a, b) ∈ A × B. Unique differences are defined analogously.

The main goal in the investigation of these phenomena is to find sufficient conditions for the existence of unique sums and differences. Such results have a variety of applications, for instance, in the context of cyclotomic integers of small modulus, field extensions, spectral properties of subsets of F_p, balanced sets, and circulant weighing matrices.

I will present a new method to study unique sums and differences, which mainly relies on the Smith Normal Form of the corresponding linear relations. This yields substantial improvements upon previously known results. For instance, we obtain the following.

Abstract: Many real-life networks have an inherent geometry, which should be reflected in the random graph models used to analyse their behaviour. A typical example is that of radio networks: radio devices may find it easier to exchange information if they lie close to each other than if they lie far apart. This and other examples have motivated research into specifically geometric models of random graphs.

Abstract: We will look at the Maker-Breaker H-game played on the edge set of the random graph G_n,p. In this game two players, Maker and Breaker, alternately claim unclaimed edges of G_n,p, until all the edges are claimed. Maker wins if he claims all the edges of a copy of a fixed graph H; Breaker wins otherwise.

It turns out that, with the exception of trees and triangles, the threshold for this game is given by the threshold of the corresponding Ramsey property of G_n,p with respect to the graph H.

Abstract: Turán densities of hypergraphs are an important object of study in the field of extremal combinatorics. Despite a substantial amount of research, many basic questions are still open, the most famous one being Turán's conjecture from 1941 on the density of K₄³ (the complete 3-graph on 4 vertices).

Abstract: A graph G is Ramsey for H if every two-colouring of the edges of G contains a monochromatic copy of H. Two graphs H and H' are Ramsey-equivalent if every graph G is Ramsey for H if and only if it is Ramsey for H'. In the talk we discuss the problem of determining which graphs are Ramsey-equivalent to the complete graph K_k. In particular we prove that the only connected graph which is Ramsey-equivalent to K_k is itself. This gives a negative answer to a question of Zumstein, Zürcher, and the speaker. For the proof we determine the smallest possible minimum degree that a minimal Ramsey graph for K_k ⋅ K₂ (the graph containing the clique with a pendant edge) can have.

Abstract: We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study bipartite graph families which are defined by their 3-connected components.

More precisely, in this talk I will explain how to get the counting formulas for bipartite series-parallel graphs (and more generally of the Ising model over this family of graphs), as well as asymptotic estimates for the number of such graphs with a fixed size.

Abstract: We prove the following two conjectures of Thomassen on highly connected tournaments:

(i) For every k, there is an f(k) so that every strongly f(k)-connected tournament contains k edge-disjoint Hamilton cycles (joint work with Kühn, Lapinskas and Patel).

(ii) For every k, there is an f(k) so that every strongly f(k)-connected tournament has a vertex partition A, B for which both A and B induce a strongly k-connected tournament (joint with Kühn and Townsend).

Abstract: Sidorenko's conjecture states that if H is a bipartite graph then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. It is known to be true for various families of graphs, including trees, even cycles and bipartite graphs with one vertex complete to the other side.

We take a look at the paper by Li and Szegedy where they establish the logarithmic calculus.

This is their abstract:

Abstract: We say that a set system F ⊆ 2^[n] shatters a given set S ⊆ [n] if 2^S = {F ∩ S : F ∈ F}. One related notion is the VC-dimension of a set system: the size of the largest set shattered by F. The Sauer inequality states that in general, a set system F shatters at least |F| sets. A set system is called shattering-extremal if it shatters exactly |F| sets. Here we present two methods, one algebraic and one graph theoretical, to study shattering-extremal set systems.

When considering a set system as a set of characteristic vectors, one can define the corresponding vanishing ideal of polynomials. The standard monomials and Gröbner bases of these ideals can be used to characterize extremal set systems and to obtain many interesting results in connection with these combinatorial objects. This algebraic characterization leads to an efficient method for testing extremality.

Abstract: A (directed) graph is k-linked if for two sets of vertices {x₁, ..., x_k} and {y₁, ..., y_k}, there are vertex disjoint paths {P₁, ..., P_k}, such that P_i goes from x_i to y_i. A theorem of Bollobas and Thomason says that every 22k-connected (undirected) graph is k-linked. It is desirable to obtain analogues for directed graphs as well. Although Thomassen showed that the Bollobas-Thomason Theorem does not hold for general directed graphs, for tournaments he showed that there is a function f(k) such that every strongly f(k)-connected digraph is k-linked. The bound on f(k) was reduced to O(k log k) by Kuhn, Lapinskas, Osthus, and Patel, who also conjectured that a linear bound should hold. We'll talk about a proof of this conjecture.

Abstract: We investigate subsets of finite abelian groups which maximize the number of r-colourings without monochromatic Schur triples, i.e. without triples of the form (a, b, c) such that a + b = c. For r = 2, 3 and abelian groups G of order |G| = 2 mod 3 we show that the maximum is achieved only by largest sum-free sets. For abelian groups of even order and r = 4 the maximum is achieved by the union of two largest sum-free sets, whenever they exist.

Abstract: Ein lateinisches Quadrat der Ordnung n ist ein n x n Feld bestehend aus n² Zellen, welche mit n verschiedenen Symbolen gefüllt sind, wobei in jeder Zeile und jeder Spalte jedes Symbol genau einmal vorkommen darf. Eine Menge aus n Zellen, genau eine aus jeder Zeile und jeder Spalte, bestehend aus k verschiedenen Symbolen, heißt partielles Transversal der Länge k.