Algorithms, Structure, Randomness - Main page Algorithms, Structure, Randomness

Berlin-Poznan Seminar/Learn- & Workshop 2007

"Random Graphs and Extremal Graph Theory"

Featured speakers:

Andrzej Ruciński (Adam Mickiewicz Universität Poznan) und
Tomasz Łuczak (Adam Mickiewicz Universität Poznan)

Humboldt University Berlin, 6-7 July 2007

Schedule:

Friday, 6 July 2007
9:00 Andrzej Ruciński (AMU) Perfect matchings and Hamilton cycles in hypergraphs -- Dirac type thresholds
10:30 Coffee Break
11:00 Reto Spöhel (ETH Zürich) Online Ramsey Games in Random Graphs
11:30 Yury Person (TU München) Counting spanning trees in dense graphs
12:00 Nicla Bernasconi (ETH Zürich) Properties of Random Graphs via Boltzmann Samplers
12:30 Lunch Break
14:00 Tomasz Łuczak (AMU) Colorful flowers: a finite case
15:30 Coffee Break
16:00 Malwina Luczak (LSE) Percolation on the 2D Hamming graph: the supercritical phase
16:45 Jerzy Jaworski (AMU) A new random mapping model
19:00 Joint dinner

Saturday, 7 July 2007
9:00 Andrzej Ruciński (AMU) Perfect matchings and Hamilton cycles in hypergraphs -- Ramsey properties
10:30 Coffee Break
11:00 Konstantinos Panagiotou (ETH Zürich) Extremal Subgraphs of Random Graphs
11:30 Nikolaos Fountoulakis (University of Birmingham) The order of the largest complete minor in a random graph
12:00 Lunch Break
14:00 Tomasz Łuczak (AMU) Colorful flowers: an infinite case
15:30 Coffee Break
16:00 Jarosław Grytczuk (University of Zielona Góra) Coloring integer distance graphs
16:45 Yoshiharu Kohayakawa (Universidade de São Paulo) An algorithmic Friedman--Pippenger theorem on tree embeddings
17:30 Closing


All lectures will be held in 

 Erwin Schrödinger-Zentrum, HU Berlin
 Rudower Chaussee 26,
 12489 Berlin
in room 0.311

Abstracts

Andrzej Ruciński

Perfect matchings and Hamilton cycles in hypergraphs -- Dirac type thresholds
Perfect matchings and Hamilton cycles in hypergraphs -- Ramsey properties

    In my lectures I will present recent results about certain aspects of extremal hypergraph theory. One direction originates in the celebrated Dirac theorem for graphs: every $n$-vertex graph with minimum degree at least $n/2$ is hamiltonian. Using a hypergraph regularity lemma and a recent technique of absorption, I will sketch a proof of an approximate version of a generalization of Dirac theorem to $k$-uniform hypergraphs . A precise Dirac type threshold will be presented for perfect and almost perfect $k$-uniform matchings. (Both are joint result with Rödl and Szemerédi).
    In the second lecture I will outline a proof (based on earlier ideas of Luczak) that the Ramsey number of a tight 3-uniform cycle on $n$ vertices is asymptotically $\frac43n$ if $n$ is a multiple of 3, and $2n$ otherwise. As a main ingredient of this outline it will be shown that the smallest integer $N$ such that every 2-coloring of the complete 3-uniform hypergraph on $N$ vertices contains a matching of size $n$ in a monochromatic connected component is equal to the ordinary Ramsey number for such a matching, that is, $N=4n-1$.

Tomasz Łuczak

Colorful flowers

    A map $f:[A]^k \to C$ is a local coloring of $k$-element subset of $A$, if disjoint sets are colored with different colors. By a colorful flower with an eye $S\in [A]^{k-1}$ we mean a family $F\subset [A]^k$ of $k$-element subsets of $A$ containing $S$ such that each subset of $F$ is colored with a different color. Moreover, by $\phi(k,\alpha)$ we denote the smallest $\gamma$ such that there exists a local coloring of a set of cardinality $\alpha$ without colorful flowers of cardinality $\gamma$. In the talks we study the behavior of $\phi(k,\alpha)$ (and its generalizations) first in the case when $\alpha$ is finite, and then for infinite cardinals $\alpha$.
    The lectures will be based on a joint work with Christian Avart, Petér Komjáth, and Vojta Rödl.

Malwina Luczak

