DIMACS Workshop on Probabilistic Methods in Discrete Mathematics

October 14-18, 1996
DIMACS Center, CoRE Building, Rutgers University

Organizers:
Noga Alon, Tel Aviv University, noga@math.tau.ac.il
Joel Spencer, NYU, spencer@cs.nyu.edu
Presented under the auspices of the DIMACS Special Focus on Discrete Probability.

Abstracts

Given a monotone decreasing property ${\cal P}$ of graphs of order $n$, and a graph $G\in {\cal P}$, colour an edge $e$ of the complement of $G$ {\bf blue} if $G+e$ belongs to ${\cal P}$, and {\bf red} otherwise. Erd\H os, de la Vina and Fajtlowicz proved that, for a number of properties ${\cal P}$, either the red or the blue graph contains a large complete subgraph.

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.

We derive inequalities of the form $d(P,Q) \leq H(P|R)+H(Q|R)$ which hold for every choice of probability measures P,Q,R, where $H(P|R)$ denotes the relative entropy of P with respect to R and d(P,Q) stands for a coupling type ``distance'' between P and Q. Using the chain rule for relative entropies and then specializing to Q of a given support we recover some of Talagrand's concentration of measure inequalities for product spaces.

Let $N=(X,||.||)$ be a $d$-dimensional normed vector space, $d\geq 2$, and let $V$ be a finite subset of $X$. For each point $v\in V$ let $r(v)$ be the closest distance to any other point in the set, i.e., $B(v, r(v))$ is the largest empty ball centered at $v$. The {\it sphere of influence graph} of $V$, written as $SIG(V)$, is the intersection graph of these balls, i.e., its vertex set is V where x and y from V are adjacent if and only if their open balls have a nonempty intersection, $r(x)+r(y) >|| x-y ||$. We determine the expected number of edges of a sphere-of-influence graph with vertices selected independently with even distribution from an open bounded region. Other proximity graphs are also investigated.

Let $G(k,r)$ denote the smallest positive integer $g$ such that if \\ $1=a_1, a_2, \dots, a_g$ is a strictly increasing sequence of integers with bounded gaps $a_{j+1}-a_j \le r$, $1\le j\le g-1$, then $\{a_1, a_2, \ldots, a_g\}$ contains a $k$-term arithmetic progression.

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.

We study the method of bounding the spectral gap of a reversible Markov chain by establishing canonical paths between the states. We provide natural examples where improved bounds can be obtained by allowing variable length functions on the edges. We give a simple heuristic for computing good length functions. Further generalization using multicommodity flow yields a bound which is an invariant of the Markov chain, and which can be computed at an arbitrary precision in polynomial time via semidefinite programming. We show that, for any reversible Markov chain on n states, this bound is off by at most a factor of order log$^2$ n, and that this can be tight.

This talk will consider the following combinatorial problem which comes from neural networks.

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.)

For an oriented graph $D$, an oriented coloring $f$ is a proper coloring with additional restriction that for each two distinct arcs $xy$ and $uv$, if $f(y)=f(u)$, then $f(x)\neq f(v)$. Naturally, the oriented chromatic number of $D$ is the minimum number of colors sufficient for an oriented coloring of $D$. For an unoriented graph $G$, define oriented chromatic number $o(G)$ to be the maximum of oriented chromatic numbers over all orientations of $G$. The aim of the talk is to survey known results on connections of oriented chromatic number with other graph characteristics. Some bounds were proved using the probabilistic approach, and probably this approach can help in further studying of the topic.

We investigate Prim's standard `tree-growing' method for finding a minimum spanning tree, when applied to a network in which all degrees are about $d$ and the edges $e$ have independent identically distributed random weights $w(e)$.

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$.

We prove that for sufficiently large $\Delta$, the total chromatic number of any graph with maximum degree $\Delta$ is at most $\Delta + 10^4$. This is joint work with Bruce Reed.

