We consider two interrelated tasks in a synchronous $n$-node ring: distributed constant colouring and local communication. We investigate the impact of the amount of knowledge available to nodes on the time of completing these tasks. Every node knows the labels of nodes up to a distance $r$ from it, called the knowledge radius. In distributed constant colouring every node has to assign itself one out of a constant number of colours, so that adjacent nodes get different colours. In local communication every node has to communicate a message to both of its neighbours. We study these problems in two popular communication models: the one-way model, in which each node can only either transmit to one neighbour or receive from one neighbour, in any round, and the radio model, in which simultaneous receiving from two neighbours results in interference noise. Hence the main problem in fast execution of the above tasks is breaking symmetry with restricted knowledge of the ring.

We show that distributed constant colouring and local communication are tightly related and one can be used to accomplish the other. Also, in most situations the optimal time is the same for both of them, and it strongly depends on knowledge radius. For knowledge radius $r=0$, i.e., when each node knows only its own label, our bounds on time for both tasks are tight in both models: the optimal time in the one-way model is $\Theta(n)$, while in the radio model it is $\Theta(\log n)$. For knowledge radius $r=1$ both tasks can be accomplished in time $O(\log \log n)$ in the one-way model, if the ring is oriented. For $2 \leq r \leq c \log ^* n$, where $c < 1/2$, the upper bounds on time are $O(\log^{(2r)} n)$ in the one-way model and $O(\log ^{(2\lfloor r/2 \rfloor)} n)$ in the radio model; the lower bound is $\Omega (\log^* n)$, in both models. For $r \geq (\log^*n)/2$ both tasks can be completed in constant time, in the one-way model, and distributed constant colouring also in the radio model. Finally, if $r \geq \log^*n$ then constant time is also enough for local communication in the radio model.

Let $C$ be a code of length $n$ over an alphabet of $q$ letters. A codeword $y$ is called a descendant of a set of $t$ codewords $\{x^1,\dots,x^t\}$ if $y_i \in \{x^1_i,\dots,x^t_i\}$ for all $i=1,\dots,n$. A code is said to have the Identifiable Parent Property of order $t$ if, for any word of length $n$ that is a descendant of at most $t$ codewords (parents), it is possible to identify at least one of them. Let $f_t(n,q)$ be the maximum possible cardinality of such a code. We prove that for any $t,n,q$, $(c_1(t)q)^{\frac{n}{s(t)}} < f_t(n,q) < c_2(t)q^{\lceil{\frac{n}{s(t)}}\rceil}$ where $s(t) = \lfloor(\frac{t}{2}+1)^2 \rfloor -1$ and $c_1(t),c_2(t)$ are some functions of $t$. We also show some bounds and constructions for $f_3(5,q)$, $f_3(6,q)$, and $f_t(n,q)$ when $n < s(t)$.

Improving an old result of Clarkson, Edelsbrunner, Guibas, Sharir and Welzl, we show that the number of distinct distances determined by a set $P$ of $n$ points in three-dimensional space is $\Omega(n^{77/141-\varepsilon})=\Omega(n^{0.546})$, for any $\varepsilon>0$. Moreover, there always exists a point $p\in P$ from which there are at least so many distinct distances to the remaining elements of $P$. The same result holds for points on the three-dimensional sphere. As a consequence, we obtain analogous results in higher dimensions.

This special issue is devoted to the Analysis of Algorithms (AofA). Most of the papers are from the Eighth Seminar on Analysis of Algorithms, held in Strobl, Austria, June 23–29, 2002.

The Tutte polynomial $T(G;x,y)$ of a graph evaluates to many interesting combinatorial quantities at various points in the $(x,y)$ plane, including the number of spanning trees, number of forests, number of acyclic orientations, the reliability polynomial, the partition function of the Q-state Potts model of a graph, and the Jones polynomial of an alternating link. The exact computation of $T(G;x,y)$ has been shown by Vertigan and Welsh [8] to be #P-hard at all but a few special points and on two hyperbolae, even in the restricted class of planar bipartite graphs. Attention has therefore been focused on approximation schemes. To date, positive results have been restricted to the upper half plane $y>1$, and most results have relied on a condition of sufficient denseness in the graph. In this paper we present an approach that yields a fully polynomial randomized approximation scheme for $T(G;x,y)$ for $x>1,\ y=1$, and for $T(G;2,0)$, in a class of sparse graphs. This is the first positive result that includes the important point $(2,0)$.

