We continue the study of regular partitions of hypergraphs. In particular, we obtain corresponding counting lemmas for the regularity lemmas for hypergraphs from our paper ‘Regular Partitions of Hypergraphs: Regularity Lemmas’ (in this issue).

Let d=1≤d1≤ d2≤···.≤ dn be a non-decreasing sequence of n positive integers, whose sum is even. Let denote the set of graphs with vertex set [n]={1,2,. . .., n} in which the degree of vertex i is di. Let Gn,d be chosen uniformly at random from . Let d=(d1+d2+···.+dn)/n be the average degree. We give a condition on d under which we can show that w.h.p. the chromatic number of is Θ(d/ln d). This condition is satisfied by graphs with exponential tails as well those with power law tails.

We consider the complexity of approximating the partition function of the ferromagnetic Ising model with varying interaction energies and local external magnetic fields. Jerrum and Sinclair provided a fully polynomial randomized approximation scheme for the case in which the system is consistent in the sense that the local external fields all favour the same spin. We characterize the complexity of the general problem by showing that it is equivalent in complexity to the problem of approximately counting independent sets in bipartite graphs, thus it is complete in a logically defined subclass of #P previously studied by Dyer, Goldberg, Greenhill and Jerrum. By contrast, we show that the corresponding computational task for the $q$-state Potts model with local external magnetic fields and $q>2$ is complete for all of #P with respect to approximation-preserving reductions.

This paper has two parts. In the first part we consider a simple Markov chain for d-regular graphs on n vertices, where d = d(n) may grow with n. We show that the mixing time of this Markov chain is bounded above by a polynomial in n and d. In the second part of the paper, a related Markov chain for d-regular graphs on a varying number of vertices is introduced, for even constant d. This is a model for a certain peer-to-peer network. We prove that the related chain has mixing time which is bounded above by a polynomial in N, the expected number of vertices, provided certain assumptions are met about the rate of arrival and departure of vertices.

Let G1 and G2 be graphs of order n with maximum degree Δ1 and Δ2, respectively. G1 and G2 are said to pack if there exist injective mappings of the vertex sets into [n], such that the images of the edge sets do not intersect. Sauer and Spencer showed that if , then G1 and G2 pack. We extend this result by showing that if , then G1 and G2 do not pack if and only if one of G1 or G2 is a perfect matching and the other either is with odd or contains .

The partition functions of the Ising and Potts models in statistical mechanics are well known to be partial evaluations of the Tutte–Whitney polynomial of the appropriate graph. The Ashkin–Teller model generalizes the Ising model and the four-state Potts model, and has been extensively studied since its introduction in 1943. However, its partition function (even in the symmetric case) is not a partial evaluation of the Tutte–Whitney polynomial. In this paper, we show that the symmetric Ashkin–Teller partition function can be obtained from a generalized Tutte–Whitney function which is intermediate in a precise sense between the usual Tutte–Whitney polynomialof the graph and that of its dual.

We study the gaps in the sequence of sums of h pairwise distinct elements of a given sequence in relation to the gaps in the sequence of sums of h not necessarily distinct elements of . We present several results on this topic. One of them gives a negative answer to a question by Burr and Erdős.

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 widely studied model for generating binary sequences is to ‘evolve’ them on a tree according to a symmetric Markov process. We show that under this model distinguishing the true (model) tree from a false one is substantially ‘easier’ (in terms of the sequence length needed) than determining the true tree. The key tool is a new and near-tight Ramsey-type result for binary trees.

A cylinder graph is the graph Cartesian product of a path and a cycle. In this paper we investigate the length of a minimal spanning tree of a cylinder graph whose edges are assigned random lengths according to independent and uniformly distributed random variables. Our work was inspired by a formula of J. Michael Steele which shows that the expected length of a minimal spanning tree of a connected graph can be calculated through the Tutte polynomial of the graph. First, using transfer matrices, we show how to calculate the Tutte polynomials of cylinder graphs. Second, using Steele's formula, we tabulate the expected lengths of the minimal spanning trees for some cylinder graphs. Third, for a fixed cycle length, we show that the ratio of the expected length of a minimal spanning tree of a cylinder graph to the length of the cylinder graph converges to a constant; this constant is described in terms of the Perron–Frobenius eigenvalue of the accompanying transfer matrix. Finally, we show that the length of a minimal spanning tree of a cylinder graph satisfies a strong law of large numbers.

Let $P(G,t)$ and $F(G,t)$ denote the chromatic and flow polynomials of a graph $G$. G. D. Birkhoff and D C. Lewis showed that, if $G$ is a plane near-triangulation, then the only zeros of $P(G,t)$ in $(-\infty,2]$ are 0, 1 and 2. We will extend their theorem by showing that a stronger result to the dual statement holds for both planar and non-planar graphs: if $G$ is a bridge graph with at most one vertex of degree other than three, then the only zeros of $F(G,t)$ in $(-\infty,\alpha]$ are 1 and 2, where $\alpha\approx 2.225\cdots$ is the real zero in $(2,3)$ of the polynomial $t^4-8t^3+22t^2-28t+17$. In addition we construct a sequence of ‘near-cubic’ graphs whose flow polynomials have zeros converging to $\alpha$ from above.

