Let (r−1)n ≥ rk and let . Suppose that F1 ∩ ⋅⋅⋅ ∩ Fr ≠ ∅ holds for all Fi ∈ i, 1 ≤ i ≤ r. Then we show that .

Let G be an abelian group of order n and let μ be a sequence of elements of G with length 2n−k+1 taking k distinct values. Assuming that no value occurs n−k+3 times, we prove that the sums of the n-subsequences of μ must include a non-null subgroup. As a corollary we show that if G is cyclic then μ has an n-subsequence summing to 0. This last result, conjectured by Bialostocki, reduces to the Erdos–Ginzburg–Ziv theorem for k=2.

Let [Fscr ] be a family of forbidden k-hypergraphs (k-uniform set systems). An [Fscr ]-saturated hypergraph is a maximal k-uniform set system not containing any member of [Fscr ]. As the main result we prove that, for any finite family [Fscr ], the minimum number of edges of an [Fscr ]-saturated hypergraph is O(nk−1). In particular, this implies a conjecture of Tuza. Some other related results are presented.

We generalize the notion of choice number from graphs to hypergraphs and estimate the sharp order of magnitude of the choice number of random hypergraphs. It turns out that the choice number and the chromatic number of a random hypergraph have the same order of magnitude, almost surely. Our result implies an earlier bound on the chromatic number of random hypergraphs, proved by Schmidt [23] using a different method.

We consider analogues of van der Waerden's theorem and Szemerédi's theorem, where arithmetic progressions are replaced by binary trees with a fixed distance between successive vertices. The proofs are based on some novel recurrence properties for Markov processes.

We put the final piece into a puzzle first introduced by Bollobás, Erdõs and Szemerédi in 1975. For arbitrary positive integers $n$ and $r$ we determine the largest integer $\Delta=\Delta (r,n)$, for which any $r$-partite graph with partite sets of size $n$ and of maximum degree less than $\Delta$ has an independent transversal. This value was known for all even $r$. Here we determine the value for odd $r$ and find that $\Delta(r,n)=\Delta(r-1,n)$. Informally this means that the addition of an oddth partite set does not make it any harder to guarantee an independent transversal.

In the proof we establish structural theorems which could be of independent interest. They work for all$r\geq 7$, and specify the structure of slightly sub-optimal graphs for even$r\geq 8$.

This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2). Here the diameter refers to the maximum distance from a vertex υ to a vertex w where (υ, w) is from the transitive closure of G – which is also the transitive closure of G ∪ S. This result provides support for the author's previous conjecture that such a set S achieving a diameter polylogarithmic in the number of vertices exists for any digraph. The result also adresses an open question of Chazelle, who did some related work on trees, and suggested the generalization to the planar cases.

If G is a plane, cubic graph, then G has a drawing such that each edge is a straight line segment and each bounded face has any prescribed area. The special case where all areas are the same proves a conjecture of G. Ringel, who gave an example of a plane triangulation that cannot be drawn in this way.

A polynomial-time randomised algorithm for uniformly generating forests in a dense graph is presented. Using this, a fully polynomial randomised approximation scheme (fpras) for counting the number of forests in a dense graph is created.

A theorem of Makarov states that the harmonic measure of a connected subset of ℝ2 is supported on a set of Hausdorff dimension one. This paper gives an analogue of this theorem for discrete harmonic measure, i.e., the hitting measure of simple random walk. It is proved that for any 1/2 < α < 1, β < α − 1/2, there is a constant k such that for any connected subset A ⊂ ℤ2 of radius n,

where HA denotes discrete harmonic measure.

Given a family [Fscr ] of r-graphs, let ex(n, [Fscr ]) be the maximum number of edges in an n-vertex r-graph containing no member of [Fscr ]. Let C(r)4 denote the family of r-graphs with distinct edges A, B, C, D, such that A ∩ B = C ∩ D = Ø and A ∪ B = C ∪ D. For s1 [les ] … [les ] sr, let K(r) (s1,…,sr) be the complete r-partite r-graph with parts of sizes s1,…,sr.

Füredi conjectured over 15 years ago that ex(n,C(3)4) [les ] (n2) for sufficiently large n. We prove the weaker result

ex(n, {C(3)4, K(3)(1,2,4)}) [les ] (n2).

Generalizing a well-known conjecture for the Turán number of bipartite graphs, we conjecture that

ex(n, K(r)(s1,…,sr)) = Θ(nr−1/s),

where s = Πr−1i=1si. We prove this conjecture when s1 = … = sr−2 = 1 and

(i) sr−1 = 2, (ii) sr−1 = sr = 3, (iii)sr > (sr−1−1)!.

In cases (i) and (ii), we determine the asymptotic value of ex(n,K(r)(s1,…,sr)).

We also provide an explicit construction giving

ex(n,K(3)(2,2,3)) > (1/6−o(1))n8/3.

This improves upon the previous best lower bound of Ω(n29/11) obtained by probabilistic methods. Several related open problems are also presented.