Percolation on the 2D Hamming graph: the supercritical phase

    We study random subgraphs of the 2-dimensional Hamming graph $H(2,n)$, which is the Cartesian product of two complete graphs on $n$ vertices. Suppose that every edge is independently present with probability $p$, where $p=\frac{1+\epsilon}{2(n-1)}$ for some $\epsilon \in \mathbb R$.
    In a sequence of three papers, Borgs, Chayes, van der Hofstad, Slade and Spencer studied phase transitions in a large class of random graphs including $H(2,n)$. They obtained precise estimates for the maximum size of a connected component in the subcritical and critical regimes, as well as upper bounds in the supercritical phase. No general lower bounds on the largest supercritical component exist; indeed, it is thought that the geometry of a given graph will play a crucial role in upper bounding its giant component.
    Here, we complement the results of Borgs et al. for the supercritical phase in the Hamming graph $H(2,n)$. We prove that, when $\epsilon \gg (\log{n})^{1/3} n^{-2/3}$, then the largest connected component has size close to $2\epsilon n^2$ with high probability. We thus obtain a law of large numbers for the largest connected component size, and show that the corresponding values of $p$ really are supercritical. Except for the factor $(\log{n})^{1/3}$, this identifies the size of the largest connected component all the way down to the critical $p$ window.
    This is joint work with Remco van der Hofstad.

Reto Spöhel

Online Ramsey Games in Random Graphs

    Consider the following one-player game: The vertices of a random graph are revealed to the player one by one, along with all edges induced by the vertices revealed so far. The player has to assign one of $r$ available colors to each vertex immediately, without creating a monochromatic copy of some fixed graph $F$. For which values of $p$ can the player asymptotically almost surely (a.a.s.) color the entire random graph $G_{n,p}$? We say that $p_0(n)$ is a threshold for this game if there is a strategy such that the player a.a.s. succeeds if $p\ll p_0$, but a.a.s. fails with any strategy if $p\gg p_0$.
    We prove explicit thresholds $p_0(F,r,n)$ for a large family of graphs $F$ including cliques and cycles of arbitrary size, and an arbitrary number $r$ of colors. In particular, we show that the order of magnitude of the threshold depends on the number of colors, in contrast to the offline case.
    If time permits, I will also talk about the edge-coloring analogon of this game, which was introduced by Friedgut et al. We show a threshold result similar to the one for the vertex-coloring case, but only covering the game with two colors.
    Joint work with Martin Marciniszyn and Angelika Steger.

Bernasconi Nicla

Properties of Random Graphs via Boltzmann Samplers

    The framework of Boltzmann samplers of Duchon et al. is an efficient method for sampling objects uniformly at random from graph classes with structural constraints, such as planar graphs. We analyze the execution of Boltzmann sampler algorithms of different classes to derive results about the structure of a random object of these classes. In particular, we determine the degree sequence of random outerplanar graphs, and derive tight bounds for the tails probabilities.
    Joint work with Konstantinos Panagiotou and Angelika Steger.

Jerzy Jaworski

A new random mapping model

    We introduce a new random mapping model, $T_n^{\hat D}$, which maps the set $\{1,2,...,n\}$ into itself. The random mapping $T_n^{\hat D}$ is constructed using a collection of exchangeable random variables $\hat{D}_1, ....,\hat{D}_n$ which satisfy $\sum_{i=1}^n\hat{D}_i=n$. In the random digraph, $G_n^{\hat D}$, which represents the mapping $T_n^{\hat D}$, the in-degree sequence for the vertices is given by the variables $\hat{D}_1, \hat{D}_2, ..., \hat{D}_n$, and, in some sense, $G_n^{\hat D}$ can be viewed as an analogue of the general independent degree models from random graph theory. We show that the distribution of the number of cyclic points, the number of components, and the size of a typical component can be expressed in terms of expectations of various functions of $\hat{D}_1, \hat{D}_2, ..., \hat{D}_n$. We also consider two special examples of $T_n^{\hat D}$ which correspond to random mappings with preferential and anti-preferential attachment, respectively, and determine, for these examples, exact and asymptotic distributions for the statistics mentioned above. Some results for the distribution of the number of successors and predecessors of a typical vertex in $G_n^{\hat D}$ in terms of expectations of various functions of $\hat{D}_1, \hat{D}_2, ..., \hat{D}_n$ are also given.

Jarosław Grytczuk

Coloring integer distance graphs

    Let $D=\{d_{1} < d_{2} < \ldots \}$ be a set of positive integers and let $G_{D}=(V,E)$ be a graph defined on the set of vertices $V=\mathbb{N}$ such that $uv\in E$ iff $\left\vert u-v\right\vert \in D$. Let $\chi (D)$ be the chromatic number of a graph $G_{D}$. For which infinite sets $D$ is $\chi (D) $ finite? The answer is closely connected to Diophantine approximation properties of $D$. Indeed, it is not hard to see that if for some positive integer $k$ and a real $x$ we have $\left\Vert xd_{i}\right\Vert \geq 1/k$ for every $i\geq 1$, then $G_{D}$ is $k$-colorable (here $\left\Vert \cdot \right\Vert $ denotes distance to the nearest integer). Using this approach, known as the \emph{regular coloring} method, Katznelson \cite{Katznelson}\ and independently Ruzsa, Tuza and Voigt \cite{RTV}, answered a question of Erd\H{o}s proving that $\chi (D)$ is finite for every \emph{lacunary} set $D$ . One tempts to conjecture that if $\chi (D)$ is finite, then there always exists a finite regular coloring of $G_{D}$.
    We consider also improper colorings of integer distance graphs connected to Ramsey theory. We show that for every lacunary set $D$ there is a regular $3$ -coloring of $G_{D}$ such that paths whose vertices form arithmetic progressions have bounded length. This supports a conjecture of Brown, Graham, and Landman \cite{BGL}. In case of finite $D$ we obtain several partial results supporting the Lonely Runner Conjecture, which says that $G_{D}$ has a regular coloring using at most $\left\vert D\right\vert +1$ colors.
    Joint work with Sebastian Czerwiński, Tomasz Schoen, and Wiesław Śliwa.

