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.

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 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 r̂(G) < c(d)·n, with n the number of vertices of G.

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 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 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² → 0

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.

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.

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 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!

1. admits both of the upper bound proofs,
2. gives rise to a superlinear lower bound.

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.

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.

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.

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₁ ≤ ... ≤ 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.

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.

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₀(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₁ and F₂ are forbidden in the two colors), and verified this conjecture for the case where both graphs are cycles.

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

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.

Abstract: A graph is called H-free if it contains no copy of H. Denote by f_n(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 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 H-free graphs.

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!

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.

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.

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.

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.