Belief propagation (BP) is a message-passing algorithm that computes the exact marginal distributions at every vertex of a graphical model without cycles. While BP is designed to work correctly on trees, it is routinely applied to general graphical models that may contain cycles, in which case neither convergence, nor correctness in the case of convergence is guaranteed. Nonetheless, BP has gained popularity as it seems to remain effective in many cases of interest, even when the underlying graph is ‘far’ from being a tree. However, the theoretical understanding of BP (and its new relative survey propagation) when applied to CSPs is poor.

Contributing to the rigorous understanding of BP, in this paper we relate the convergence of BP to spectral properties of the graph. This encompasses a result for random graphs with a ‘planted’ solution; thus, we obtain the first rigorous result on BP for graph colouring in the case of a complex graphical structure (as opposed to trees). In particular, the analysis shows how belief propagation breaks the symmetry between the 3! possible permutations of the colour classes.

In this paper, I give a short proof of a recent result by Sokal, showing that all zeros of the chromatic polynomial $P_G(q)$ of a finite graph $G$ of maximal degree $D$ lie in the disk $|q|< K D$, where $K$ is a constant that is strictly smaller than 8.

One of the first graph-theoretical problems to be given serious attention (in the 1950s) was the decision whether a given integer sequence is equal to the degree sequence of a simple graph (or graphical, for short). One method to solve this problem is the greedy algorithm of Havel and Hakimi, which is based on the swap operation. Another, closely related question is to find a sequence of swap operations to transform one graphical realization into another of the same degree sequence. This latter problem has received particular attention in the context of rapidly mixing Markov chain approaches to uniform sampling of all possible realizations of a given degree sequence. (This becomes a matter of interest in the context of the study of large social networks, for example.) Previously there were only crude upper bounds on the shortest possible length of such swap sequences between two realizations. In this paper we develop formulae (Gallai-type identities) for the swap-distances of any two realizations of simple undirected or directed degree sequences. These identities considerably improve the known upper bounds on the swap-distances.

In 1978 Erdős, Faudree, Rousseau and Schelp conjectured that \[ r ( C_{p},K_{r} ) = ( p-1 ) (r-1) +1 \] for every $p\,{\geq}\,r\,{\geq}\,3$, except for $p\,{=}\,q\,{=}\,3$. This has been proved for $r\,{\leq}\,6$, and for \[ p \geq r^{2}-2r\].

In this note we prove the conjecture for $p\,{\geq}\,4r+2$.

Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences $E_N\in\{-1,1\}^N$ in order to measure their ‘level of randomness’. Two of these parameters are the normality measure$\cal{N}(E_N)$ and the correlation measure$C_k(E_N)$of order k, which focus on different combinatorial aspects of $E_N$. In their work, amongst others, Mauduit and Sárközy investigated the minimal possible value of these parameters.

In this paper, we continue the work in this direction and prove a lower bound for the correlation measure $C_k(E_N)$ (k even) for arbitrary sequences $E_N$, establishing one of their conjectures. We also give an algebraic construction for a sequence $E_N$ with small normality measure $\cal{N}(E_N)$.

The lifetime of a player is defined to be the time where he gets his b-th hit, where a hit will occur with probability p. We consider the maximum statistics of N independent players. For b≠1 this is significantly more difficult than the known instance b=1. The expected value of the maximum lifetime of N players is given by logQN+(b−1)logQ logQN+ smaller order terms, where Q=1/(1−p).

We propose a new method, probabilistic divide-and-conquer, for improving the success probability in rejection sampling. For the example of integer partitions, there is an ideal recursive scheme which improves the rejection cost from asymptotically order n3/4 to a constant. We show other examples for which a non-recursive, one-time application of probabilistic divide-and-conquer removes a substantial fraction of the rejection sampling cost.

We also present a variation of probabilistic divide-and-conquer for generating i.i.d. samples that exploits features of the coupon collector's problem, in order to obtain a cost that is sublinear in the number of samples.

Bollobás and Scott (Random Struct. Alg.21 (2002) 414–430) asked for conditions that guarantee a bisection of a graph with m edges in which each class has at most (1/4+o(1))m edges. We demonstrate that cycles of length 4 play an important role for this question. Let G be a graph with m edges, minimum degree δ, and containing no cycle of length 4. We show that if (i) G is 2-connected, or (ii) δ ⩾ 3, or (iii) δ ⩾ 2 and the girth of G is at least 5, then G admits a bisection in which each class has at most (1/4+o(1))m edges. We show that each of these conditions are best possible. On the other hand, a construction by Alon, Bollobás, Krivelevich and Sudakov shows that for infinitely many m there exists a graph with m edges and girth at least 5 for which any bisection has at least (1/4−o(1))m edges in one of the two classes.

Thinking of a deterministic function s: ℤ → ℕ as ‘scenery’ on the integers, a simple random walk on ℤ generates a random record of scenery ‘observed’ along the walk. We address this question: If t:ℤ → ℕ is another scenery on the integers and we are handed a random scenery record obtained from either s or t, under what circumstances can the source be distinguished? We allow ourselves to use information about s and t together with information contained in the scenery record. It has been conjectured that it is sufficient for t to be neither a translate of s nor a translate of the reflection of s. We show that this condition is sufficient to ensure distinguishability if s−1(δ) is finite and non-empty for some δ ∈ℕ.