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 co-prime 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
On-line Ramsey Numbers II
12.05.2010
11:00
Roman Glebov
FU Berlin
On-line 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
Balog-Szemerédi-Gowers 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 H-decompositions 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 Urbana-Champaign
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 Clique-Paths
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 3-SAT
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 edge-coloring 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 out-degree k, the main question is, whether you can color the edges such a way, that:
  1. all k edges leaving any vertex have distinct colors and
  2. there is a suitable sequence w of colors, such that no matter which vertex we choose as start-point we get the same end-point, reading the word w label to label and choosing the suitable edge (according to w), on which we can travel to the next vertex.
It was first conjectured in 1970 by Weiss and Adler, that one can always find an appropriate coloring with a suitable word, if the digraph is strongly connected and aperiodic, that is, there is no integer k > 1 that divides the length of every cycle of the graph. In 2007 Trahtman proved the conjecture (now it is called Road coloring theorem). In my talk I will present a partial result proved by Kari (2002), which says that the theorem is true if the graph is eulerian and regular, that is, all vertices have in and outdegree k.
25.06.2010
Anusch Taraz (TU Munich)
On co-prime labellings of trees
Abstract: A conjecture by Entringer from around 1980 states that the vertices of every n-vertex tree can be labelled with numbers 1 up to n in such a way that adjacent vertices get co-prime 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 (G) of a graph G is the smallest number of integers such that there exists a graph F with edges for which every red-blue-edge-coloring 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 (G) < c(dn, 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 (G) of a graph G is the smallest integer such that there is a graph F of edges with the property that any two-coloring 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 (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:

(Pn)/n → ∞

(Pn)/n2 → 0

In 1983 Beck proved that for every sufficiently large value of n (Pn) < 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)
On-line Ramsey Numbers II

Abstract: In Ramsey theory, we mostly look at the number r(t) denoting the minimum number of vertices sich that a two-coloring of the edges of the clique on r(t) many vertices necessarily produces a monochromatic t-subclique (we also say an r(t)-clique "arrows" a t-clique). 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 on-line version of this problem according to a resent paper by David Conlon. In a two-players-game, Builder draws edges one-by-one, and Painter colors them as each appears. Builder's aim is to force Painter to draw a monochromatic t-clique.

In my second talk on the on-line Ramsey numbers, I present a specific upper bound for r''(t) of order 4t - c(log2(t))/(loglog(t)).
12.05.2010
Roman Glebov (FU Berlin)
On-line Ramsey Numbers I

Abstract: In Ramsey theory, we mostly look at the number r(t) denoting the minimum number of vertices sich that a two-coloring of the edges of the clique on r(t) many vertices necessarily produces a monochromatic t-subclique (we also say an r(t)-clique "arrows" a t-clique). 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 on-line version of this problem according to a resent paper by David Conlon. In a two-players-game, Builder draws edges one-by-one, and Painter colors them as each appears. Builder's aim is to force Painter to draw a monochromatic t-clique. The minimum number of edges which Builder must draw is the on-line 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 two-coloring of the edges of the complete graph Kn on n vertices yields a monochromatic copy of G. For example it is known that r(Kk) is at least 2k/2 and at most 22k 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) < 2C√(m) (this would be then best possible up to a constant factor in view of the above mentioned bounds for r(Kk)). 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ős-Simonovits 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 d-dimensional polytope with n facets is at most n - d. The best general upper bound due to Kalai and Kleitman is n1 + 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
  1. admits both of the upper bound proofs,
  2. gives rise to a superlinear lower bound.
The lower bound is proved using the Lovász Local Lemma. In the talk we present this paper.
18.03.2010
Anita Liebenau (Cambridge University)
Balog-Szemerédi-Gowers Theorem

Abstract: The Balog-Szemerédi-Gowers 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 k-nonrepetitive (k ≥ 2) if it contains no k-repetition, i.e. a block B of the form B = CC...C (k-times) 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 2-nonrepetitive 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 conflict-free (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 conflict-free 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 2-coloring of the edges of KN (the complete graph on N vertices) yields a monochromatic k-clique. For 60 years it is known that 2(k/2) < R(k) < 4k, 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 KN. Maker's goal is to completely occupy a Kk 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 Kk in the game on KN. 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 d1 ≤ ... ≤ dn. If n ≥ 3 and dii + 1 or dn - in - 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.

Nash-Williams 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 edge-disjoint 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 edge-disjoint 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 Gn,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 p0(Fn) for the existence of such a coloring. Kohayakawa and Kreuter (1997) conjectured a general threshold function for the asymmetric case (where different graphs F1 and F2 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 so-called KŁR-Conjecture is true for the sparser of the two graphs. We present a new upper bound proof that does not depend on the KŁR-Conjecture. Together with earlier lower bound results [Marciniszyn, Skokan, S., Steger (2006)], this yields in particular a full proof of the Kohayakawa-Kreuter conjecture for the case where both graphs are cliques.
08.01.2010
Yury Person (HU Berlin)
Minimum H-decompositions of graphs

Abstract: Let φH(G) be the minimum number of graphs needed to partition the edge set of G into edges (K2) and edge-disjoint copies of H. The problem is what graph G on n vertices maximizes φH(G)?

Bollobás showed that for H = Kr, 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 tr - 1(n) + o(n2), where tr - 1(n) is the number of edges in (r - 1)-partite Turán graph on n vertices. They also conjectured that φH(G) = ex(nH). 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 Urbana-Champaign)
Counting graphs without a fixed complete bipartite subgraph

Abstract: A graph is called H-free if it contains no copy of H. Denote by fn(H) the number of (labeled) H-free graphs on n vertices. Since every subgraph of an H-free graph is also H-free, it immediately follows that fn(H) ≥ 2ex(nH). Erdős conjectured that, provided H contains a cycle, this trivial lower bound is in fact tight, i.e. fn(H) = 2(1 + o(1))ex(nH).

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 H-free 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 Ramsey-type 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 H-subgraphs, 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‘ H-subgraphs.

This is joint work with Reto Spöhel and Lutz Warnke.
20.11.2009
Roman Glebov (FU Berlin)
Extremal Graphs for Clique-Paths
Abstract: In this talk, we deal with a Turán-type 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 clique-path, that is an k-path, where each edge is blown up to an r-clique, 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 k-coloring 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 k-coloring.

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 NP-complete, 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 3-SAT

Abstract: In an attempt to derandomize Schoening's famous algorithm for k-SAT, Dantsin et al. proposed a deterministic k-SAT 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 search-trees can sometimes be Copy-Pasted 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 H-Ramsey if any two-coloring of the edges of G contains a monochromatic copy of H. An H-Ramsey graph is called H-minimal if no proper subgraph of it is H-Ramsey.

We investigate the minimum degree of H-minimal graphs, a problem initiated by Burr, Erdős, and Lovász.

We determine the smallest possible minimum degree of H-minimal graphs for numerous bipartite graphs H, including bi-regular bipartite graphs and forests.

We also make initial progress for graphs of larger chromatic number.