We prove that any Cayley graph $G$ with degree $d$ polynomial growth does not satisfy ${f(n)}$-containment for any $f=o(n^{d-2})$. This settles the asymptotic behaviour of the firefighter problem on such graphs as it was known that $Cn^{d-2}$ firefig
hters are enough, answering and strengthening a conjecture of Develin and Hartke. We also prove that intermediate growth Cayley graphs do not satisfy polynomial containment, and give explicit lower bounds depending on the growth rate of the group. These bounds can be further improved when more geometric information is available, such as for Grigorchuks group.
We show that for a fixed k, Gromov random groups with any positive density have no non-trivial degree-k representations over any field, a.a.s. This is especially interesting in light of the results of Agol, Ollivier and Wise that when the density is
less than 1/6 such groups have a faithful linear representation over the rationals, a.a.s.
We prove that all groups of exponential growth support non-constant positive harmonic functions. In fact, out results hold in the more general case of strongly connected, finitely supported Markov chains invariant under some transitive group of autom
orphisms for which the directed balls grow exponentially.
We study bond percolation on the square lattice with one-dimensional inhomogeneities. Inhomogeneities are introduced in the following way: A vertical column on the square lattice is the set of vertical edges that project to the same vertex on $mathbb
{Z}$. Select vertical columns at random independently with a given positive probability. Keep (respectively remove) vertical edges in the selected columns, with probability $p$, (respectively $1-p$). All horizontal edges and vertical edges lying in unselected columns are kept (respectively removed) with probability $q$, (respectively $1-q$). We show that, if $p > p_c(mathbb{Z}^2)$ (the critical point for homogeneous Bernoulli bond percolation) then $q$ can be taken strictly smaller then $p_c(mathbb{Z}^2)$ in such a way that the probability that the origin percolates is still positive.
We study a natural discrete Bochner-type inequality on graphs, and explore its merit as a notion of curvature in discrete spaces. An appealing feature of this discrete version seems to be that it is fairly straightforward to compute this notion of cu
rvature parameter for several specific graphs of interest - particularly, abelian groups, slices of the hypercube, and the symmetric group under various sets of generators. We further develop this notion by deriving Buser-type inequalities (a la Ledoux), relating functional and isoperimetric constants associated with a graph. Our derivations provide a tight bound on the Cheeger constant (i.e., the edge-isoperimetric constant) in terms of the spectral gap, for graphs with nonnegative curvature, particularly, the class of abelian Cayley graphs - a result of independent interest.
