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.

Many of the classical results of Ramsey Theory, including those of Hilbert, Schur, and van der Waerden, are naturally stated as instances of the following problem: given a u × ν matrix A with rational entries, is it true, that whenever the set ℕ of positive integers is finitely coloured, there must exist some x∈ℕν such that all entries of Ax are the same colour? While the theorems cited are all consequences of Rado's theorem, the general problem had remained open. We provide here several solutions for the alternate problem, which asks that x∈ℕν. Based on this, we solve the general problem, giving various equivalent characterizations.

Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then connects pairs of points by an edge if they are within a fixed distance of one another. In addition to giving rise to a range of basic theoretical questions, this class of random graphs has been a central analytical tool in the wireless networking community.

For many of the primary applications of wireless networks, however, the underlying environment has a large number of obstacles, and communication can only take place among nodes when they are close in space and when they have line-of-sight access to one another – consider, for example, urban settings or large indoor environments. In such domains, the standard model of random geometric graphs is not a good approximation of the true constraints, since it is not designed to capture the line-of-sight restrictions.

Here we propose a random-graph model incorporating both range limitations and line-of-sight constraints, and we prove asymptotically tight results for k-connectivity. Specifically, we consider points placed randomly on a grid (or torus), such that each node can see up to a fixed distance along the row and column it belongs to. (We think of the rows and columns as ‘streets’ and ‘avenues’ among a regularly spaced array of obstructions.) Further, we show that when the probability of node placement is a constant factor larger than the threshold for connectivity, near-shortest paths between pairs of nodes can be found, with high probability, by an algorithm using only local information. In addition to analysing connectivity and k-connectivity, we also study the emergence of a giant component, as well an approximation question, in which we seek to connect a set of given nodes in such an environment by adding a small set of additional ‘relay’ nodes.

We describe a short and easy-to-analyse construction of constant-degree expanders. The construction relies on the replacement product, applied by Reingold, Vadhan and Wigderson (2002) to give an iterative construction of bounded-degree expanders. Here we give a simpler construction, which applies the replacement product (only twice!) to turn the Cayley expanders of Alon and Roichman (1994), whose degree is polylog n, into constant-degree expanders. This enables us to prove the required expansion using a simple new combinatorial analysis of the replacement product (instead of the spectral analysis used by Reingold, Vadhan and Wigderson).

We show that for each α>0 every sufficiently large oriented graph G with δ+(G), δ−(G)≥3|G|/8+α|G| contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen [21]. In fact, we prove the stronger result that G is still Hamiltonian if δ(G)+δ+(G)+δ−(G)≥3|G|/2 + α|G|. Up to the term α|G|, this confirms a conjecture of Häggkvist [10]. We also prove an Ore-type theorem for oriented graphs.

A generalization of the random assignment problem asks the expected cost of the minimum-cost matching of cardinality k in a complete bipartite graph Km,n, with independent random edge weights. With weights drawn from the exponential distribution with intensity 1, the answer has been conjectured to be

Σi,j≥0, i+j<k1/(m−i)(n−j).

Here, we prove the conjecture for k [les ] 4, k = m = 5, and k = m = n = 6, using a structured, automated proof technique that results in proofs with relatively few cases. The method yields not only the minimum assignment cost's expectation but the Laplace transform of its distribution as well. From the Laplace transform we compute the variance in these cases, and conjecture that, with k = m = n → ∞, the variance is 2/n + O(log n/n2). We also include some asymptotic properties of the expectation and variance when k is fixed.

Let H be a k-uniform hypergraph on n vertices where n is a sufficiently large integer not divisible by k. We prove that if the minimum (k − 1)-degree of H is at least ⌊n/k⌋, then H contains a matching with ⌊n/k⌋ edges. This confirms a conjecture of Rödl, Ruciński and Szemerédi [13], who proved that minimum (k − 1)-degree n/k + O(log n) suffices. More generally, we show that H contains a matching of size d if its minimum codegree is d < n/k, which is also best possible.

It is well known that a graph with m edges can be made triangle-free by removing (slightly less than) m/2 edges. On the other hand, there are many classes of graphs which are hard to make triangle-free, in the sense that it is necessary to remove roughly m/2 edges in order to eliminate all triangles.

We prove that dense graphs that are hard to make triangle-free have a large packing of pairwise edge-disjoint triangles. In particular, they have more than m(1/4+cβ) pairwise edge-disjoint triangles where β is the density of the graph and c ≥ is an absolute constant. This improves upon a previous m(1/4−o(1)) bound which follows from the asymptotic validity of Tuza's conjecture for dense graphs. We conjecture that such graphs have an asymptotically optimal triangle packing of size m(1/3−o(1)).

We extend our result from triangles to larger cliques and odd cycles.

We consider a random permutation drawn from the set of 132-avoiding permutations of length n and show that the number of occurrences of another pattern σ has a limit distribution, after scaling by nλ(σ)/2, where λ(σ) is the length of σ plus the number of descents. The limit is not normal, and can be expressed as a functional of a Brownian excursion. Moments can be found by recursion.

We describe a very simple method of randomly permuting the cube {0, 1}n such that the sample space is very small, but, given any m distinct points in {0, 1}n, the images of those points under the random permutation are approximately uniformly distributed over all sequences of m distinct points.

