---

Les graphes aléatoires et leurs applications
Org: Anthony Bonato (Wilfrid Laurier), Penny Haxell (Waterloo) et Nicholas Wormald (Waterloo)
[PDF]

---

TOM BOHMAN, Carnegie Mellon University, Department of Mathematical Sciences
Anti-Ramsey Thresholds [PDF]

We call an edge-coloring of a graph a k-coloring if it uses no more than k colors and k-bounded if it uses no color more than k times. We call a subgraph homogeneous if all of its edges are colored the same and heterogeneous if all of its edges are colored differently.

A classical Ramsey theorem states that for every k and n there exists an m such that any k-coloring of the edges of K_m contains a homogeneous K_n. Rodl et al. proved the following anti-Ramsey theorem: for every k and every n there exists an m such that any k-bounded coloring of the edges of K_m contains a heterogeneous K_n.

Let H be a fixed connected graph that contains a cycle. In this talk we establish the threshold for the property that every k-bounded coloring of the random graph G_n,p has a heterogenous copy of H. We also discuss the behavior of the probability that G_n,p has this property for p close to the threshold and pose a conjecture for the threshold when H is a tree.

This is joint work with Alan Frieze, Oleg Pikhurko and Cliff Smyth.

JOSH COOPER, Courant Institute, NYU
Erdös-Hajnal Sets and Semigroup Decompositions [PDF]

Define a set of lines in R³ to be "stacked" with respect to v Î R³ if, from a vantage point far away in the direction of v, the lines are linearly ordered by the "crossing over" relation. Given a collection of skew lines and a point v, we ask, what is the largest stacked subset that must be present among the lines? This question, which appears in a a 2000 paper of Erdös, Hajnal, and Pach, is intimately related to the well-known Erdös-Hajnal conjecture via the Milnor-Thom theorem. It was recently resolved by a powerful and very general theorem of Alon, Pach, Pinchasi, Radoicic, and Sharir.

We describe these results and discuss several related issues, including a generalization to "Erdös-Hajnal sets" and an intriguing problem concerning the decomposability of semi-algebraic sets: Do all semi-algebraic sets belong to the set algebra generated by semigroups in R^d? Our main result is a resolution of this question in dimensions 1 and 2.

KEVIN COSTELLO, UCSD, 9500 Gilman Drive, La Jolla, CA  92093-0112
On random matrices [PDF]

We are going to discuss a few basic problems concerning random discrete matrices. By "discrete" we would like to stress the case when the entries have discrete support (an important subcase is when they take values 0 and 1).

ABRAHAM FLAXMAN, Carnegie Mellon University, Pittsburgh, PA, USA
On the Average Case Performance of Some Greedy Approximation Algorithms for the Uncapacitated Facility Location Problem [PDF]

In combinatorial optimization, a popular approach to NP-hard problems is the design of approximation algorithms. These algorithms typically run in polynomial time and are guaranteed to produce a solution which is within a known multiplicative factor of optimal. Unfortunately, the known factor is often known to be large in pathological instances. Conventional wisdom holds that, in practice, approximation algorithms will produce solutions closer to optimal than their proven guarantees.

We analyze the performance of three related approximation algorithms for the uncapacitated facility location problem (from [Jain, Mahdian, Markakis, Saberi, Vazirani, 2003] and [Mahdian, Ye, Zhang, 2002]) when each is applied to an instances created by placing n points uniformly at random in the unit square. We find that, with high probability, these three algorithms do not find asymptotically optimal solutions, and, also with high probability, a simple plane partitioning heuristic does find an asymptotically optimal solution.

ALAN FRIEZE, Carnegie Mellon University
Hamilton cycles in 3-out [PDF]

We consider the existence of Hamilton cycles in the random graph 3-out. In this model, each of the n vertices independently chooses 3 incident edges. We show that with high probability this graph has a Hamilton cycle. The proof relies in part on the analysis of a simple greedy algorithm. We use the differential equation method to model this. Numerical computations with double precision, etc., verify what we need for the outcome of this process. We are currently working on a rigorous global error analysis.

Joint work with Tom Bohman.

DAVID GALVIN, IAS, Einstein Drive, Princeton, NJ 08540, USA
Bounding the partition function of spin-systems [PDF]

