Combinatorics Seminar 2013/2014

Talks take place at Arnimallee 3, 14195 Berlin, Room 210 at 16:15, unless stated otherwise.

DateSpeakerTitle
16.10.2013 Juanjo Rué
FU Berlin
On the probability of planarity of a random graph near the critical point
23.10.2013 Tuan Tran
FU Berlin
Subgraphs of dense multipartite graphs
31.10.2013 László Lovász
Eötvös Loránd University
Extremal graphs and graph limits
06.11.2013
14:15 SR119
Peter Keevash
University of Oxford
Dynamic concentration of the triangle-free process
13.11.2013 Frederik Garbe
FU Berlin
On Graphs with Excess 2
20.11.2013 Piotr Micek
Jagiellonian University
Nonrepetitve sequences, colorings and entropy compression method
27.11.2013
14:15 SR119
Alexey Pokrovskiy
FU Berlin
Nonnegative sums in a set of numbers
11.12.2013 Kathleen Johst
FU Berlin
The k-color Ramsey number of a graph with m edges
17.12.2013
14:15
Bernhard Schmitt
Nanyang Technological University, Singapore
Unique Sums and Differences in Finite Abelian Groups
18.12.2013
14:15 SR119
Christian Reiher
University of Hamburg
Counting odd cycles in locally dense graphs
17.01.2014
9:30 SR 130
Sylwia Antoniuk
Adam Mickiewicz University
Random triangular groups
22.01.2014
14:15
Juanjo Rué
FU Berlin
Reading Group: Independent Sets in Hypergraphs Part 1 - Introduction
24.01.2014
9:30 SR 130
Victor Falgas-Ravry
Umeå University
On the connectivity of k-nearest-neighbours random geometric graphs
29.01.2014 Julia Ehrenmüller
TU Hamburg-Harburg
On the intersection of longest paths
29.01.2014 Miloš Stojaković
University of Novi Sad
Threshold for Maker-Breaker H-game
31.01.2014
9:30 SR 130
Dennis Clemens
FU Berlin
Lothar Narins
FU Berlin
Reading Group: Independent Sets in Hypergraphs Part 2 - The Proof
12.02.2014
14:15
Codruţ Grosu
FU Berlin
Tuan Tran
FU Berlin
Reading Group: Independent Sets in Hypergraphs Part 3 - The Proof Continued
19.02.2014
14:15
Alexey Pokrovskiy
FU Berlin
Reading Group: Independent Sets in Hypergraphs Part 4 - Applications
26.02.2014
13:15
Alexey Pokrovskiy
FU Berlin
Reading Group: Independent Sets in Hypergraphs Part 5 - The KŁR Conjecture
05.03.2014
14:15
Codruţ Grosu
FU Berlin
An algebraic approach to Turán densities
31.03.2014
10:15
Simeon Ball
Universitat Politècnica de Catalunya
On the Turán number of complete bipartite graphs
09.04.2014
14:15
Tibor Szabó
FU Berlin
What is Ramsey-equivalent to a clique?
30.04.2014
14:15
Juanjo Rué
FU Berlin
Applications of Tutte's tree decomposition in the enumeration of bipartite graph families
05.05.2014
10:15
Deryk Osthus
University of Birmingham
Proof of Two Conjectures of Thomassen on Tournaments
07.05.2014
14:15
Lothar Narins
FU Berlin
Tau and the Connectedness of Line Graphs
14.05.2014
14:15
Olaf Parczyk
FU Berlin
On the logarithmic calculus and Sidorenko's conjecture
23.05.2014 - 24.05.2014 Berlin - Poznań Seminar (Hamburg)
05.06.2014
10:15
Lander Ramos
Universitat Politècnica de Catalunya
Random planar graphs with minimum degree two
11.06.2014
14:15
Tamás Mészáros
Central European University
Shattering extremal set systems
18.06.2014
14:15
Alexey Pokrovskiy
FU Berlin
Linkage structures in tournaments
25.06.2014
14:15
Alexey Pokrovskiy
FU Berlin
Linkage structures in tournaments (part II)
09.07.2014 Hiệp Hàn
Emory University
Maximum number of colourings without monochromatic Schur triples
10.07.2014
14:15
Alice Händel
FU Berlin
Partielle Transversale in Lateinischen Quadraten

