We continue the study of random lifts of graphs initiated in [4]. Here we study the possibility of generating graphs with high edge expansion as random lifts. Along the way, we introduce the method of $\epsilon$-nets into the study of random structures. This enables us to improve (slightly) the known bounds for the edge expansion of regular graphs.

We show how to generate labelled and unlabelled outerplanar graphs with $n$ vertices uniformly at random in polynomial time in $n$. To generate labelled outerplanar graphs, we present a counting technique using the decomposition of a graph according to its block structure, and compute the exact number of labelled outerplanar graphs. This allows us to make the correct probabilistic choices in a recursive generation of uniformly distributed outerplanar graphs.

Next we modify our formulas to also count rooted unlabelled graphs, and finally show how to use these formulas in a Las Vegas algorithm to generate unlabelled outerplanar graphs uniformly at random in expected polynomial time.

The two-type Richardson model describes the growth of two competing infections on $\mathbb{Z}^d$. At time 0 two disjoint finite sets $\xi_1,\xi_2\subset \mathbb{Z}^d$ are infected with type 1 and type 2 infection respectively. An uninfected site then becomes type 1 (2) infected at a rate proportional to the number of type 1 (2) infected nearest neighbours and once infected it remains so forever. The main result in this paper is, loosely speaking, that the choice of the initial sets $\xi_1$ and $\xi_2$ is irrelevant in deciding whether or not the event of mutual unbounded growth for the two infection types has positive probability.

Let $\Gamma_{k,g}$ be the class of $k$-connected cubic graphs of girth at least $g$. For several choices of $k$ and $g$, we determine a set ${\cal O}_{k,g}$ of graph operations, for which, if $G$ and $H$ are graphs in $\Gamma_{k,g}$, $G\not\cong H$, and $G$ contains $H$ topologically, then some operation in ${\cal O}_{k,g}$ can be applied to $G$ to result in a smaller graph $G'$ in $\Gamma_{k,g}$ such that, on one hand, $G'$ is contained in $G$ topologically, and on the other hand, $G'$ contains $H$ topologically.

It is well known that counting $\lambda$-colourings ($\lambda\geq 3$) is #P-complete for general graphs, and also for several restricted classes such as bipartite planar graphs. On the other hand, it is known to be polynomial time computable for graphs of bounded tree-width. There is often special interest in counting colourings of square grids, and such graphs can be regarded as borderline graphs of unbounded tree-width in a specific sense. We are thus motivated to consider the complexity of counting colourings of subgraphs of the square grid. We show that the problem is #P-complete when $\lambda\geq 3$. It remains #P-complete when restricted to induced subgraphs with maximum degree 3.

We show that evaluating the Tutte polynomial for the class of bicircular matroids is #P-hard at every point $(x,y)$ except those in the hyperbola $(x-1)(y-1)=1$ and possibly those on the lines $x=0$ and $x=-1$. Since bicircular matroids form a rather restricted subclass of transversal matroids, our results can be seen as a partial strengthening of a result by Colbourn, Provan and Vertigan, namely that the evaluation of the Tutte polynomial for the class of transversal matroids is #P-hard for all points except those in the hyperbola $(x-1)(y-1)=1$.

It is a classical result of Jaeger, Vertigan and Welsh that evaluating the Tutte polynomial of a graph is #P-hard in all but a few special points. On the other hand, several papers in the past few years have shown that the Tutte polynomial of a graph can be efficiently computed for graphs of bounded tree-width. In this paper we present a recursive formula computing the Tutte polynomial of a matroid $M$ represented over a finite field (which includes all graphic matroids), using a so called parse tree of a branch-decomposition of $M$. This formula provides an algorithm computing the Tutte polynomial for a representable matroid of bounded branch-width in polynomial time with a fixed exponent.

Markov chain decomposition is a tool for analysing the convergence rate of a complicated Markov chain by studying its behaviour on smaller, more manageable pieces of the state space. Roughly speaking, if a Markov chain converges quickly to equilibrium when restricted to subsets of the state space, and if there is sufficient ergodic flow between the pieces, then the original Markov chain also must converge rapidly to equilibrium. We present a new version of the decomposition theorem where the pieces partition the state space, rather than forming a cover where pieces overlap, as was previously required. This new formulation is more natural and better suited to many applications. We apply this disjoint decomposition method to demonstrate the efficiency of simple Markov chains designed to uniformly sample circuits of a given length on certain Cayley graphs. The proofs further indicate that a Markov chain for sampling adsorbing staircase walks, a problem arising in statistical physics, is also rapidly mixing.

We consider the complexity of the two-variable rank generating function, $S$, of a graphic 2-polymatroid. For a graph $G$, $S$ is the generating function for the number of subsets of edges of $G$ having a particular size and incident with a particular number of vertices of $G$. We show that for any $x, y \in \mathbb{Q}$ with $xy \not =1$, it is #P-hard to evaluate $S$ at $(x,y)$. We also consider the $k$-thickening of a graph and computing $S$ for the $k$-thickening of a graph.

Let ${P_s(d)}$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let ${E(d)}$ be the expected number of 0/1-vectors in the linear subspace spanned by $d-1$ random independent 0/1-vectors. (So ${E(d)}$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.)

We prove that bounds on ${P_s(d)}$ are equivalent to bounds on ${E(d)}$: \[{P_s(d)} = \bigg(2^{-d} {E(d)} + \frac{d^2}{2^{d+1}} \bigg) (1 + \so(1)). \] We also report on computational experiments pertaining to these numbers.

Let $P=(X,\le)$ be a finite partially ordered set. That is, $X$ is a finite ground set and $\le$ is a partial ordering on $X$ (a reflexive, transitive, and weakly antisymmetric relation). An $x\in X$ is an immediate predecessor of a $y\in X$ if $x<y$ and there is no $z\in X$ with $x<z<y$ (where $x<y$ means that $x\le y$ and $x\ne y$). The Hasse diagram$H(P)$ is the undirected graph with vertex set $X$ and with $\{x,y\}$ forming an edge if $x$ is an immediate predecessor of $y$ or if $y$ is an immediate predecessor of $x$. We denote bya $\alpha(H(P))$ the independence number of the Hasse diagram, that is, the maximum possible size of a subset $I\subseteq X$ such that no element of $I$ is an immediate predecessor (in $P$) of another element of $I$. This quantity should not be confused with the maximum size of an antichain in $P$, which is sometimes denoted by $\alpha(P)$.