The ACO Seminar (2008-2009)

We provide a complete description of the giant component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ as soon as it emerges from the scaling window, i.e., for $p = (1+\epsilon)/n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$.

Our description is particularly simple for $\epsilon = o(n^{-1/4})$, where the giant component $C_1$ is contiguous with the following model (i.e., every graph property that holds with high probability for this model also holds w.h.p. for $C_1$). Let $Z$ be normal with mean $(2/3) \epsilon^3 n$ and variance $\epsilon^3 n$, and let $K$ be a random $3$-regular (multi)graph on $2\lfloor Z\rfloor$ vertices. Replace each edge of $K$ by a path, where the path lengths are i.i.d. geometric with mean $1/\epsilon$. Finally, attach an independent Poisson($1-\epsilon$)-Galton-Watson tree to each vertex. A similar picture is obtained for larger $\epsilon=o(1)$, in which case the random 3-regular graph is replaced by a random (multi)graph with $N_k$ vertices of degree $k$ for $k\geq 3$, where $N_k$ has mean and variance of order $\epsilon^k n$.

This description enables us to determine fundamental characteristics of the supercritical random graph. Namely, we can infer the asymptotics of the diameter of the giant component for any rate of decay of $\epsilon$, as well as the mixing time of the random walk on $C_1$.

Joint work with Jian Ding and Yuval Peres.

We study the space requirements for Cuckoo Hashing. This can be reduced to the following question in Random Graphs.

We are given two disjoint sets L,R with |L|=n=alpha*m and |R|=m. We construct a random graph G by allowing each x in L to choose d random neighbours in R. The problem is to find m(G), the size of the largest matching in G.

From the point of view of Cuckoo Hashing, a key question is to locate the threshold for when m(G)=n with high probability, since if m(G) < n it is impossible to store all items. We answer this question exactly for d greater than 5.

Contingency tables are the method of choice of government agencies for releasing statistical summaries of categorical data. In this paper, we consider lower bounds on how much distortion (noise) is necessary in these tables to provide privacy guarantees when the data being summarized is sensitive. We extend a line of recent work on lower bounds on noise for private data analysis (DInur & Nissim, PODS 03; Dwork, McSherry & Talwar, STOC 07; Dwork and Yekhanin, Crypto 08) to a natural and important class of functionalities. Our investigation also leads to new results on the spectra of random matrices with correlated rows.

Joint work with Shiva Kasiviswanathan (Los Alamos) and Mark Rudelson (Michigan).

A weighting of the edges of a graph with integer weights gives rise to a weighting of the vertices, the weight of a vertex being the sum of the weights of its incident edges. Such a weighting induces a vertex coloring, i.e., by assigning the same color to vertices with the same weight. It is natural to consider edge weighting where we require that adjacent vertices have different weights --- that is, the vertex weighting induce a proper coloring of the graph.

Conjecture (Karonski, Luczak and Thomason, 2001): The edges of every graph that does not contain a component isomorphic to $K_2$ can be weighted with the integers {1,2,3} such that the resultant vertex weighting is a proper coloring.

In my talk I will discuss some recent developments regarding the above conjecture. and a related {1,2}-conjecture. In particular, I will present a joint result, with Maciej Kalkowski and Florian Pfender, showing that {1,2, ... , 5}-edge-weighting suffices to properly color vertices of a graph.

We study the vertex pursuit game of Cops and Robbers where cops try to capture a robber on the vertices of the graph. The minimum number of cops required to win on a given graph G is the cop number of G. We present asymptotic results for the game of Cops and Robber played on a random graph G(n,p) for a wide range of p=p(n). It has been shown that the cop number as a function of an average degree forms an intriguing zigzag shape.

A d-simplex is a collection of d+1 sets such that every d of them have non-empty intersection and the intersection of all of them is empty. A strong d-simplex is a collection of $+2 sets A,A_1, ... ,A_{d+1} such that {A_1, ... ,A_{d+1}} is a d-simplex, while A contains an element of each d-wise intersection.

For n large and k \geq d+2, we prove that a k-uniform hypergraph F that contains no strong d-simplex has size at most {n-1 \choose k-1} with equality only when F is a star.

Joint work with Tao Jiang and Oleg Pikhurko.

We say that the graphs G and H with n vertices pack if G and H can be embedded to the same vertex set with no overlapping edges. Bollobas, Eldridge and independently Catlin conjectured that if that if (M(G)+1)(M(H)+1) < n+2 holds for the maximal degress then G and H pack. Aigner and Brandt and independently Alon and Fischer proved this in the case M(G),M(H)<3. Csaba, Shokoufandeh and Szemeredi proved it if M(G),M(H)<4. Bollobas, Kostochka and Nakprasit settled the case when one of the graphs is degenerate. Kaul, Kostochka and Yu showed that if M(G)M(H)<3/5n and the maximal degrees are large enough then G and H pack. We prove the conjecture for graphs with at least 10^8 vertices.

Since the seminal work of Erd"os and R'enyi the phase transition of the largest components in random graphs became one of the central topics in random graph theory and discrete probability theory. In this talk we discuss the similarity and difference of critical behaviour of the largest components in the Erd"os and R'enyi random graph and in a uniform random planar graph.