A full characterization of invariant embeddability of unimodular planar graphs

When can a unimodular random planar graph be drawn in the Euclidean or the hyperbolic plane in a way that the distribution of the random drawing is isometry-invariant? This question was answered for one-ended unimodular graphs in Benjamini and Timar, using the fact that such graphs automatically have locally finite (simply connected) drawings into the plane. For the case of graphs with multiple ends the question was left open. We revisit Halin's graph theoretic characterization of graphs that have a locally finite embedding into the plane. Then we prove that such unimodular random graphs do have a locally finite invariant embedding into the Euclidean or the hyperbolic plane, depending on whether the graph is amenable or not.     

The critical probability for Voronoi percolation in the hyperbolic plane tends to 1/2

We consider percolation on the Voronoi tessellation generated by a homogeneous Poisson point process on the hyperbolic plane. We show that the critical probability for the existence of an infinite cluster tends to 1/2 as the intensity of the Poisson process tends to infinity. This confirms a conjecture of Benjamini and Schramm [5].     

Geometry and spectrum of rapidly branching graphs

We study graphs whose vertex degree tends to infinity and which are, therefore, called rapidly branching. We prove spectral estimates, discreteness of spectrum, first order eigenvalue and Weyl asymptotics solely in terms of the vertex degree growth. The underlying techniques are estimates on the isoperimetric constant. Furthermore, we give lower volume growth bounds and we provide a new criterion for stochastic incompleteness.     

Anchored expansion and random walk

This paper studies anchored expansion, a non-uniform version of the strong isoperimetric inequality. We show that every graph with i-anchored expansion contains a subgraph with isoperimetric (Cheeger) constant at least i. We prove a conjecture by Benjamini, Lyons and Schramm (1999) that in such graphs the random walk escapes with a positive lim inf speed. We also show that anchored expansion implies a heat-kernel decay bound of order exp(—cn ^1/3). Submitted: September 1999, Revision: January 2000.     

Group-invariant Percolation on Graphs

Let G be a closed group of automorphisms of a graph X. We relate geometric properties of G and X, such as amenability and unimodularity, to properties of G-invariant percolation processes on X, such as the number of infinite components, the expected degree, and the topology of the components. Our fundamental tool is a new masstransport technique that has been occasionally used elsewhere and is developed further here.¶ Perhaps surprisingly, these investigations of group-invariant percolation produce results that are new in the Bernoulli setting. Most notably, we prove that critical Bernoulli percolation on any nonamenable Cayley graph has no infinite clusters. More generally, the same is true for any nonamenable graph with a unimodular transitive automorphism group.¶ We show that G is amenable if for all $ \alpha < 1 $ \alpha < 1 , there is a G-invariant site percolation process w \omega on X with $ {\bf P} [x \in \omega] > \alpha $ {\bf P} [x \in \omega] > \alpha for all vertices x and with no infinite components. When G is not amenable, a threshold $ \alpha < 1 $ \alpha < 1 appears. An inequality for the threshold in terms of the isoperimetric constant is obtained, extending an inequality of Häggström for regular trees.¶ If G acts transitively on X, we show that G is unimodular if the expected degree is at least 2 in any G-invariant bond percolation on X with all components infinite.¶ The investigation of dependent percolation also yields some results on automorphism groups of graphs that do not involve percolation.     

Isoperimetry in Two‐Dimensional Percolation

We study isoperimetric sets, i.e., sets with minimal boundary for a prescribed volume, on the unique infinite connected component of supercritical bond percolation on the square lattice. In the limit of the volume tending to infinity, properly scaled isoperimetric sets are shown to converge (in the Hausdorff metric) to the solution of an isoperimetric problem in ?² with respect to a particular norm. As part of the proof we also show that the anchored isoperimetric profile as well as the Cheeger constant of the giant component in finite boxes scale to deterministic quantities. This settles a conjecture of Itai Benjamini for the square lattice. © 2015 Wiley Periodicals, Inc.     

Lower bounds on the cover-index of a graph

In this paper we give some new lower bounds for the cover-index of graphs with multiple edges permitted. The results are analogous to upper bounds for the chromatic index. We show that a simple graph with cover-index different from the minimum degree has at least three vertices of minimum degree. This implies that almost all simple graphs have cover-index equal to the minimum degree.     

Graph drawings with few slopes

