


Random Graphs and Their Applications
Org: Anthony Bonato (Wilfrid Laurier), Penny Haxell (Waterloo) and Nicholas Wormald (Waterloo) [PDF]
 TOM BOHMAN, Carnegie Mellon University, Department of Mathematical
Sciences
AntiRamsey Thresholds
[PDF] 
We call an edgecoloring of a graph a kcoloring if it uses no more
than k colors and kbounded 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 kcoloring of the edges of K_{m}
contains a homogeneous K_{n}. Rodl et al. proved the
following antiRamsey theorem: for every k and every n there
exists an m such that any kbounded 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
kbounded 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ösHajnal Sets and Semigroup Decompositions
[PDF] 
Define a set of lines in R^{3} to be "stacked" with respect to v Î R^{3} 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 wellknown ErdösHajnal conjecture via
the MilnorThom 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ösHajnal sets" and an
intriguing problem concerning the decomposability of semialgebraic
sets: Do all semialgebraic 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 920930112
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 NPhard 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 3out
[PDF] 
We consider the existence of Hamilton cycles in the random graph
3out. 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 spinsystems
[PDF] 
Let L = {l_{i} : 1 £ i £ m} È{l_{ij} :1 £ i £ j £ m} be a system of nonnegative 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
spinmodels such as Potts, Ising and hardcore.)
With Prasad Tetali, we considered the normalizing constant (or
partition function) of the abovedescribed 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
nonnegative 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^{3}) simple permutations on {0,1}^{n}. Specifically
we ask how many randomly selected simple permutations need be composed
to yield a permutation that is close to kwise independent. We
improve on previous results and show that up to a polylogarithmic
factor, n^{2} k^{2} compositions of random permutations from this family
suffice. In addition, our results give an explicit construction of a
degree O(n^{3}) Cayley graph of the alternating group of 2^{n} objects
with a spectral gap W(1/(n^{2} 2^{n})), 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 selforganizing
networks
[PDF] 
Selforganizing 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
3SAT problem
[PDF] 
We analyze the satisfiability problem of a certain random 3SAT
problem in which the appearances of 3clauses 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 3SAT problem in which the
appearances of 3clauses are not independent. In this paper, a phase
transition phenomenon is found for the random 3SAT problem. In the
course of the analysis, we also introduce a generalized random 2SAT
formula and show its phase transition phenomenon.
Joint work with SungSoon 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 kSAT, random
kcolourability and many other wellstudied 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 1o(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 socalled (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 realworld 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 2factors 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, k1+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 ballsintoboxes model. We place k1
balls into k bins, ball j going into bin i with probability
p(1p)^{i1}/(1p^{k}), a truncated exponential where we think of p
as the tilt. With Z_{t} balls in bin t the "queue walk" has
Y_{0}=1, Y_{t} = Y_{t1}+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 nearlyspanning 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 (1e)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
(1e)n vertices with maximum degree at most d.
We also prove that if an (n,D,l)graph G (i.e., a
Dregular 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 kregular 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 3regular 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 kregular subgraph. We also discuss the appearance of
3regular subgraphs in cores of random graphs.