This work presents an {\em average case} analysis of {\em fully dynamic} graph connectivity (when the operations are edge insertions and deletions). We introduce the model of {\em stochastic graph processes}, i.e. dynamically changing random graphs with random equiprobable edge insertions and deletions, which generalizes Erd{\"o}s and Renyi's 35 year-old random graph process. As the stochastic graph process continues indefinitely, all potential edge locations (in $V \times V$) may be repeatedly inspected (and learned) by the algorithm. This learning of the structure seems to imply that traditional random graph analysis methods cannot be employed (since an observed edge is not a random event anymore). However, we show that a small (logarithmic) number of dynamic random updates are enough to allow our algorithm to re-examine edges as if they were {\em random with respect to certain events} (i.e. the graph ``forgets'' its structure). This {\em short memory} property of the stochastic graph process enables us to present an algorithm for graph connectivity which admits an {\em amortized expected} cost of $O(\log^{3}n)$ time per update. In contrast, the best known deterministic worst-case algorithms for fully dynamic connectivity require $n^{1/2}$ time per update.

The main problem is to find some estimates for the rate of convergence of a random walk. One of the most abstract and powerful approaches to this problem is based on strong stationary times and was introduced by Aldous and Diaconis in 1986. Unfortunately in most cases these times are hard to construct and other approaches have been used. We present new constructions of strong stationary times which are based on a group structure and subsequently give strong upper bounds.

Joint work with I. Benjamini and Y. Peres.

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.

A graph $H$ is overfull if $|V(H)|$ is odd and $|E(H)| > \Delta(H)(|V(H)|-1)/2$. Hilton conjectured the following:

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.

The goal of our study is a detailed probabilistic analysis of a well-known maximum matching greedy suggested and analyzed by Karp and Sipser for the random graph $G\bigl(n,\mbox{Prob(edge)}=c/n\bigr)$. This is a two-phase algorithm in which a matching set is constructed one edge at a time, by randomly selecting edges among those incident to pendant vertices, or---in absence of such vertices---among all edges present, and deleting the incident edges in either case. Tightening the Karp--Sipser results, we show that for the case $ce$ whp the phase 2 matches all but $O(n^{1/4+\varepsilon})$ of the remaining vertices, and this provides a strong error estimate for the algorithm. Our approach is based on exponential supermartingales constructed >from the integrals of the differential equations that provide a mean values approximation for the deletion process. The equations had been obtained and used by Karp and Sipser, but whether the integrals could be found has remained an open problem.

We discuss bounding the chromatic number by convex combinations of the clique size and the maximum degree. We present applications of this result to various problems including strong edge colouring. This is joint work with Mike Molloy.

For any fixed connected graph $G$ let $f_n(d)$ denote the minimum possible proportion of the set of all points in $G^n$ whose distance from some set $S$ of at least $|G^n|/2$ points in $G^n$ is at least $d$, where the minimum is taken over all possible such sets $S$. Using martingale techniques we find an asymptotic formula for $\ln f_n(d)$ when $n^{1/2}\ll d\ll n$. The formula involves what we call the spread constant $c=c(G)$ which may be of independent interest. (Joint work with Noga Alon.)

We introduce here a new probabilistic technique based on properties of a special class of quadratic systems, which are similar to (but more general than) the classical crossover systems. We prove the fast convergence of such systems to a unique steady state. We also indicate when such systems have a uniform steady state probability distribution. This is shown via the relation of such systems to some special Markov chains. As an application we show how to generate in RNC, almost uniformly, a matching from the set of all matchings in a graph. This implies an RNC algorithm for approximate counting of matchings. We also extend the result to the RNC generation of perfect matchings in a dense bipartite graph and to the approximation of the permanent in RNC.

A major conjecture of Beck and Fiala is that matrices A with entries in ${-1,0,1}$ and no column having more than t nonzeroes, have discrepancy $disc(A) = O(\sqrt(t))$; any bound of $o(t)$ would be very interesting. We show that certain related discrepancy measures of A that are lower bounds on $disc(A)$, are $o(t)$. We also show that $disc(A) = O(\sqrt t log n)$, improving the Beck-Spencer bound of $O(\sqrt t \log t \log n)$. We show improved upper bounds on the discrepancy of two well-studied combinatorial families of matrices: p permutations of [n], and rectangles containing n points in $R^k$ (for k = 2, 3, 4).

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

Previous: Participation
Next: Registration
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on October 8, 1996.