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.

It is shown that the maximum possible chromatic number of the square of a graph with maximum degree d and girth g is (1 +o(1))d2 if g = 3, 4, 5 or 6, and is Θ(d2 / log d) if g [ges ] 7. Extensions to higher powers are considered as well.

This paper shows that the largest possible contrast $C_{k,n}$ in a $k$-out-of-$n$ secret sharing scheme is approximately $4^{-(k-1)}$. More precisely, we show that $4^{-(k-1)} \leq C_{k,n} \leq 4^{-(k-1)}n^k/(n(n-1)\cdots(n-(k-1)))$. This implies that the largest possible contrast equals $4^{-(k-1)}$ in the limit when $n$ approaches infinity. For large $n$, the above bounds leave almost no gap. For values of $n$ that come close to $k$, we will present alternative bounds (being tight for $n=k$). The proofs of our results proceed by finding a relationship between the largest possible contrast in a secret sharing scheme and the smallest possible approximation error in problems occurring in approximation theory.

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.

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.

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.

A string graph is the intersection graph of a collection of continuous arcs in the plane. We show that any string graph with m edges can be separated into two parts of roughly equal size by the removal of vertices. This result is then used to deduce that every string graph with n vertices and no complete bipartite subgraph Kt,t has at most ctn edges, where ct is a constant depending only on t. Another application shows that locally tree-like string graphs are globally tree-like: for any ε > 0, there is an integer g(ε) such that every string graph with n vertices and girth at least g(ε) has at most (1 + ε)n edges. Furthermore, the number of such labelled graphs is at most (1 + ε)nT(n), where T(n) = nn−2 is the number of labelled trees on n vertices.

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.

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.

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.

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}

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. We say that percolation occurs if eventually every vertex is infected.

The elements of the set of initially infected vertices, A ⊂ V(G), are normally chosen independently at random, each with probability p, say. This process has been extensively studied on the sequence of torus graphs [n]d, for n = 1,2, . . ., where d = d(n) is either fixed or a very slowly growing function of n. For example, Cerf and Manzo [17] showed that the critical probability is o(1) if d(n) ≤ log*n, i.e., if p = p(n) is bounded away from zero then the probability of percolation on [n]d tends to one as n → ∞.

In this paper we study the case when the growth of d to ∞ is not excessively slow; in particular, we show that the critical probability is 1/2 + o(1) if d ≥ (log log n)2 log log log n, and give much stronger bounds in the case that G is the hypercube, [2]d.

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.

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.

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.