DIMACS Center, CoRE Building, Rutgers University

**Organizers:****Noga Alon**, Tel Aviv University, noga@math.tau.ac.il**Joel Spencer**, NYU, spencer@cs.nyu.edu

**B\'ela Bollob\'as, Memphis and Cambridge***Colourings Generated by Monotone Properties*

In the talk we shall present some recent results obtained jointly with Oliver Riordan. Among other results, answering the main question of Erd\H{o}s, de la Vina and Fajtlowicz, we prove that if ${\cal P}$ is the property of containing no $C_4$, then neither the red nor the blue graph obtained need contain a large complete subgraph.

**Amir Dembo***Information inequalities and concentration of measure*

**Zoltan F\"uredi, Department of Mathematics, University of Illinois***The expected size of a random sphere-of-influence graph*

**Donovan Hare, Math. & Stats., Okanagan University College, Canada***Arithmetic Progressions in Sequences With Bounded Gaps*

In this talk we give an exponential lower bound for $G(k,2)$ and (with the help of the Lov\'{a}sz Local Lemma) an improved lower bound for $G(k,r)$, $r>2$. We show that $G(k,2) > \sqrt{\frac{k-1}{2}} \left(\frac{4}{3}\right)^{\frac{k-1}{2}}$, $G(k,3) > \frac{2^{k-2}}{ek}(1+o(1))$, and $G(k,2r-1) > \frac{r^{k-2}}{ek}(1+o(1))$, $r\ge 2$.

This is joint work with Tom Brown, Math. \& Stats., Simon Fraser University, Canada.

**Nabil Kahale***A semidefinite bound for mixing rates of Markov chains*

**Jeong Han Kim, AT&T Labs - Research***Random Coverings of the $n$-Dimensional Cube*

Let $Q_n$ be the $n$-dimensional cube $\{1, -1\}^n $. The ($n$-dimensional) half space $H_{x}$ generated by $x \in R^n$ is the set of all $n$-dimensional real vectors $w$ having negative inner product with $x$; that is, $$H_{x} := \{ w \in R^n: w\cdot x < 0 \}. $$ How many random vectors in $Q_n$ (with every vector in $A$ equally likely to be chosen) are needed to cover $Q_n$ using the half spaces generated by the random vectors?

It is easy to see that (1+o(1))n random vectors are sufficient. Is (1-o(1))n random vectors necessary? The answer is ``NO''. It may be shown that 0.9963n are sufficient and 0.005n are necessary.

We will also see how this problem is related to neural networks. (Joint work with J. Roche.)

**Alexander Kostochka***Oriented colorings of graphs*

**Tomasz Luczak***Extremal properties of random sets*

**Colin McDiarmid***Finding a minimum spanning tree in a network with random weights*

We find that when the $k$th edge $e_k$ is added to the current tree, where $k = o(\sqrt{d})$, the probability that this edge $e_k$ is incident to the node that was most recently added to the tree equals $\frac12 + \frac1{2k} + o(1)$ as $d \rightarrow \infty$. We also find for example that, if the edge weights are uniformly distributed on $(0,1)$, then the expected value of $w(e_k)$ is asymptotic to $(\frac12 + \frac1{2k})/d$.

**Mike Molloy***A Bound on the Total Chromatic Number*

**Sotiris Nikoletseas***Stochastic Graphs Have Short Memory: Fully Dynamic Connectivity in Poly-Log Expected Time*

**Igor Pak***Random walks on groups: strong stationary times approach*

**Robin Pemantle, University of Wisconsin-Madison***Exponentially separated paths and application to oriented percolation*

A (directed) graph admits EXPONENTIALLY SEPARATED PATHS if there is a probability measure on the infinite paths of the graph such that the number of meetings of two independent paths has exponential tails. A graph with ESP must have $p_c < 1$ for oriented percolation and simple random walk on the oriented percolation cluster must be transient with positive probabilty. We show that $Z^3$ has ESP, extending to the oriented case a result of Grimmett and Zhang concerning transience of simple random walk on unoriented percolation clusters.

**Ljubomir Perkovic***Edge Coloring in polynomial time (on average)*

If a simple graph $G=(V,E)$ of maximum degree $\Delta > |V|/3$ has no overfull subgraph of degree $\Delta$ then $G$ is $\Delta$ edge colorable.

We show that the conjecture is true for large enough graphs given some technical conditions. The proof uses a probabilistic argument. We use it to construct a polynomial time randomized procedure that optimally colors the edges of graphs satisfying the conditions of the theorem.

We then present a deterministic algorithm that optimally colors the edges of any simple graph. Assuming a uniform distribution of the input graphs the expected running time of the algorithm is polynomial. A deterministic version of the procedure above is used as one of the steps in the algorithm. All this is joint work with Bruce Reed.

**Jonathan Aronson, Alan Frieze (Carnegie Mellon University) and Boris Pittel (Ohio State University)***Maximum matchings in sparse random graphs: Karp--Sipser re-visited*

**Bruce Reed***$\omega,\Delta,\chi$*

**Vojtech R\"odl & Andrzej Rucinski***Partition properties of Random Structures*

**Joel Spencer***An asymptotic isoperimetric inequality*

**Paul Spirakis***Genetic probabilistic methods for almost uniform generation in parallel*

**Aravind Srinivasan***Improving the discrepancy bound for sparse matrices: better approximations for sparse integer programs*

We also present a simple connection between discrepancy and communication complexity.

**Michel Talagrand***Concentration of measure and combinatorics: what is the final word?*

Previous: Participation

Next: Registration

Workshop Index

DIMACS Homepage

Contacting the Center

Document last modified on October 8, 1996.