Abstracts:

16.10.2013
Juanjo Rué (FU Berlin)
On the probability of planarity of a random graph near the critical point

Abstract: Consider the uniform random graph G(nM) with n vertices and M edges. Erdős and Rényi (1960) conjectured that the limit lim P[G(nn/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(nn/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.

This is a joint work with Marc Noy (UPC-Barcelona) and Vlady Ravelomanana (LIAFA-Paris).
23.10.2013
Tuan Tran (FU Berlin)
Subgraphs of dense multipartite graphs

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.

This is a joint work with Lothar Narins.
31.10.2013
László Lovász (Eötvös Loránd University)
Extremal graphs and graph limits

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.

This setting also allows us to pose and in some cases answer general questions about extremal graph theory: which inequalities between subgraph densities are valid, and what is the possible structure of extremal graphs.
06.11.2013
Peter Keevash (University of Oxford)
Dynamic concentration of the triangle-free process
Abstract: The triangle-free process begins with an empty graph on n vertices and iteratively adds edges chosen uniformly at random subject to the constraint that no triangle is formed. We determine the asymptotic number of edges in the maximal triangle-free graph at which the triangle-free process terminates. We also bound the independence number of this graph, which gives an improved lower bound on Ramsey numbers: we show R(3, t) > (1/4 - o(1))t2/log t, which is within a 4 + o(1) factor of the best known upper bound. Furthermore, we determine which bounded size subgraphs are likely to appear in the maximal triangle-free graph produced by the triangle-free process: they are precisely those triangle-free graphs with maximal average density at most 2.
13.11.2013
Frederik Garbe (FU Berlin)
On Graphs with Excess 2
Abstract: The Moore bound m(dk) = 1 + d Σi=1,...,k-1(d - 1)i is a lower bound for the number of vertices of a graph by given girth g = 2k + 1 and minimal degree d. Hoffmann and Singleton, Bannai and Ito, Damerell showed that graphs with d > 2 tight to this bound can only exist for girth 5 and degree 3, 7, 57. The difference to the Moore bound by given girth is called the excess of a graph. In the case of girth 5 Brown showed that there are no graphs with excess 1 and Bannai and Ito showed that for g ≥ 7 there are also no graphs with excess 1. We generalize the result of Kovács that, under special conditions for the degree d, there are no graphs with excess 2 and girth 5 and prove the new result that an excess-2-graph with odd degree and girth 9 cannot exist. In this proof we discover a link to certain elliptic curves. Furthermore we prove the non-existence of graphs with excess 2 for higher girth and special valences under certain congruence conditions.
20.11.2013
Piotr Micek (Jagiellonian University)
Nonrepetitve sequences, colorings and entropy compression method

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 L1, ..., Ln there exists a nonrepetitive sequence s1, ..., sn with si ∈ Li. 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.

Joint work with Jarosław Grytczuk and Jakub Kozik.
27.11.2013
Alexey Prokrovskiy (FU Berlin)
Nonnegative sums in a set of numbers
Abstract: Suppose that we have a set of numbers x1, ..., xn which have nonnegative sum. How many subsets of k numbers from {x1, ..., xn} must have nonnegative sum? Manickam, Miklos, and Singhi conjectured that for n at least 4k the answer is (n - 1 choose k - 1). This conjecture is known to hold when n is large compared to k. For example, Alon, Huang, and Sudakov proved the conjecture when n > 33k2. We will discuss an improvement to this bound by showing that there is a constant C such that the conjecture holds when n > Ck.
11.12.2013
Kathleen Johst (FU Berlin)
The k-color Ramsey number of a graph with m edges
Abstract: The k-color Ramsey number rk(H) of a graph H is the smallest integer N, such that in each k-coloring of the edges of the complete graph KN on N vertices there is a monochromatic copy of H. In my talk I show an upper bound rk(H) ≤ k2√(km)(1 + o(1)) for bipartite graphs H with m edges and no isolated vertices and k ≥ 2. Further, for a general graph H with m edges and no isolated vertices I discuss an upper bound rk(H) ≤ k3km2/3, for k ≥ 3.
17.12.2013
Bernhard Schmitt (Nanyang Technological University, Singapore)
Unique Sums and Differences in Finite Abelian Groups

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 (ab) ∈ 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 Fp, 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.

Let G be a finite abelian group and let p be the smallest prime divisor of the order of G. If A and B are subsets of G with ∜(12)|A|+|B|-2 < p, then A + B contains a unique sum.
18.12.2013
Christian Reiher (University of Hamburg)
Counting odd cycles in locally dense graphs
Abstract: Roughly speaking we prove that if a graph on n vertices has the property that each set of vertices whose size is linear in n spans at least as many edges as it spans in a random graph of density d, then the graph contains at least as many (odd) cycles of fixed length as the random graph does. With "at least" being replaced by "(almost) exactly" this is well known, but the present version seems to require a different approach. The result addresses a question of Y. Kohayakawa, B. Nagle, V. Rödl, and M. Schacht.
17.01.2014
Sylwia Antoniuk (Adam Mickiewicz University)
Random triangular groups
Abstract: (No abstract submitted.)
24.01.2014
Victor Falgas-Ravry (Umeå University)
On the connectivity of k-nearest-neighbours random geometric graphs

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.

In this talk I will present one such model, the k-nearest-neighbours random geometric graph model, and discuss its connectivity properties. I will present in particular a sharp threshold result, which is joint with Mark Walters (QMUL), as well as some more recent work of mine on subcritical components.
29.01.2014
Julia Ehrenmüller (TU Hamburg-Harburg)
On the intersection of longest paths
Abstract: A longest path in a graph has the property that there exists no other path in the graph that is strictly longer. In 1966 Gallai asked whether all longest paths in a connected graph have nonempty intersection. This is not true in general and various counterexamples have been found. However, the answer to Gallai's question is positive for several well-known classes of graphs, e.g. trees, outerplanar graphs, split graphs, and 2-trees. In this talk we discuss these results and present a proof that all series-parallel graphs have a vertex that is common to all of its longest paths. We also comment on how this vertex can be found in quadratic time. Joint work with Cristina G. Fernandes and Carl G. Heise.
29.01.2014
Miloš Stojaković (University of Novi Sad)
Threshold for Maker-Breaker H-game

Abstract: We will look at the Maker-Breaker H-game played on the edge set of the random graph Gn,p. In this game two players, Maker and Breaker, alternately claim unclaimed edges of Gn,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 Gn,p with respect to the graph H.

This is joint work with Rajko Nenadov and Angelika Steger.
26.02.2014
Codruţ Grosu (FU Berlin)
An algebraic approach to Turán densities

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 K43 (the complete 3-graph on 4 vertices).

I will start by reviewing what is known about Turán densities, and then I will explain how to apprach the problem in an algebraic manner. This will lead to several new (and somewhat surprising) results.
31.03.2014
Simeon Ball (Universitat Politècnica de Catalunya)
On the Turán number of complete bipartite graphs
Abstract: (No abstract submitted.)
09.04.2014
Tibor Szabó (FU Berlin)
What is Ramsey-equivalent to a clique?

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 Kk. In particular we prove that the only connected graph which is Ramsey-equivalent to Kk 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 Kk ⋅ K2 (the graph containing the clique with a pendant edge) can have.

This represents joint work with Jacob Fox, Andrey Grinshpun, Anita Liebenau, and Yury Person.
30.04.2014
Juanjo Rué (FU Berlin)
Applications of Tutte's tree decomposition in the enumeration of bipartite graph families

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.

This talk is based in a work in progress joint with Kerstin Weller.
05.05.2014
Deryk Osthus (University of Birmingham)
Proof of Two Conjectures of Thomassen on Tournaments

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

Our proofs introduce the concept of `robust dominating structures', which will hopefully have further applications. I will also discuss related open problems on cycle factors and linkedness in tournaments.
07.05.2014
Lothar Narins (FU Berlin)
Tau and the Connectedness of Line Graphs
Abstract: The topological connectedness of the independence complex is a useful and important tool that has lead to such things as the proof of Ryser's Conjecture for 3-partite 3-graphs. In this talk, I will present a lower-bound on the connectedness of the line graph of a hypergraph in terms of the hypergraph's vertex-cover number (tau). The bound is tight for general hypergraphs, but there are potentially improvements to be made in the case of r-partite r-graphs. I will sketch the proof of a conjectured lower-bound improvement for 3-partite 3-graphs for tau at most 12.
14.05.2014
Olaf Parczyk (FU Berlin)
On the logarithmic calculus and Sidorenko's conjecture

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:

We study a type of calculus for proving inequalities between subgraph densities which is based on Jensen's inequality for the logarithmic function. As a demonstration of the method we verify the conjecture of Erdős-Simonovits and Sidorenko for new families of graphs. In particular we give a short analytic proof for a result by Conlon, Fox and Sudakov. Using this, we prove the forcing conjecture for bipartite graphs in which one vertex is complete to the other side.
05.06.2014
Lander Ramos (Universitat Politècnica de Catalunya)
Random planar graphs with minimum degree two
Abstract: We illustrate how to use the symbolic method to determine asymptotic parameters of a combinatorial class. In particular, we compute the asymptotic exponential growth of the class of planar graphs with minimum degree at least two, as well as the expected number of edges of a random graph from this class.
11.06.2014
Tamás Mészáros (Central European University)
Shattering extremal set systems

Abstract: We say that a set system F ⊆ 2[n] shatters a given set S ⊆ [n] if 2S = {FS : FF}. 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.

The inclusion graph of a set system F ⊆ 2[n] is the labelled graph GF whose vertices are the elements of F, and there is an edge going from G to F with label j iff F = G ∪ {j}. GF is just the Hasse diagram of F labelled in a natural way. This graph theoretical point of view enables us to study the problem in a more familiar environment. We managed to characterize extremal set systems of VC-dimension at most 2 in terms of their inclusion graphs.
18.06.2014
Alexey Pokrovskiy (FU Berlin)
Linkage structures in tournaments

Abstract: A (directed) graph is k-linked if for two sets of vertices {x1, ..., xk} and {y1, ..., yk}, there are vertex disjoint paths {P1, ..., Pk}, such that Pi goes from xi to yi. 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.

The proof uses linkage structures in tournaments which were recently introduced by Kuhn, Lapinskas, Osthus, and Patel in order to prove a conjecture of Thomassen about edge disjoint Hamiltonian cycles in tournaments. As a consequence of our results we will also show that there is a constant C such that every Ck2 connected tournament contains k edge-disjoint Hamiltonian cycles, solving another conjecture of Kuhn, Lapinskas, Osthus, and Patel.
25.06.2014
Alexey Pokrovskiy (FU Berlin)
Linkage structures in tournaments (part II)
Abstract: Thomassen conjectured that there is a function f(k) such that every strongly f(k)-connected tournament contains k edge-disjoint Hamiltonian cycles. This conjecture was recently proved by Kuhn, Lapinskas, Osthus, and Patel who showed that f(k) < O(k2(log k)2) and conjectured that there was a constant C such that f(k) < Ck2. We'll discuss a proof of this conjecture, giving an overview of the Kuhn, Lapinskas, Osthus, and Patel proof and modifications which are needed to obtain the quadratic bound on f(k).
09.07.2014
Hiệp Hàn (Emory University)
Maximum number of colourings without monochromatic Schur triples

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 (abc) 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.

Joint work with Andrea Jimenez.
10.07.2014
Alice Händel (FU Berlin)
Partielle Transversale in Lateinischen Quadraten

Abstract: Ein lateinisches Quadrat der Ordnung n ist ein n x n Feld bestehend aus n2 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.

Im Rahmen dieses Seminarvortrages wird der Beweis von Shor und Hatami, dass jedes lateinische Quadrat der Ordnung n ein partielles Transversal der Länge mindestens n - 11,053 log2 n besitzt, bewiesen.