Motivated by the problem of making correct computations from partly false information, we study a corruption of the classic game “Twenty Questions” in which the player who answers the yes-or-no questions is permitted to lie up to a fixed fraction r of the time. The other player is allowed q arbitrary questions with which to try to determine, with certainty, which of n objects his opponent has in mind; he “wins” if he can always do so, and “wins quickly” if he can do so using only O(log n) questions.

It turns out that there is a threshold value for r below which the querier can win quickly, and above which he cannot win at all. However, the threshold value varies according to the precise rules of the game. Our “three thresholds theorem” says that when the answerer is forbidden at any point to have answered more than a fraction r of the questions incorrectly, then the threshold value is r = ½; when the requirement is merely that the total number of lies cannot exceed rq, the threshold is ⅓; and finally if the answerer gets to see all the questions before answering, the threshold drops to ¼.

In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in $\mathbb{Z}$d with random initial configurations. Formally, we are given a set $\mathcal{U}$ = {X1,. . . , Xm} of finite subsets of $\mathbb{Z}$d \ {0}, and an initial set A0 ⊂ $\mathbb{Z}$d of ‘infected’ sites, which we take to be random according to the product measure with density p. At time t ∈ $\mathbb{N}$, the set of infected sites At is the union of At-1 and the set of all x ∈ $\mathbb{Z}$d such that x + X ∈ At-1 for some X ∈ $\mathcal{U}$. Our model may alternatively be thought of as bootstrap percolation on $\mathbb{Z}$d with arbitrary update rules, and for this reason we call it $\mathcal{U}$-bootstrap percolation.

In two dimensions, we give a classification of $\mathcal{U}$-bootstrap percolation models into three classes – supercritical, critical and subcritical – and we prove results about the phase transitions of all models belonging to the first two of these classes. More precisely, we show that the critical probability for percolation on ($\mathbb{Z}$/n$\mathbb{Z}$)2 is (log n)−Θ(1) for all models in the critical class, and that it is n−Θ(1) for all models in the supercritical class.

The results in this paper are the first of any kind on bootstrap percolation considered in this level of generality, and in particular they are the first that make no assumptions of symmetry. It is the hope of the authors that this work will initiate a new, unified theory of bootstrap percolation on $\mathbb{Z}$d.

Szemerédi's Regularity Lemma is an important tool for analysing the structure of dense graphs. There are versions of the Regularity Lemma for sparse graphs, but these only apply when the graph satisfies some local density condition. In this paper, we prove a sparse Regularity Lemma that holds for all graphs. More generally, we give a Regularity Lemma that holds for arbitrary real matrices.

The question of the maximum number $\mbox{ex}(m,n,C_{2k})$ of edges in an m by n bipartite graph without a cycle of length 2k is addressed in this note. For each $k \geq 2$, it is shown that $\mbox{ex}(m,n,C_{2k}) \leq \begin{cases} (2k-3)\bigl[(mn)^{\frac{k+1}{2k}} + m + n\bigr] & \mbox{ if }k \mbox{ is odd,}\\[2pt] (2k-3)\bigl[m^{\frac{k+2}{2k}}\, n^{\frac{1}{2}} + m + n\bigr] & \mbox{ if }k \mbox{ is even.}\\ \end{cases}$

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node, without leaving any trace. We consider the task of locating a black hole in a (partially) synchronous tree network, assuming an upper bound on the time of any edge traversal by an agent. The minimum number of agents capable of identifying a black hole is two. For a given tree and given starting node we are interested in the fastest-possible black hole search by two agents. For arbitrary trees we give a 5/3-approximation algorithm for this problem. We give optimal black hole search algorithms for two ‘extreme’ classes of trees: the class of lines and the class of trees in which any internal node (including the root which is the starting node) has at least two children.

