Combinatorics Seminar 2009/2010
Archive of old talks. The current schedule can be found here.
Date  Speaker  Title 

09.07.2010 11:00 
Gábor Mészáros HU Berlin 
Road Coloring Problem 
25.06.2010 11:00 
Anusch Taraz TU Munich 
On coprime labellings of trees 
16.06.2010 11:00 
Wilma Weps FU Berlin 
On Size Ramsey Number of Graphs with Bounded Maximum Degree 
11.06.2010 11:00 
Balázs Szegedy University of Toronto 
Limits of discrete structures (recent directions) 
02.06.2010 11:00 
Gábor Mészáros HU Berlin 
Path Size Ramsey Numbers 
19.05.2010 11:00 
Roman Glebov FU Berlin 
Online Ramsey Numbers II 
12.05.2010 11:00 
Roman Glebov FU Berlin 
Online Ramsey Numbers I 
05.05.2010 11:00 
Yury Person HU Berlin 
A conjecture of Erdős on graph Ramsey numbers 
28.04.2010 11:00 
Oleg Pikhurko Carnegie Mellon University 
An analytic approach to stability 
21.04.2010 11:15 
Tibor Szabó FU Berlin 
A combinatorial model for the diameter of a polyhedra 
18.03.2010 12.00 
Anita Liebenau Cambridge University 
BalogSzemerédiGowers Theorem 
12.03.2010 12:00 
Wilma Weps FU Berlin 
Nonrepetitive colorings of graphs 
03.03.2010 12:00 
Gábor Tardos Simon Fraser University, Rényi Institute 
Conflict free coloring of neighborhoods in graphs 
23.02.2010 11:15 
Heidi Gebauer ETH Zürich 
Game Theoretic Ramsey Numbers 
22.01.2010 10:00 
Andrew Treglown University of Birmingham 
Hamilton cycles in directed graphs 
13.01.2010 12:00 
Reto Spöhel ETH Zürich 
Upper bounds for asymmetric Ramsey properties of random graphs 
08.01.2010 12:00 
Yury Person HU Berlin 
Minimum Hdecompositions of graphs 
07.01.2010 10:15 
Anna Huber MPII Saarbrücken 
Performance and Robustness of Randomized Rumor Spreading Protocols 
06.01.2010 12:00 
Wojciech Samotij University of Illinois at UrbanaChampaign 
Counting graphs without a fixed complete bipartite subgraph 
11.12.2009 14:15 
Michael Krivelevich Tel Aviv University 
Intelligence vs Randomness: the power of choices 
26.11.2009 10:15 
Angelika Steger ETH Zürich 
A deletion method for local subgraph counts 
20.11.2009 12:00 
Roman Glebov FU Berlin 
Extremal Graphs for CliquePaths 
09.11.2009 10:15 
Philipp Zumstein ETH Zürich 
Polychromatic Colorings of Plane Graphs 
26.10.2009 10:15 
Dominik Scheder ETH Zürich 
Deterministic Local Search for 3SAT 
23.10.2009 12:00 
Tomislav Doslic University of Zagreb 
Computing the bipartite edge frustration of some classes of graphs 
16.10.2009 12:00 
Tibor Szabó FU Berlin 
Minimum degree of minimal ramsey graphs 
Abstracts:
09.07.2010 

Gábor Mészáros (HU Berlin) 
Road Coloring Problem 
Abstract: The road coloring problem deals with the question whether there exists an edgecoloring of a network such that by using special instructions, one can reach or locate an object or destination from any other point within the network. Precisely, if you have a directed graph G with regular outdegree k, the main question is, whether you can color the edges such a way, that:

25.06.2010 

Anusch Taraz (TU Munich) 
On coprime labellings of trees 
Abstract: A conjecture by Entringer from around 1980 states that the vertices of every nvertex tree can be labelled with numbers 1 up to n in such a way that adjacent vertices get coprime labels. In joint work with P.E. Haxell and O. Pikhurko we recently managed to prove this conjecture for sufficiently large n. I will discuss the proof in this talk. 
16.06.2010 

Wilma Weps (FU Berlin) 
On Size Ramsey Number of Graphs with Bounded Maximum Degree 
Abstract: The size Ramsey number r̂(G) of a graph G is the smallest number of integers r̂ such that there exists a graph F with r̂ edges for which every redblueedgecoloring contains a monochromatic copy of G. Josef Beck raised the question whether for a graph G with bounded maximum degree d there exists a constant c(d) depending only on the maximum degree such that r̂(G) < c(d)·n, with n the number of vertices of G. It has shown to be true that such a constant exists if G is a cycle or a tree. In my talk I will present a counterexample by Rödl and Szemerédi which shows that the statement above already fails if d = 3. 
11.06.2010 