Let L = {l_i : 1 £ i £ m} È{l_ij :1 £ i £ j £ m} be a system of non-negative reals. For any graph G, L induces a natural probability distribution on {f : V(G) ® [m]} in which each such f is given weight Õ_{v Î V(G)} l_f(v) Õ_{u,v Î E(G)}l_f(u)f(v) and is chosen with probability proportional to its weight. (This framework encompasses many familiar statistical physics spin-models such as Potts, Ising and hard-core.)

With Prasad Tetali, we considered the normalizing constant (or partition function) of the above-described distribution, in the case when all l_ij Î {0,1}, and we obtained an upper bound that is tight for the class of regular bipartite graphs. Here we use random graphs to extend this work to the case of general non-negative l_ij.

SHLOMO HOORY, University of British Columbia
Simple permutations mix well [PDF]

A naturally occurring question in cryptography is how well the composition of simple permutations drawn from a simple distribution resembles a random permutation. Although such constructions are a common source of security for block ciphers like DES and AES, their mathematical justification (or lack thereof) is troubling.

Motivated by this question, we study the random composition of a small family of O(n³) simple permutations on {0,1}ⁿ. Specifically we ask how many randomly selected simple permutations need be composed to yield a permutation that is close to k-wise independent. We improve on previous results and show that up to a polylogarithmic factor, n² k² compositions of random permutations from this family suffice. In addition, our results give an explicit construction of a degree O(n³) Cayley graph of the alternating group of 2ⁿ objects with a spectral gap W(1/(n² 2ⁿ)), which is a substantial improvement over previous constructions.

This question is essentially about the rapid mixing of a certain Markov chain, and the proofs are based on the comparison technique.

JEANNETTE JANSSEN, Dalhousie University, Halifax, Nova Scotia
Infinite limits of random graph models for self-organizing networks [PDF]

Self-organizing networks are real or virtual networks that are formed by the actions of a mulitude of independent agents, who act with only local knowledge of the network. A famous example is the virtual network formed by the pages and hyperlinks of the World Wide Web; other examples include social networks, the Internet, and biological networks such as that modelling the interaction between proteins. It has been observed in various studies that such networks share a number of common graph properties. Moreover, these properties do not fit the traditional G(n,p) model. In order to explain the occurrence of these characteristics, a number of new random graph models have been proposed. These are mostly based on a stochastic time process, where nodes and edges are added (and removed) at each time step.

A new approach to study these graphs is to study these models by considering the infinite graphs that result when time goes to infinity. In this talk, I will describe this method, and the results obtained from it. Particularly, I will describe a new model that incorporates the idea, coined in the literature, that new nodes "copy" the neighbourhood of an existing node, with some error. Depending on the parameters, the infinite limits of this model will exhibit some form of the property that defines R, the infinite random graph. I will also discuss some new classes of infinite graphs that arise naturally in this context.

This is joint work with Anthony Bonato.

JEONG HAN KIM, Microsoft Research
Phase Transitions in a random NK landscape Model and a random 3-SAT problem [PDF]

We analyze the satisfiability problem of a certain random 3-SAT problem in which the appearances of 3-clauses are not independent. The random model is reduced directly from the solubility problem of a random NK landscape model with K=3. Proposed by Kauffman, the NK model is one of the most notable mathematical models to study the evolution on a fitness landscape, where a fitness landscape is a function that maps each genetic composition (genotype) to the fitness of the expression (phenotype) of the genetic composition in an environment.

Gao and Culberson introduced a random NK model and pointed out that the solubility problem of the random NK model is equivalent to the satisfiability problem of a certain random 3-SAT problem in which the appearances of 3-clauses are not independent. In this paper, a phase transition phenomenon is found for the random 3-SAT problem. In the course of the analysis, we also introduce a generalized random 2-SAT formula and show its phase transition phenomenon.

Joint work with Sung-Soon Choi and Kyomin Jung.

MICHAEL MOLLOY, University of Toronto
Sharp Thresholds in Random Constraint Satisfaction Problems [PDF]