Recently, the authors gave upper bounds for the size of 3-uniform hypergraphs avoiding a given odd cycle using the definition of a cycle due to Berge. In the present paper we extend this bound to m-uniform hypergraphs (for all m ≥ 3), as well as m-uniform hypergraphs avoiding a cycle of length 2k. Finally we consider non-uniform hypergraphs avoiding cycles of length 2k or 2k + 1. In both cases we can bound |h| by O(n1+1/k) under the assumption that all h ∈ ε() satisfy |h| ≥ 4k2.

We prove that the probability i(n, k) that a random permutation of an n element set has an invariant subset of precisely k elements decreases as a power of k, for k ≤ n/2. Using this fact, we prove that the fraction of elements of Sn belong to transitive subgroups other than Sn or An tends to 0 when n → ∞, as conjectured by Cameron. Finally, we show that for every ∈ > 0 there exists a constant C such that C elements of the symmetric group Sn, chosen randomly and independently, generate invariably Sn with probability at least 1 − ∈. This confirms a conjecture of McKay.

The problem of probabilistic representability of semimatroids over a four-element set is solved. In this problem, one looks for all combinations of conditional independences within four random variables which can occur simultaneously. New properties of the stochastic conditional independences are deduced from conditional information inequalities. Examples of four-tuples of random variables are presented to show the probabilistic representability of three non-Ingleton semimatroids.

We give short proofs of the following two results: Thomas's theorem that every finite graph has a linked tree-decomposition of width no greater than its tree-width; and the ‘tree-width duality theorem’ of Seymour and Thomas, that the tree-width of a finite graph is exactly one less than the largest order of its brambles.

A graph is $k$-linked if for every list of $2k$ vertices $\{s_1,{\ldots}\,s_k, t_1,{\ldots}\,t_k\}$, there exist internally disjoint paths $P_1,{\ldots}\, P_k$ such that each $P_i$ is an $s_i,t_i$-path. We consider degree conditions and connectivity conditions sufficient to force a graph to be $k$-linked.

Let $D(n,k)$ be the minimum positive integer $d$ such that every $n$-vertex graph with minimum degree at least $d$ is $k$-linked and let $R(n,k)$ be the minimum positive integer $r$ such that every $n$-vertex graph in which the sum of degrees of each pair of non-adjacent vertices is at least $r$ is $k$-linked. The main result of the paper is finding the exact values of $D(n,k)$ and $R(n,k)$ for every $n$ and $k$.

Thomas and Wollan [14] used the bound $D(n,k)\leq (n+3k)/2-2$ to give sufficient conditions for a graph to be $k$-linked in terms of connectivity. Our bound allows us to modify the Thomas–Wollan proof slightly to show that every $2k$-connected graph with average degree at least $12k$ is $k$-linked.

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n [ges ] n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

Extremal graph theory has a great number of conjectures concerning the embedding of large sparse graphs into dense graphs. Szemerédi's Regularity Lemma is a valuable tool in finding embeddings of small graphs. The Blow-up Lemma, proved recently by Komlós, Sárközy and Szemerédi, can be applied to obtain approximate versions of many of the embedding conjectures. In this paper we review recent developments in the area.

Let {X1 , . . , Xn} be a collection of binary-valued random variables and let f : {0, 1}n → $\mathbb{R}$ be a Lipschitz function. Under a negative dependence hypothesis known as the strong Rayleigh condition, we show that f − ${\mathbb E}$f satisfies a concentration inequality. The class of strong Rayleigh measures includes determinantal measures, weighted uniform matroids and exclusion measures; some familiar examples from these classes are generalized negative binomials and spanning tree measures. For instance, any Lipschitz-1 function of the edges of a uniform spanning tree on vertex set V (e.g., the number of leaves) satisfies the Gaussian concentration inequality

\begin{linenomath}$${{\mathbb P} (f - {\mathbb E} f \geq a) \leq \exp \biggl( - \frac{a^2}{8 \, |V|} \biggr) }.$$\end{linenomath}

Upper and lower bounds are proved for the maximum number of triangles in C2k+1-free graphs. The bounds involve extremal numbers related to appropriate even cycles.

