Abstract. How small can a set of vertices in the [Formula: see text]-dimensional hypercube [Formula: see text] be if it meets every copy of [Formula: see text]? The asymptotic density of such a set (for [Formula: see text] fixed and [Formula: see text] large) is denoted by [Formula: see text]. It is easy to see that [Formula: see text], and it is known that [Formula: see text] for [Formula: see text], but it was recently shown that [Formula: see text] for [Formula: see text]. In this paper, we show that the latter phenomenon also holds for [Formula: see text] and [Formula: see text].

Abstract. How many random transpositions (meaning that we swap given pairs of elements with given probabilities independently) are needed to ensure that each element of [Formula: see text] is uniformly distributed—in the sense that the probability that [Formula: see text] is mapped to [Formula: see text] is [Formula: see text] for all [Formula: see text] and [Formula: see text]? And what if we insist that each pair is uniformly distributed? In this paper we show that the minimum for the first problem is about [Formula: see text], with this being exact when [Formula: see text] is a power of 2. For the second problem, we show that, rather surprisingly, the answer is not quadratic: [Formula: see text] random transpositions suffice. We also show that if we ask only that the pair [Formula: see text] is uniformly distributed, then the answer is [Formula: see text]. This proves a conjecture of Groenland, Johnston, Radcliffe, and Scott.

A (finite or infinite) graph is called constructible if it may be obtained recursively from the one-point graph by repeatedly adding dominated vertices. In the finite case, the constructible graphs are precisely the cop-win graphs, but for infinite graphs the situation is not well understood. One of our aims in this paper is to give a graph that is cop-win but not constructible. This is the first known such example. We also show that every countable ordinal arises as the rank of some constructible graph, answering a question of Evron, Solomon and Stahl. In addition, we give a finite constructible graph for which there is no construction order whose associated domination map is a homomorphism , answering a question of Chastand, Laviolette and Polat. Lehner showed that every constructible graph is a weak cop win (meaning that the cop can eventually force the robber out of any finite set). Our other main aim is to investigate how this notion relates to the notion of ‘locally constructible’ (every finite graph is contained in a finite constructible subgraph). We show that, under mild extra conditions, every locally constructible graph is a weak cop win. But we also give an example to show that, in general, a locally constructible graph need not be a weak cop win. Surprisingly, this graph may even be chosen to be locally finite. We also give some open problems.

In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by the nonempty subsets $A\subset \{1,\dots,n\}$, is it possible to construct a body $T\subset \mathbb{R}^n$ such that $x_A=|T_A|$, where $|T_A|$ is the $|A|$-dimensional volume of the projection of $T$ onto the subspace spanned by the axes in $A$? As it is more convenient to take logarithms, we denote by $\psi_n$ the set of all vectors $x$ for which there is a body $T$ such that $x_A=\log |T_A|$ for all $A$. Bollobás and Thomason showed that $\psi_n$ is contained in the polyhedral cone defined by the class of “uniform cover inequalities.” Tan and Zeng conjectured that the convex hull $\operatorname{conv}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. We prove that this conjecture is “nearly” right: the closed convex hull $\overline{\operatorname{conv}}(\psi_n)$ is equal to the cone given by the uniform cover inequalities. However, perhaps surprisingly, we also show that $\operatorname{conv}(\psi_n)$ is not closed for $n\ge 4$, thus disproving the conjecture.

A Boolean function $f:\{ 0,1 \}^n \to \{ 0,1 \}$ is called trivial if it depends on only one coordinate. We show that nontrivial Boolean functions of positively correlated random variables are strictly less correlated than the variables themselves. This improves on a correlation inequality of Witsenhausen. Over the last decade, several people in computer science and computer chess have investigated the problem of quality and reliability in game-tree searching, where the heuristic evaluation function is not free of errors. In random models with independent leaf values and independently occuring errors, a phenomenon of pathology was observed: the deeper the search in the tree, the worse the final estimate of the root value. The main result of this note implies that pathology is not only a feature of game trees, but appears in any sequence of increasing bivalued recursion trees with independent leaf values, independently occuring errors, and nontrivial recursion rules.

The concentration of a real-valued random variable X is \[ c ( X ) = \sup_{t \in \mathbb{R}} {\mathbf{P}} ( t < X < t + 1 ). \] Given bounds on the concentrations of n independent random variables, how large can the concentration of their sum be? The main aim of this paper is to give a best possible upper bound for the concentration of the sum of n independent random variables, each of concentration at most $1/k$, where k is an integer. Other bounds on the concentration are also discussed, as well as the case of vector-valued random variables.

The discrete torus is the graph on $\mathbb{Z}_k^n = ( \mathbb{Z}/k\mathbb{Z} )^n $ in which $x = (x_i )_1^n $ is joined to $y = (y_i )_1^n $ if for some i there is $x_i = y_i \pm 1$ and $x_j = y_j $ for all $j \ne i$. For a set $A \subset \mathbb{Z}_k^n $ and a natural number t, let $A_{( t )} $ be the set of vertices of $\mathbb{Z}_k^n $ within distance t of A. The main aim of this paper is to give a best possible lower bound for $| A_{(t)} |$ in terms of $| A |$, for even values of k.