We consider a wide family of models for random constraint satisfaction problems. This family includes random k-SAT, random k-colourability and many other well-studied generalizations. Our goal is to determine precisely which members of this family have sharp thresholds of satisfiability, in the sense (formalized by Friedgut) that the probability of satisfiability drops suddenly from 1-o(1) to o(1). In doing so, we want to understand what sorts of features can cause models to have coarse thresholds rather than sharp ones.

In this talk, I'll report some progress towards this goal. This includes the following:

(1) A theorem that for any simple connected graph H (on at least 2 vertices), the property "is homomorphic to H" has a sharp threshold iff H has a triangle.
(2) A characterization of which models from a natural subfamily (the so-called (d,k,t)-models) have sharp thresholds.
(3) Some interesting examples of models which have coarse thresholds.

This is joint work with Hamed Hatami.

PAWEL PRALAT, University of Waterloo, 200 University Ave. W., Waterloo, ON N2L 3G1
Protean graphs [PDF]

The web may be viewed as a directed graph each of whose vertices corresponds to a static HTML web page, and each of whose arcs corresponds to a hyperlink from one web page to another. Recently there has been considerable interest in using random graphs to model complex real-world networks to gain an insight into their properties.

We propose a new random model of web graph in which the degrees of a vertex depends on its age. We characterize the degree sequence of this model and study its behaviour near the connectivity threshold.

Joint work with Tomasz Luczak.

ROBERT ROBINSON, University of Georgia, Athens, GA
Finding Hamilton Cycles in Random Cubic Graphs [PDF]

We consider the problem of finding a Hamilton cycle in a graph G drawn at random from the set of labeled cubic graphs of order 2n. In 1996 Frieze et al. showed that with high probability the expected number of independent random 2-factors of G needed to yield a Hamilton cycle is O(n^5/2).

A more careful analysis reveals that over a class containing almost all cubic graphs (as n ® ¥) this expectation is asymptotic to Cn^1/2 for a constant C = 0.56802636.... This suggests an algorithm which intuitively should find a Hamilton cycle in time O(n^3/2) with high probability. Supporting evidence for such performance is provided by data from experiments carried out by Mei Xue while an M.S. student at The University of Georgia.

JOEL SPENCER, Courant Institute, New York
Counting Connected Graphs using Erdös Magic [PDF]

Let C(k,l) be the number of labelled connected graphs with k vertices, k-1+l edges. We employ random graphs and breadth first search techniques to find the asymptotics of C(k,l) whenever k,l both tend to infinity. We further analyze the joint distribution of the number of vertices and edges of the "giant component" of Erdös and Renyi. We further consider randomized algorithms that (for "most" k,l) efficiently generate uniformly distributed connected graphs with these parameters.

At heart we have a tilted balls-into-boxes model. We place k-1 balls into k bins, ball j going into bin i with probability p(1-p)^i-1/(1-p^k), a truncated exponential where we think of p as the tilt. With Z_t balls in bin t the "queue walk" has Y₀=1, Y_t = Y_t-1+Z_t-1 and hence Y_k=0. We analyze (for appropriate p) the probability that the walk has Y_t > 0 for all 0 £ t < k.

BENJAMIN SUDAKOV, Department of Mathematics, Princeton University, Princeton, NJ  08544, USA
Embedding nearly-spanning bounded degree trees [PDF]

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-e)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ³ 2 and 0 < e < 1, there exists a constant c=c(d,e) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-e)n vertices with maximum degree at most d.

We also prove that if an (n,D,l)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most l in their absolute values) has large enough spectral gap D/l as a function of d and e, then G has a copy of every tree T as above.

Joint work with Noga Alon and Michael Krivelevich.

JACQUES VERSTRAETE, University of Waterloo, 200 University Avenue West, Waterloo, Ontario N2L 1J9
Regular Subgraphs of Random Graphs [PDF]

In this talk, we prove that there exists a function r_k = (4 +o(1)) k such that G(n,r/n) contains a k-regular graph with high probability whenever r > r_k. In the case of k=3, it is also shown that G(n,r/n) contains a 3-regular graph with high probability whenever r > l » 5.1494. These are the first constant bounds on the average degree in G(n,p) for the existence of a k-regular subgraph. We also discuss the appearance of 3-regular subgraphs in cores of random graphs.