Balázs Szegedy (University of Toronto) 
Limits of discrete structures (recent directions) 
Abstract: This talk is a status report on a recently developing subject in the frame of which big finite structures are viewed as approximations of infinite analytic structures. This framework enables one to use differential calculus, measure theory, topology and other infinite tools to analyze finite structures. 
02.06.2010 

Gábor Mészáros (HU Berlin) 
Path Size Ramsey Numbers 
Abstract: The size Ramsey number r̂(G) of a graph G is the smallest integer r̂ such that there is a graph F of r̂ edges with the property that any twocoloring of the edges of G yields a monochromatic copy of G. An obvious upper bound is known for the size Ramsey number of an arbitrary graph G, namely r̂(G) ≤ (r(G) choose 2) where r(G) denotes the Ramsey number of G. For paths Erdős offered 100$ for a proof or disproof of the following conjectures: r̂(P_{n})/n → ∞ r̂(P_{n})/n^{2} → 0 In 1983 Beck proved that for every sufficiently large value of n r̂(P_{n}) < 900·n, which result answered Erdős's question. In my talk I will present Beck's proof and discuss some related results in the area, including some interesting counterexamples which tell us that Beck's result is not necessarily true for general trees. 
19.05.2010 

Roman Glebov (FU Berlin) 
Online Ramsey Numbers II 
Abstract: In Ramsey theory, we mostly look at the number r(t) denoting the minimum number of vertices sich that a twocoloring of the edges of the clique on r(t) many vertices necessarily produces a monochromatic tsubclique (we also say an r(t)clique "arrows" a tclique). The size Ramsey number r'(t) is the smallest number of edges such that there exists a graph with r'(t) edges arrowing an r(t)clique. In my two talks I present the online version of this problem according to a resent paper by David Conlon. In a twoplayersgame, Builder draws edges onebyone, and Painter colors them as each appears. Builder's aim is to force Painter to draw a monochromatic tclique. In my second talk on the online Ramsey numbers, I present a specific upper bound for r''(t) of order 4^{t  c(log2(t))/(loglog(t))}. 
12.05.2010 

Roman Glebov (FU Berlin) 
Online Ramsey Numbers I 
Abstract: In Ramsey theory, we mostly look at the number r(t) denoting the minimum number of vertices sich that a twocoloring of the edges of the clique on r(t) many vertices necessarily produces a monochromatic tsubclique (we also say an r(t)clique "arrows" a tclique). The size Ramsey number r'(t) is the smallest number of edges such that there exists a graph with r'(t) edges arrowing an r(t)clique. In my two talks I present the online version of this problem according to a resent paper by David Conlon. In a twoplayersgame, Builder draws edges onebyone, and Painter colors them as each appears. Builder's aim is to force Painter to draw a monochromatic tclique. The minimum number of edges which Builder must draw is the online Ramsey number r''(t). The main result presented in the first talk is the fact that for in finitely many values of t, r''(t) is exponentially smaller than r'(t). 
05.05.2010 

Yury Person (HU Berlin) 
A conjecture of Erdős on graph Ramsey numbers 
Abstract: For a given graph G, let r(G) be the minimum number n such that any twocoloring of the edges of the complete graph K_{n} on n vertices yields a monochromatic copy of G. For example it is known that r(K_{k}) is at least 2^{k/2} and at most 2^{2k} and despite efforts of many researchers the constant factors in the exponents remain the same for more than 60 years! For a graph G with m edges and no isolated vertices Erdős conjectured that r(G) < 2^{C√(m)} (this would be then best possible up to a constant factor in view of the above mentioned bounds for r(K_{k})). Very recently, Benny Sudakov proved this conjecture. In my talk I will present Sudakov's proof and discuss some related results and propblems in the area. 
28.04.2010 

Oleg Pikhurko (Carnegie Mellon University) 
An analytic approach to stability 
Abstract: This is an attempt to understand how the recently developed theory of graph limits may apply to finite problem of extremal graph theory. We formulate the notion of a stable problem (meaning, roughly speaking, that almost extremal graphs have structure close to that of an extremal graph) and give an equivalent characterization in terms of graph limits. As an application, we present a new proof of the ErdősSimonovits stability theorem. 
21.04.2010 

