The ACO Seminar (2009-2010)

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.

We present fastest known algorithms for various network flow problems. In particular, we consider the well-known maximum flow and minimum-cost flow problems, as well as the generalized versions of these problems. In the generalized versions, a multiplicative factor is associated with each edge, defining the relationship between the amount flowing in and the amount flowing out of the edge. Our algorithm deals with "lossy" generalized flow networks, where the multiplicative factors are at most 1. We obtain an additive epsilon approximation for the lossy generalized max flow and min-cost flow problems in time O(m^(3/2)log^2(U/epsilon)) (excluding log(m) factors) for graphs with m edges, and with integer capacities and costs in the range {1...U} and loss multipliers that are ratios of integers in the same range. Furthermore, for the standard max-flow and min-cost flow problems we obtain exact algorithms that run in time O(m^(3/2)log^2(U)) (excluding log(m) factors). For the standard min-cost flow problem, and for the lossy generalized max flow and min-cost flow problems, our algorithms are faster than the previously best known by a factor of roughly O(m^(1/2)).

The above algorithms work by accelerating traditional interior point algorithms by quickly solving the linear equations that arise in each step. The running times rely on our analysis of the performance of interior-point algorithms when each step is computed using an approximate solver. In particular, for network flow problems, to obtain the results described above it suffices to approximately compute each interior-point step in nearly linear time.

In standard flow problems, the system of linear equations arising at each interior-point step is described by a symmetric positive-semidefinite diagonally-dominant matrix. Such systems can be solved in nearly linear time using an algorithm of Spielman and Teng.

In the generalized flow problems, the linear systems from the interior-point steps are described by symmetric M-matrices. We present an algorithm for solving linear systems in symmetric M-matrices in nearly-linear time. Our algorithm reduces the problem of solving a linear system in a symmetric M-matrix to that of solving a logarithmic number of linear systems in symmetric diagonally-dominant matrices.

By speeding up interior-point algorithms using the Spielman-Teng algorithm (in the standard flow case) and our M-matrix algorithm (in the generalized flow case) we obtain the flow algorithms stated above.

The theory of positional games is a branch of combinatorics, whose main aim is to develop systematically an extensive mathematical basis for a variety of two player perfect information games, ranging from such commonly popular games as Tic-Tac-Toe and Hex to purely abstract games played on graphs and hypergraphs.

In this talk I will survey basic notions and concepts of positional games and some recent developments in the field, putting an emphasis on interconnections between positional games and other branches of mathematics and computer science, in particular probabilistic considerations.