The slope-number of a graph G is the minimum number of distinct edge slopes in a straight-line drawing of G in the plane. We prove that for Δ5 and all large n, there is a Δ-regular n-vertex graph with slope-number at least . This is the best known lower bound on the slope-number of a graph with bounded degree. We prove upper and lower bounds on the slope-number of complete bipartite graphs. We prove a general upper bound on the slope-number of an arbitrary graph in terms of its bandwidth. It follows that the slope-number of interval graphs, cocomparability graphs, and AT-free graphs is at most a function of the maximum degree. We prove that graphs of bounded degree and bounded treewidth have slope-number at most . Finally we prove that every graph has a drawing with one bend per edge, in which the number of slopes is at most one more than the maximum degree. In a companion paper, planar drawings of graphs with few slopes are also considered.     

Drawings of planar graphs with few slopes and segments

We study straight-line drawings of planar graphs with few segments and few slopes. Optimal results are obtained for all trees. Tight bounds are obtained for outerplanar graphs, 2-trees, and planar 3-trees. We prove that every 3-connected plane graph on n vertices has a plane drawing with at most segments and at most 2n slopes. We prove that every cubic 3-connected plane graph has a plane drawing with three slopes (and three bends on the outerface). In a companion paper, drawings of non-planar graphs with few slopes are also considered.     

Percolation in the hyperbolic plane

We study percolation in the hyperbolic plane and on regular tilings in the hyperbolic plane. The processes discussed include Bernoulli site and bond percolation on planar hyperbolic graphs, invariant dependent percolations on such graphs, and Poisson-Voronoi-Bernoulli percolation. We prove the existence of three distinct nonempty phases for the Bernoulli processes. In the first phase, , there are no unbounded clusters, but there is a unique infinite cluster for the dual process. In the second phase, , there are infinitely many unbounded clusters for the process and for the dual process. In the third phase, , there is a unique unbounded cluster, and all the clusters of the dual process are bounded. We also study the dependence of in the Poisson-Voronoi-Bernoulli percolation process on the intensity of the underlying Poisson process.

     

Bond percolation on isoradial graphs: criticality and universality

In an investigation of percolation on isoradial graphs, we prove the criticality of canonical bond percolation on isoradial embeddings of planar graphs, thus extending celebrated earlier results for homogeneous and inhomogeneous square, triangular, and other lattices. This is achieved via the star–triangle transformation, by transporting the box-crossing property across the family of isoradial graphs. As a consequence, we obtain the universality of these models at the critical point, in the sense that the one-arm and $2j$ -alternating-arm critical exponents (and therefore also the connectivity and volume exponents) are constant across the family of such percolation processes. The isoradial graphs in question are those that satisfy certain weak conditions on their embedding and on their track system. This class of graphs includes, for example, isoradial embeddings of periodic graphs, and graphs derived from rhombic Penrose tilings.     

Transfer matrices, hyperbolic geometry and absolutely continuous spectrum for some discrete Schrödinger operators on graphs

We prove the existence of absolutely continuous spectrum for a class of discrete Schrödinger operators on tree like graphs. We consider potentials whose radial behaviour is subject only to an ?^∞ bound. In the transverse direction the potential must satisfy a condition such as periodicity. The graphs we consider include binary trees and graphs obtained from a binary tree by adding edges, possibly with weights. Our methods are motivated by the one-dimensional transfer matrix method, interpreted as a discrete dynamical system on the hyperbolic plane. This is extended to more general graphs, leading to a formula for the Green's function. Bounds on the Green's function then follow from the contraction properties of the transformations that arise in this generalization. The bounds imply the existence of absolutely continuous spectrum.     

Looseness of Plane Graphs

A face of a vertex coloured plane graph is called loose if the number of colours used on its vertices is at least three. The looseness of a plane graph G is the minimum k such that any surjective k-colouring involves a loose face. In this paper we prove that the looseness of a connected plane graph G equals the maximum number of vertex disjoint cycles in the dual graph G* increased by 2. We also show upper bounds on the looseness of graphs based on the number of vertices, the edge connectivity, and the girth of the dual graphs. These bounds improve the result of Negami for the looseness of plane triangulations. We also present infinite classes of graphs where the equalities are attained.     

Domination in bipartite graphs

We prove that the domination number of a graph of order n and minimum degree at least 2 that does not contain cycles of length 4, 5, 7, 10 or 13 is at most . Furthermore, we derive upper bounds on the domination number of bipartite graphs of given minimum degree.     

Eigenvalues and expansion of bipartite graphs