Tibor Szabó (FU Berlin) 
A combinatorial model for the diameter of a polyhedra 
Abstract: The Hirsch Conjecture states that the diameter of a ddimensional polytope with n facets is at most n  d. The best general upper bound due to Kalai and Kleitman is n^{1 + log d}. For constant dimension Larman showed that the diameter is linear in n. Recently, Eisenbrand, Hähnle, Razborov, and Rothvoß introduced a combinatorial model for the problem which

18.03.2010 

Anita Liebenau (Cambridge University) 
BalogSzemerédiGowers Theorem 
Abstract: The BalogSzemerédiGowers theorem is a result in the field of additive combinatorics and gives a relationship between the sizes of sum sets and partial sum sets. Surprisingly, the proof is purely graph theoretical and relies on a statement about paths of length 3 in a bipartite graph. It is the object of this talk to develop this relationship as well as giving sketches of the proofs of the corresponding statements in graph theory. I will assume only basic definitions of graph theory and no previous knowledge about additive combinatorics. 
12.03.2010 

Wilma Weps (FU Berlin) 
Nonrepetitive colorings of graphs 
Abstract: Nonrepetitive coloring of graphs is a graph theoretic variant of the nonrepetitive sequences of Thue. A (in)finite sequence is called knonrepetitive (k ≥ 2) if it contains no krepetition, i.e. a block B of the form B = CC...C (ktimes) with C being a nonempty block. A vertex coloring f of a graph G is called nonrepetitive if each path P in G has a 2nonrepetitive sequence f(P) of colors. Defining the Thue number of a graph to be the smallest number of colors needed for such a coloring, one is interested in estimating this graph invariant. I will present a theorem by Alon et al. proving the Thue number is bounded by the maximum degree of a graph; furthermore, a theorem by Kündgen and Pelsmajer showing the Thue number is bounded by the treewidth of a graph from above. However, for most classes of graphs the exact value of the Thue number remains unknown. 
03.03.2010 

Gábor Tardos (Simon Fraser University, Rényi Institute) 
Conflict free coloring of neighborhoods in graphs 
Abstract: A (not necessarily proper) vertex coloring of a graph is called conflictfree (with respect to the neighborhoods) if the neighborhood N(x) of any vertex x contains a vertex whose color is not repeated in N(x). We consider how many colors are needed in the worst case for conflictfree coloring of an n vertex graph. Surprisingly the answer depends very strongly on whether one considers the neighborhood N(x) to contain or exclude x itself. The results are joint with János Pach. 
23.02.2010 

Heidi Gebauer (ETH Zürich) 
Game Theoretic Ramsey Numbers 
Abstract: The Ramsey Number, R(k), is defined as the minimum N such that every 2coloring of the edges of K_{N} (the complete graph on N vertices) yields a monochromatic kclique. For 60 years it is known that 2^{(k/2)} < R(k) < 4^{k}, and it is a widely studied open problem to find significantly better bounds. In this talk we consider a game theoretic variant of the Ramsey number: Two players, called Maker and Breaker, alternately claim an edge of K_{N}. Maker's goal is to completely occupy a K_{k} and Breaker's goal is to prevent this. The game theoretic Ramsey Number R'(k) is defined as the minimum N such that Maker has a strategy to build a K_{k} in the game on K_{N}. In contrast to ordinary Ramsey numbers, R'(k) has been determined precisely  a result of Beck. We will sketch a new, weaker result about R'(k) and use it to solve some related open problems. 
22.01.2010 

Andrew Treglown (University of Birmingham) 
Hamilton cycles in directed graphs 
Abstract: Since it is unlikely that there is a characterization of all those graphs which contain a Hamilton cycle it is natural to ask for sufficient conditions which ensure Hamiltonicity. One of the most general of these is Chvátal's theorem that characterizes all those degree sequences which ensure the existence of a Hamilton cycle in a graph: Suppose that the degrees of a graph G are d_{1} ≤ ... ≤ d_{n}. If n ≥ 3 and d_{i} ≥ i + 1 or d_{n  i} ≥ n  i for all i < n/2 then G is Hamiltonian. This condition on the degree sequence is best possible in the sense that for any degree sequence violating this condition there is a corresponding graph with no Hamilton cycle. NashWilliams conjectured a digraph analogue of Chvátal's theorem quite soon after the latter was proved. In the first part of the talk I will discuss an approximate version of this conjecture. A Hamilton decomposition of a graph or digraph G is a set of edgedisjoint Hamilton cycles which together cover all the edges of G. A conjecture of Kelly from 1968 states that every regular tournament has a Hamilton decomposition. We recently proved the following approximate version of Kelly's conjecture: Every regular tournament on n vertices contains (1/2  o(1))n edgedisjoint Hamilton cycles. I will discuss some of our techniques as well as some related open problems in the area. This is joint work with Daniela Kühn and Deryk Osthus. 
13.01.2010 