Finite graph homology may seem trivial, but for infinite graphs things become interesting. We present a new ‘singular’ approach that builds the cycle space of a graph not on its finite cycles but on its topological circles, the homeomorphic images of $S^1$ in the space formed by the graph together with its ends.

Our approach permits the extension to infinite graphs of standard results about finite graph homology – such as cycle–cocycle duality and Whitney's theorem, Tutte's generating theorem, MacLane's planarity criterion, the Tutte/Nash-Williams tree packing theorem – whose infinite versions would otherwise fail. A notion of end degrees motivated by these results opens up new possibilities for an ‘extremal’ branch of infinite graph theory.

Numerous open problems are suggested.

Let $c$ be a constant and $(e_1,f_1), (e_2,f_2), \dots, (e_{cn},f_{cn})$ be a sequence of ordered pairs of edges on vertex set $[n]$ chosen uniformly and independently at random. Let $A$ be an algorithm for the on-line choice of one edge from each presented pair, and for $i= 1,\hellip,cn$ let $G_A(i)$ be the graph on vertex set $[n]$ consisting of the first $i$ edges chosen by $A$. We prove that all algorithms in a certain class have a critical value $c_A$ for the emergence of a giant component in $G_A(cn) (ie$, if $c \gt c_A$, then with high probability the largest component in $G_A(cn)$ has $o(n)$ vertices, and if $c > c_A$ then with high probability there is a component of size $\Omega(n)$ in $G_A(cn))$. We show that a particular algorithm in this class with high probability produces a giant component before $0.385 n$ steps in the process ($ie$, we exhibit an algorithm that creates a giant component relatively quickly). The fact that another specific algorithm that is in this class has a critical value resolves a conjecture of Spencer.

In addition, we establish a lower bound on the time of emergence of a giant component in any process produced by an on-line algorithm and show that there is a phase transition for the off-line version of the problem of creating a giant component.

For a graph G on vertex set V = {1, …, n} let k = (k1, …, kn) be an integral vector such that 1 [les ] ki [les ] di for i ∈ V, where di is the degree of the vertex i in G. A k-dominating set is a set Dk ⊆ V such that every vertex i ∈ V[setmn ]Dk has at least ki neighbours in Dk. The k-domination number γk(G) of G is the cardinality of a smallest k-dominating set of G.

For k1 = · · · = kn = 1, k-domination corresponds to the usual concept of domination. Our approach yields an improvement of an upper bound for the domination number found by N. Alon and J. H. Spencer.

If ki = di for i = 1, …, n, then the notion of k-dominating set corresponds to the complement of an independent set. A function fk(p) is defined, and it will be proved that γk(G) = min fk(p), where the minimum is taken over the n-dimensional cube Cn = {p = (p1, …, pn) [mid ] pi ∈ ℝ, 0 [les ] pi [les ] 1, i = 1, …, n}. An [Oscr ](Δ22Δn-algorithm is presented, where Δ is the maximum degree of G, with INPUT: p ∈ Cn and OUTPUT: a k-dominating set Dk of G with [mid ]Dk[mid ][les ]fk(p).

Motivated by the result that an ‘approximate’ evaluation of the Jones polynomial of a braid at a 5th root of unity can be used to simulate the quantum part of any algorithm in the quantum complexity class BQP, and results relating BQP to the counting class GapP, we introduce a form of additive approximation which can be used to simulate a function in BQP. We show that all functions in the classes #P and GapP have such an approximation scheme under certain natural normalizations. However, we are unable to determine whether the particular functions we are motivated by, such as the above evaluation of the Jones polynomial, can be approximated in this way. We close with some open problems motivated by this work.

A simple proof is given of the best-known upper bound on the cardinality of a set of vectors of length t over an alphabet of size b, with the property that, for every subset of k vectors, there is a coordinate in which they all differ. This question is motivated by the study of perfect hash functions.

We describe a time randomized algorithm that estimates the number of feasible solutions of a multidimensional knapsack problem within 1 ± ε of the exact number. (Here r is the number of constraints and n is the number of integer variables.) The algorithm uses a Markov chain to generate an almost uniform random solution to the problem.