We call a tree parameter additive if it can be determined recursively as the sum of the parameter values of all branches, plus a certain toll function. In this paper, we prove central limit theorems for very general toll functions, provided that they are bounded and small on average. Simply generated families of trees are considered as well as Pólya trees, recursive trees and binary search trees, and the results are illustrated by several examples of parameters for which we prove normal or log-normal limit laws.

We consider the problem of testing expansion in bounded-degree graphs. We focus on the notion of vertex expansion: an α-expander is a graph G = (V, E) in which every subset U ⊆ V of at most |V|/2 vertices has a neighbourhood of size at least α ⋅ |U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time . We prove that the property-testing algorithm proposed by Goldreich and Ron with appropriately set parameters accepts every α-expander with probability at least and rejects every graph that is ϵ-far from any α*-expander with probability at least , where and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is .

We show that symmetry, represented by a graph's automorphism group, can be used to greatly reduce the computational work for the substitution method. This allows application of the substitution method over larger regions of the problem lattices, resulting in tighter bounds on the percolation threshold $p_c$. We demonstrate the symmetry reduction technique using bond percolation on the $(3,12^2)$ lattice, where we improve the bounds on $p_c$ from (0.738598,0.744900) to (0.739399,0.741757), a reduction of more than 62% in width, from 0.006302 to 0.002358.

Given complex numbers w1,…,wn, we define the weight w(X) of a set X of 0–1 vectors as the sum of $w_1^{x_1} \cdots w_n^{x_n}$ over all vectors (x1,…,xn) in X. We present an algorithm which, for a set X defined by a system of homogeneous linear equations with at most r variables per equation and at most c equations per variable, computes w(X) within relative error ∊ > 0 in (rc)O(lnn-ln∊) time provided $|w_j| \leq \beta (r \sqrt{c})^{-1}$ for an absolute constant β > 0 and all j = 1,…,n. A similar algorithm is constructed for computing the weight of a linear code over ${\mathbb F}_p$. Applications include counting weighted perfect matchings in hypergraphs, counting weighted graph homomorphisms, computing weight enumerators of linear codes with sparse code generating matrices, and computing the partition functions of the ferromagnetic Potts model at low temperatures and of the hard-core model at high fugacity on biregular bipartite graphs.

The theta graph ${\Theta _{\ell ,t}}$ consists of two vertices joined by t vertex-disjoint paths, each of length $\ell $ . For fixed odd $\ell $ and large t, we show that the largest graph not containing ${\Theta _{\ell ,t}}$ has at most ${c_\ell }{t^{1 - 1/\ell }}{n^{1 + 1/\ell }}$ edges and that this is tight apart from the value of ${c_\ell }$ .

Motivated by a property of linear resistive electrical networks, we introduce the class of Rayleigh matroids. These form a subclass of the balanced matroids defined by Feder and Mihail [9] in 1992. We prove a variety of results relating Rayleigh matroids to other well-known classes – in particular, we show that a binary matroid is Rayleigh if and only if it does not contain $\mathcal{S}_{8}$ as a minor. This has the consequence that a binary matroid is balanced if and only if it is Rayleigh, and provides the first complete proof in print that $\mathcal{S}_{8}$ is the only minor-minimal binary non-balanced matroid, as claimed in [9]. We also give an example of a balanced matroid which is not Rayleigh.

We prove that there are at most {cA1/3} different lattice polygons of area A. This improves a result of V. I. Arnol'd.

We answer a question of Sós by showing that, if a graph G of order n and density p has no complete minor larger than would be found in a random graph G(n, p), then G is quasi-random, provided either p > 0.45631 … or κ(G) [ges ] n(log log log n)/(log log n), where 0.45631 … is an explicit constant.

The results proved can also be used to fill the gaps in an argument of Thomason, describing the extremal graphs having no Kt minor for given t.

We investigate the asymptotic behaviour of the average displacement of the simple random walk on the Sierpiński graph. The existence of an oscillating factor in this asymptotics is shown rigorously. The proof depends mainly on the analysis of the corresponding generating function. Using a functional equation and techniques from complex analysis we obtain the desired properties of this generating function.

The notion of conductance introduced by Jerrum and Sinclair [8] has been widely used to prove rapid mixing of Markov chains. Here we introduce a bound that extends this in two directions. First, instead of measuring the conductance of the worst subset of states, we bound the mixing time by a formula that can be thought of as a weighted average of the Jerrum–Sinclair bound (where the average is taken over subsets of states with different sizes). Furthermore, instead of just the conductance, which in graph theory terms measures edge expansion, we also take into account node expansion. Our bound is related to the logarithmic Sobolev inequalities, but it appears to be more flexible and easier to compute.

In the case of random walks in convex bodies, we show that this new bound is better than the known bounds for the worst case. This saves a factor of $O(n)$ in the mixing time bound, which is incurred in all proofs as a ‘penalty’ for a ‘bad start’. We show that in a convex body in $\mathbb{R}^n$, with diameter $D$, random walk with steps in a ball with radius $\delta$ mixes in $O^*(nD^2/\delta^2)$ time (if idle steps at the boundary are not counted). This gives an $O^*(n^3)$ sampling algorithm after appropriate preprocessing, improving the previous bound of $O^*(n^4)$.

The application of the general conductance bound in the geometric setting depends on an improved isoperimetric inequality for convex bodies.