Combinatorics Seminar 2013/2014
Talks take place at Arnimallee 3, 14195 Berlin, Room 210 at 16:15, unless stated otherwise.
Date | Speaker | Title |
---|---|---|
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(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. 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))t^{2}/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(d, k) = 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 L_{1}, ..., L_{n} there exists a nonrepetitive sequence s_{1}, ..., 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. 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 x_{1}, ..., x_{n} which have nonnegative sum. How many subsets of k numbers from {x_{1}, ..., x_{n}} 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 > 33k^{2}. 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 r_{k}(H) of a graph H is the smallest integer N, such that in each k-coloring of the edges of the complete graph K_{N} on N vertices there is a monochromatic copy of H. In my talk I show an upper bound r_{k}(H) ≤ k^{2√(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 r_{k}(H) ≤ k^{3km2/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 (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. 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 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. 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 K_{4}^{3} (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 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_{2} (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 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. The inclusion graph of a set system F ⊆ 2^{[n]} is the labelled graph G_{F} whose vertices are the elements of F, and there is an edge going from G to F with label j iff F = G ∪ {j}. G_{F} 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 {x_{1}, ..., x_{k}} and {y_{1}, ..., y_{k}}, there are vertex disjoint paths {P_{1}, ..., 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. 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 Ck^{2} 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(k^{2}(log k)^{2}) and conjectured that there was a constant C such that f(k) < Ck^{2}. 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 (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. 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 n^{2} 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 log^{2} n besitzt, bewiesen. |