Let graph $G=(V,E)$ and integer $b\geq 1$ be given. A set $S\subseteq V$ is said to be $b$-independent if $u,v\in S$ implies $d_G(u,v)>b$, where $d_G(u,v)$ is the shortest distance between $u$ and $v$ in $G$. The $b$-independence number $\a_b(G)$ is the size of the largest $b$-independent subset of $G$. When $b=1$ this reduces to the standard definition of independence number.

We study this parameter in relation to the random graph $G_{n,p},\,p=d/n$, in particular, when $d$ is a large constant. We show that w.h.p. if $d\geq d_{\epsilon, b}$, $$ \left| \alpha_b(G_{n,p}) - \frac{2bn}{d^b} \biggl(\log{d} - \frac{\log{\log{d}}}{b} - \frac{\log{2b}}{b} + \frac{1}{b}\biggr)\right| \leq \frac{\epsilon n}{d^b}.$$

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

It is shown that the hard-core model on ${{\mathbb Z}}^d$ exhibits a phase transition at activities above some function $\lambda(d)$ which tends to zero as $d\rightarrow \infty$. More precisely, consider the usual nearest neighbour graph on ${{\mathbb Z}}^d$, and write ${\cal E}$ and ${\cal O}$ for the sets of even and odd vertices (defined in the obvious way). Set $${\cal G}L_M={\cal G}L_M^d =\{z\in{{\mathbb Z}}^d:\|z\|_{\infty}\leq M\},\quad \partial^{\star} {\cal G}L_M =\{z\in{{\mathbb Z}}^d:\|z\|_{\infty}= M\},$$ and write ${\cal I}({\cal G}L_M)$ for the collection of independent sets (sets of vertices spanning no edges) in ${\cal G}L_M$. For $\lambda>0$ let ${\bf I}$ be chosen from ${\cal I}({\cal G}L_M)$ with $\Pr({\bf I}=I) \propto \lambda^{|I|}$.

TheoremThere is a constant$C$such that if$\lambda > Cd^{-1/4}\log^{3/4}d$, then$$\lim_{M\rightarrow\infty}\Pr(\underline{0}\in{\bf I}|{\bf I}\supseteq \partial^{\star} {\cal G}L_M\cap {\cal E})~> \lim_{M\rightarrow\infty}\Pr(\underline{0}\in{\bf I}| {\bf I}\supseteq \partial^{\star} {\cal G}L_M\cap {\cal O}).$$ Thus, roughly speaking, the influence of the boundary on behaviour at the origin persists as the boundary recedes.

This note presents two results on real zeros of chromatic polynomials. The first result states that if $G$ is a graph containing a $q$-tree as a spanning subgraph, then the chromatic polynomial $P(G,\lambda)$ of $G$ has no non-integer zeros in the interval $(0,q)$. Sokal conjectured that for any graph $G$ and any real $\lambda>\Delta(G)$, $P(G,\lambda)>0$. Our second result confirms that it is true if $\Delta(G)\ge \lfloor n/3\rfloor -1$, where $n$ is the order of $G$.

The notion of the influence of a variable on a Boolean function on a product space has attracted much attention in combinatorics, computer science and other fields. Two of the basic papers dealing with this notion are by Kahn, Kalai and Linial (KKL) and Bourgain, Kahn, Kalai, Katznelson and Linial (BKKKL).

In this paper we survey the results in those papers and offer some simpler proofs, corrections, and extensions of the theorems presented there. We present several related open problems.

We show that all maximum length paths in a connected circular arc graph have non-empty intersection.