Reto Spöhel (ETH Zürich) 
Upper bounds for asymmetric Ramsey properties of random graphs 
Abstract: Consider the following problem: Is there a coloring of the edges of the random graph G_{n,p} with two colors such that there is no monochromatic copy of some fixed graph F? A celebrated result by Rödl and Rucinski (1995) states a general threshold function p_{0}(F, n) for the existence of such a coloring. Kohayakawa and Kreuter (1997) conjectured a general threshold function for the asymmetric case (where different graphs F_{1} and F_{2} are forbidden in the two colors), and verified this conjecture for the case where both graphs are cycles. Implicit in their work is the following more general statement: The conjectured threshold function is an upper bound on the actual threshold provided that i) the two graphs satisfy some balancedness condition, and ii) the socalled KŁRConjecture is true for the sparser of the two graphs. We present a new upper bound proof that does not depend on the KŁRConjecture. Together with earlier lower bound results [Marciniszyn, Skokan, S., Steger (2006)], this yields in particular a full proof of the KohayakawaKreuter conjecture for the case where both graphs are cliques. 
08.01.2010 

Yury Person (HU Berlin) 
Minimum Hdecompositions of graphs 
Abstract: Let φ_{H}(G) be the minimum number of graphs needed to partition the edge set of G into edges (K_{2}) and edgedisjoint copies of H. The problem is what graph G on n vertices maximizes φ_{H}(G)? Bollobás showed that for H = K_{r}, r ≥ 3 the only maximizer is the Turán graph. Pikhurko and Sousa extended his result for general H with χ(H) = r ≥ 3 and proved an upper bound being t_{r  1}(n) + o(n^{2}), where t_{r  1}(n) is the number of edges in (r  1)partite Turán graph on n vertices. They also conjectured that φ_{H}(G) = ex(n, H). In the talk, we verify their conjecture for odd cycles, and show that the only graph maximizing φ_{C2l + 1}(G) is the Turán graph, for large n. Joint work with Lale Özkahya. 
07.01.2010 

Anna Huber (MPII Saarbrücken) 
Performance and Robustness of Randomized Rumor Spreading Protocols 
Abstract: Randomized rumor spreading is a classical protocol to disseminate information in a network. Initially, one vertex of a finite, undirected and connected graph has some piece of information ("rumor"). In each round, every one of the informed vertices chooses one of its neighbors uniformly and independently at random and informs it. At SODA 2008, a quasirandom version of this protocol was proposed. There, each vertex has a cyclic list of its neighbors. Once a vertex has been informed, it chooses uniformly at random only one neighbor. In the following round, it informs this neighbor and in each subsequent round it informs the next neighbor from its list. I will talk about recent results on the performance and robustness of these two protocols, in particular about the runtime on random graphs and about the robustness on the complete graph. 
06.01.2010 

Wojciech Samotij (University of Illinois at UrbanaChampaign) 
Counting graphs without a fixed complete bipartite subgraph 
Abstract: A graph is called Hfree if it contains no copy of H. Denote by f_{n}(H) the number of (labeled) Hfree graphs on n vertices. Since every subgraph of an Hfree graph is also Hfree, it immediately follows that f_{n}(H) ≥ 2^{ex(n, H)}. Erdős conjectured that, provided H contains a cycle, this trivial lower bound is in fact tight, i.e. f_{n}(H) = 2^{(1 + o(1))ex(n, H)}. The conjecture was resolved in the affirmative for graphs with chromatic number at least 3 by Erdős, Frankl and Rödl (1986), but the case when H is bipartite remains wide open. We will give an overview of the known results in case χ(H) = 2 and present our recent contributions to the study of Hfree graphs. This is joint work with Jozsef Balogh (University of California, San Diego). 
11.12.2009 