Nikolaos Fountoulakis

The order of the largest complete minor in a random graph

    A graph is contained as a minor in another graph if we obtain a copy of the former by repeated contractions of edges of the latter and discarding any multiple edges that are created. We are interested in the largest k such that a complete graph of order k is contained in a given graph G (this is called the contraction clique number - ccl(G)). This question is motivated by Hadwiger's conjecture. Bollobas, Catlin and Erdos proved that almost all graphs satisfy Hadwiger's conjecture, by estimating ccl(G(n,1/2)) (they also did it for any fixed p<1). Answering a question set by Krivelevich and Sudakov, we estimate ccl(G(n,p)) for sparse random graphs, that is p=o(1). We will also discuss several related problems.
    This is joint work with Daniela Kuehn and Deryk Osthus.

Yury Person

Counting spanning trees in dense graphs

    The regularity-blow-up-lemma approach is not only useful for providing existence results, but also when one wants to count(approximately). The latter results are often a byproduct of the former(embedding results). Precisely, we want to show for a given graph $T$ not only that it lies in some dense graph $G$, but also to determine the number of embeddings of $T$ into $G$ (lower bounds). In 2003 Sarkozy, Selkow and Szemeredi did this for hamiltonian cycles : they found $c^n n!$ such copies, where $c>0$ is a small constant. I present a generalisation of the version of the blow-up lemma, which was proved by Rödl, Rucinski and Taraz in 1999. Then, using the recently proved Bollobas-Komlos conjecture, I derive similar counting results for bipartite graphs of bounded degree and small bandwidth, and especially for trees.

Konstantinos Panagiotou

Extremal Subgraphs of Random Graphs

    Let $K_l$ denote the complete graph on $l$ vertices. We prove that there is a constant $c = c(l) > 0$, such that whenever $p \ge n^{-c}$, with probability tending to 1 when $n$ goes to infinity, every maximum $K_l$-free subgraph of the binomial random graph $G_{n,p}$ is $(l-1)$-partite.
    The proof is based on a tool of independent interest: we show, for instance, that the maximum cut of almost all graphs with $M$ edges, where $M\gg n$, is nearly unique. More precisely, given a maximum cut $C$ of $G_{n,M}$, we can obtain all maximum cuts by moving at most $O(\sqrt{n3/M})$ vertices between the parts of $C$.

Yoshiharu Kohayakawa

An algorithmic Friedman--Pippenger theorem on tree embeddings

    An \textit{$(n,d)$-expander} is a graph~$G=(V,E)$ such that for every~$X\subset V$ with~$|X|\leq2n-2$ we have~$|\Gamma_G(X)|\geq(d+1)|X|$. A tree~$T$ is \textit{small} if it has at most~$n$ vertices and has maximum degree at most~$d$. Friedman and Pippenger~(1987) proved that any~$(n,d)$-expander contains every small tree. However, their elegant proof does not seem to yield an efficient algorithm for obtaining the tree. In this talk, we shall give an alternative result that does admit a polynomial time algorithm for finding the immersion of any small tree in subgraphs~$G$ of $(N,D,\lambda)$-graphs~$\Lambda$, as long as~$G$ contains a positive fraction of the edges of~$\Lambda$ and~$\lambda/D$ is small enough. In several applications of the Friedman--Pippenger theorem, including the ones in the original paper of those authors, the $(n,d)$-expander~$G$ is a subgraph of an $(N,D,\lambda)$-graph as above. Therefore, our result suffices to provide efficient algorithms for such previously non-constructive applications. Our approach is based on a reduction of the tree embedding problem to a certain online matching problem for bipartite graphs, solved by Aggarwal et al.~(1996).
    This is joint work with D. Dellamonica Jr (São Paulo)

Contact:

Dr. Mihyun Kang 
Postal address
Johann von Neumann-Haus
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin


Tel.   : (+49 30) 2093 3830
Fax    : (+49 30) 2093 3191
e-mail : kang@informatik.hu-berlin.de
last modified 07/11/07 (alkox-www)