Two infinite 0–1 sequences are called compatible when it is possible to cast out $0\,$s from both in such a way that they become complementary to each other. Answering a question of Peter Winkler, we show that if the two 0–1 sequences are random i.i.d. and independent from each other, with probability $p$ of $1\,$s, then if $p$ is sufficiently small they are compatible with positive probability. The question is equivalent to a certain dependent percolation with a power-law behaviour: the probability that the origin is blocked at distance $n$ but not closer decreases only polynomially fast and not, as usual, exponentially.

We consider a random generalized railway defined as a random 3-regular multigraph where some vertices are regarded as switches that only allow traffic between certain pairs of attached edges. It is shown that the probability that the generalized railway is functioning is linear in the proportion of switches. Thus there is no threshold phenomenon for this property.

We consider random planar graphs on $n$ labelled nodes, and show in particular that if the graph is picked uniformly at random then the expected number of edges is at least $\frac{13}{7}n +o(n)$. To prove this result we give a lower bound on the size of the set of edges that can be added to a planar graph on $n$ nodes and $m$ edges while keeping it planar, and in particular we see that if $m$ is at most $\frac{13}{7}n - c$ (for a suitable constant~$c$) then at least this number of edges can be added.

We give an algorithm that, with high probability, recovers a planted $k$-partition in a random graph, where edges within vertex classes occur with probability $p$ and edges between vertex classes occur with probability $r\ge p+c\sqrt{p\log n/n}$. The algorithm can handle vertex classes of different sizes and, for fixed $k$, runs in linear time. We also give variants of the algorithm for partitioning matrices and hypergraphs.

Let $G$ be a finite graph with maximum degree at most $d$. Then, for every partition of $V(G)$ into classes of size $3d-1$, there exists a proper colouring of $G$ with $3d-1$ colours in which each class receives all $3d-1$ colours.

We give results on the strong connectivity for spaces of sparse random digraphs specified by degree sequence. A full characterization is provided, in probability, of the fan-in and fan-out of all vertices including the number of vertices with small ($o(n)$) and large ($cn$) fan-in or fan-out. We also give the size of the giant strongly connected component, if any, and the structure of the bow-tie digraph induced by the vertices with large fan-in or fan-out. Our results follow a direct analogy of the extinction probabilities of classical branching processes.

Let ${\bf C}$ denote the field of complex numbers and $\Omega_n$ the set of $n$th roots of unity. For $t = 0,\ldots,n-1$, define the ideal $\Im(n,t+1) \subset {\bf C}[x_0,\ldots,x_{t}]$ consisting of those polynomials in $t+1$ variables that vanish on distinct $n$th roots of unity; that is, $f \in \Im(n,t+1)$ if and only if $f(\omega_0,\ldots,\omega_{t}) = 0$ for all $(\omega_0,\ldots,\omega_{t}) \in \Omega_n^{t+1}$ satisfying $\omega_i \neq \omega_j$, for $0 \le i < j \le t$.

In this paper we apply Gröbner basis methods to give a Combinatorial Nullstellensatz characterization of the ideal $\Im(n,t+1)$. In particular, if $f \in {\bf C}[x_0,\ldots,x_{t}]$, then we give a necessary and sufficient condition on the coefficients of $f$ for membership in $\Im(n,t+1)$.

Sampling formulas describe probability laws of exchangeable combinatorial structures like partitions and compositions. We give a brief account of two known parametric families of sampling formulas for compositions and add a new family to the list.

We consider Boolean functions over $n$ variables. Any such function can be represented (and computed) by a complete binary tree with and or or in the internal nodes and a literal in the external nodes, and many different trees can represent the same function, so that a fundamental question is related to the so-called complexity of a Boolean function: $L(f):=$ minimal size of a tree computing $f$.

The existence of a limiting probability distribution $P(\cdot)$ on the set of and/or trees was shown by Lefmann and Savický [8]. We give here an alternative proof, which leads to effective computation in simple cases. We also consider the relationship between the probability $P(f)$ and the complexity $L(f)$ of a Boolean function $f$. A detailed analysis of the functions enumerating some sub-families of trees, and of their radius of convergence, allows us to improve on the upper bound of $P(f)$, established by Lefmann and Savický.