Michael Krivelevich (Tel Aviv University) 
Intelligence vs Randomness: the power of choices 
Abstract: Consider the following very standard experiment: n balls are thrown independently at random each into n bins (if you are practically inclined, think about distributing n jobs at random between n machines). It is quite easy to see that the maximum load over all bins will be almost surely about ln n/lnln n. If however each ball is allowed to choose between two randomly drawn bins, the typical maximum bin load drops dramatically to about lnln n, as shown in a seminal paper of Azar, Broder, Karlin and Upfal from 1994  an exponential improvement! The above described result is just one manifestation of a recently widely studied phenomenon, where a limited manipulation of the otherwise truly random input is capable to advance significantly various goals. In this talk I will describe results of this type, mainly focusing on the so called controlled random graph processes, where at each stage an algorithm is presented with a collection of randomly drawn edges and is allowed to manipulate this collection in a certain predefined way. Models to be defined and discussed include the Achlioptas process and Ramseytype games on random graphs. 
26.11.2009 

Angelika Steger (ETH Zürich) 
A deletion method for local subgraph counts 
Abstract: For a given graph H let X denote the random variable that counts the number of copies of H in a random graph. For subgraph counts one can use Janson’s inequality to obtain upper bounds on the probability that X is smaller than its expectation. For the corresponding upper tail, however, such bounds are not obtained easily and are known to not hold with similarly small probabilities. In this talk we thus consider the following variation of the problem: we want to find a subgraph that on the one hand still contains at roughly E[X] many Hsubgraphs, and on the other hand has the property that every vertex (and more generally every small subset of vertices) is contained in ‘not too many‘ Hsubgraphs. This is joint work with Reto Spöhel and Lutz Warnke. 
20.11.2009 

Roman Glebov (FU Berlin) 
Extremal Graphs for CliquePaths 
Abstract: In this talk, we deal with a Turántype problem: given a positive integer n and a forbidden graph H, how many edges can there be in a graph on n vertices without a subgraph H? And how does a graph look like, if it has this extremal edge number? The forbidden graph in this talk is a cliquepath, that is an kpath, where each edge is blown up to an rclique, r ≥ 3. We determine both the extremal number and the extremal graph for sufficiently large n. 
09.11.2009 

Philipp Zumstein (ETH Zürich) 
Polychromatic Colorings of Plane Graphs 
Abstract: A vertex kcoloring of a plane graph G is called polychromatic if in every face of G all k colors appear. Let p(G) be the maximum number k for which there is a polychromatic kcoloring. For a plane graph G, let g(G) denote the length of the shortest face in G. We show p(G) ≥ (3g(G)  5)/4 for every plane graph G and on the other hand for each g we construct a plane graph H with g(H) = g and p(H) ≤ (3g + 1)/4. Furthermore, we show that the problem of determining whether a plane graph admits a vertex coloring by 3 colors in which all colors appear in every face is NPcomplete, even for graphs in which all faces are of length 3 or 4 only. The investigation of this problem is motivated by its connection to a variant of the art gallery problem in computational geometry. Joint work with Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Peter Csorba, Saswata Shannigrahi, and Bettina Speckmann. 
26.10.2009 

Dominik Scheder (ETH Zürich) 
Deterministic Local Search for 3SAT 
Abstract: In an attempt to derandomize Schoening's famous algorithm for kSAT, Dantsin et al. proposed a deterministic kSAT algorithm based on covering codes and deterministic local search. The deterministic local search procedure was subsequently improved by several authors. I will present the main ideas behind the algorithm and the latest improvements, one of them by myself. At the heart of my improvement is the idea that recursive searchtrees can sometimes be CopyPasted to save time. 
23.10.2009 

Tomislav Doslic (University of Zagreb) 
Computing the bipartite edge frustration of some classes of graphs 
Abstract: The bipartite edge frustration of a graph is defined as the smallest number of edges that have to be deleted from the graph in order to obtain a bipartite spanning subgraph. The quantity is, in general, difficult to compute; however it can be efficiently computed for certain classes of graphs. I will speak about computing the bipartite edge frustration of some planar graphs, in particular fullerenes, and of some composite graphs. 
16.10.2009 

Tibor Szabó (FU Berlin) 
Minimum degree of minimal ramsey graphs 
Abstract: A graph G is called HRamsey if any twocoloring of the edges of G contains a monochromatic copy of H. An HRamsey graph is called Hminimal if no proper subgraph of it is HRamsey. We investigate the minimum degree of Hminimal graphs, a problem initiated by Burr, Erdős, and Lovász. We determine the smallest possible minimum degree of Hminimal graphs for numerous bipartite graphs H, including biregular bipartite graphs and forests. We also make initial progress for graphs of larger chromatic number. 