We prove lower bounds on the largest and second largest eigenvalue of the adjacency matrix of connected bipartite graphs and give necessary and sufficient conditions for equality. We give several examples of classes of graphs that are optimal with respect to the bounds. We prove that BIBD-graphs are characterized by their eigenvalues. Finally we present a new bound on the expansion coefficient of (c, d)-regular bipartite graphs and compare that with with a classical bound.     

The Dirichlet problem at infinity for random walks on graphs with a strong isoperimetric inequality

Summary We study the spatial behaviour of random walks on infinite graphs which are not necessarily invariant under some transitive group action and whose transition probabilities may have infinite range. We assume that the underlying graphG satisfies a strong isoperimetric inequality and that the transition operatorP is strongly reversible, uniformly irreducible and satisfies a uniform first moment condition. We prove that under these hypotheses the random walk converges almost surely to a random end ofG and that the Dirichlet problem forP-harmonic functions is solvable with respect to the end compactification If in addition the graph as a metric space is hyperbolic in the sense of Gromov, then the same conclusions also hold for the hyperbolic compactification in the place of the end compactification. The main tool is the exponential decay of the transition probabilities implied by the strong isoperimetric inequality. Finally, it is shown how the same technique can be applied to Brownian motion to obtain analogous results for Riemannian manifolds satisfying Cheeger's isoperimetric inequality. In particular, in this general context new (and simpler) proofs of well known results on the Dirichlet problem for negatively curved manifolds are obtained.The first author was partially supported by Consiglio Nazionale delle Ricerche, GNAFA Current address: Department of Mathematics, University of Edinburgh, Edinburgh EH9 3JZ, Scotland     

Isoperimetric control of the Steklov spectrum

We prove that the normalized Steklov eigenvalues of a bounded domain in a complete Riemannian manifold are bounded above in terms of the inverse of the isoperimetric ratio of the domain. Consequently, the normalized Steklov eigenvalues of a bounded domain in Euclidean space, hyperbolic space or a standard hemisphere are uniformly bounded above. On a compact surface with boundary, we obtain uniform bounds for the normalized Steklov eigenvalues in terms of the genus. We also establish a relationship between the Steklov eigenvalues of a domain and the eigenvalues of the Laplace-Beltrami operator on its boundary hypersurface.     

Lightness of digraphs in surfaces and directed game chromatic number

The lightness of a digraph is the minimum arc value, where the value of an arc is the maximum of the in-degrees of its terminal vertices. We determine upper bounds for the lightness of simple digraphs with minimum in-degree at least 1 (resp., graphs with minimum degree at least 2) and a given girth k, and without 4-cycles, which can be embedded in a surface S. (Graphs are considered as digraphs each arc having a parallel arc of opposite direction.) In case k≥5, these bounds are tight for surfaces of nonnegative Euler characteristics. This generalizes results of He et al. [W. He, X. Hou, K.-W. Lih, J. Shao, W. Wang, X. Zhu, Edge-partitions of planar graphs and their game coloring numbers, J. Graph Theory 41 (2002) 307-317] concerning the lightness of planar graphs. From these bounds we obtain directly new bounds for the game colouring number, and thus for the game chromatic number of (di)graphs with girth k and without 4-cycles embeddable in S. The game chromatic resp. game colouring number were introduced by Bodlaender [H.L. Bodlaender, On the complexity of some coloring games, Int. J. Found. Comput. Sci. 2 (1991) 133-147] resp. Zhu [X. Zhu, The game coloring number of planar graphs, J. Combin. Theory B 75 (1999) 245-258] for graphs. We generalize these notions to arbitrary digraphs. We prove that the game colouring number of a directed simple forest is at most 3.     

A Harris‐Kesten theorem for confetti percolation

Percolation properties of the dead leaves model, also known as confetti percolation, are considered. More precisely, we prove that the critical probability for confetti percolation with square‐shaped leaves is 1/2. This result is related to a question of Benjamini and Schramm concerning disk‐shaped leaves and can be seen as a variant of the Harris‐Kesten theorem for bond percolation. The proof is based on techniques developed by Bollobás and Riordan to determine the critical probability for Voronoi and Johnson‐Mehl percolation. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 361–385, 2015     

The vertex isoperimetric problem for the powers of the diamond graph

We introduce a new graph for all whose cartesian powers the vertex isoperimetric problem has nested solutions. This is the fourth kind of graphs with this property besides the well-studied graphs like hypercubes, grids, and tori. In contrast to the mentioned graphs, our graph is not bipartite. We present an exact solution to the vertex isoperimetric problem on our graph by introducing a new class of orders that unifies all known isoperimetric orders defined on the cartesian powers of graphs.