We study a dynamically evolving random graph which adds vertices and edges using preferential attachment and is ‘attacked by an adversary’. At time t, we add a new vertex xt and m random edges incident with xt, where m is constant. The neighbours of xt are chosen with probability proportional to degree. After adding the edges, the adversary is allowed to delete vertices. The only constraint on the adversarial deletions is that the total number of vertices deleted by time n must be no larger than δn, where δ is a constant. We show that if δ is sufficiently small and m is sufficiently large then with high probability at time n the generated graph has a component of size at least n/30.

Consider the set of finite words on a totally ordered alphabet with two letters. We prove that the distribution of the length of the standard right factor of a random Lyndon word with length n, divided by n, converges to when n goes to infinity. The convergence of all moments follows. This paper thus completes the results of [2], in which the limit of the first moment is given.

We show that a random graph studied by Ioffe and Levit is an example of an inhomogeneous random graph of the type studied by Bollobás, Janson and Riordan, which enables us to give a new, and perhaps more revealing, proof of their result on a phase transition.

We consider the distribution of the value of the optimal k-assignment in an m × n matrix, where the entries are independent exponential random variables with arbitrary rates. We give closed formulas for both the Laplace transform of this random variable and for its expected value under the condition that there is a zero-cost (k − 1)-assignment.

We investigate the Laplacian eigenvalues of sparse random graphs Gnp. We show that in the case that the expected degree d = (n-1)p is bounded, the spectral gap of the normalized Laplacian is o(1). Nonetheless, w.h.p. G = Gnp has a large subgraph core(G) such that the spectral gap of is as large as 1-O (d−1/2). We derive similar results regarding the spectrum of the combinatorial Laplacian L(Gnp). The present paper complements the work of Chung, Lu and Vu [8] on the Laplacian spectra of random graphs with given expected degree sequences. Applied to Gnp, their results imply that in the ‘dense’ case d ≥ ln2n the spectral gap of is 1-O (d−1/2) w.h.p.

The vertex-nullity interlace polynomial of a graph, described by Arratia, Bollobás and Sorkin in [3] as evolving from questions of DNA sequencing, and extended to a two-variable interlace polynomial by the same authors in [5], evokes many open questions. These include relations between the interlace polynomial and the Tutte polynomial and the computational complexity of the vertex-nullity interlace polynomial. Here, using the medial graph of a planar graph, we relate the one-variable vertex-nullity interlace polynomial to the classical Tutte polynomial when x=y, and conclude that, like the Tutte polynomial, it is in general #P-hard to compute. We also show a relation between the two-variable interlace polynomial and the topological Tutte polynomial of Bollobás and Riordan in [13].

We define the γ invariant as the coefficient of x1 in the vertex-nullity interlace polynomial, analogously to the β invariant, which is the coefficientof x1 in the Tutte polynomial. We then turn to distance hereditary graphs, characterized by Bandelt and Mulder in [9] as being constructed by a sequence ofadding pendant and twin vertices, and show that graphs in this class have γ invariant of 2n+1 when n true twins are added intheir construction. We furthermore show that bipartite distance hereditary graphs are exactly the class of graphs with γ invariant 2, just as the series-parallel graphs are exactly the class of graphs with β invariant 1. In addition, we show that a bipartite distance hereditary graph arises precisely as the circle graph of an Euler circuitin the oriented medial graph of a series-parallel graph. From this we conclude that the vertex-nullity interlace polynomial is polynomial time to compute for bipartite distancehereditary graphs, just as the Tutte polynomial is polynomial time to compute for series-parallel graphs.

The strong isometric dimension of a graph G is the least number k such that G isometrically embeds into the strong product of k paths. Using Sperner's theorem, the strong isometric dimension of the Hamming graphs K2 □ Kn is determined.

We study a point process describing the asymptotic behaviour of sizes of the largest components of the random graph G(n, p) in the critical window, that is, for p = n−1 + λn−4/3, where λ is a fixed real number. In particular, we show that this point process has a surprising rigidity. Fluctuations in the large values will be balanced by opposite fluctuations in the small values such that the sum of the values larger than a small ϵ (a scaled version of the number of vertices in components of size greater than εn2/3) is almost constant.

For a fixed graph $H$, we define the rainbow Turán number $\ex^*(n,H)$ to be the maximum number of edges in a graph on $n$ vertices that has a proper edge-colouring with no rainbow $H$. Recall that the (ordinary) Turán number $\ex(n,H)$ is the maximum number of edges in a graph on $n$ vertices that does not contain a copy of $H$. For any non-bipartite $H$ we show that $\ex^*(n,H)=(1+o(1))\ex(n,H)$, and if $H$ is colour-critical we show that $\ex^{*}(n,H)=\ex(n,H)$. When $H$ is the complete bipartite graph $K_{s,t}$ with $s \leq t$ we show $\ex^*(n,K_{s,t}) = O(n^{2-1/s})$, which matches the known bounds for $\ex(n,K_{s,t})$ up to a constant. We also study the rainbow Turán problem for even cycles, and in particular prove the bound $\ex^*(n,C_6) = O(n^{4/3})$, which is of the correct order of magnitude.