Scaled Gromov hyperbolic graphs

In this article, the δ‐hyperbolic concept, originally developed for infinite graphs, is adapted to very large but finite graphs. Such graphs can indeed exhibit properties typical of negatively curved spaces, yet the traditional δ‐hyperbolic concept, which requires existence of an upper bound on the fatness δ of the geodesic triangles, is unable to capture those properties, as any finite graph has finite δ. Here the idea is to scale δ relative to the diameter of the geodesic triangles and use the Cartan–Alexandrov–Toponogov (CAT) theory to derive the thresholding value of δdiam below which the geometry has negative curvature properties. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 157–180, 2008     

Gromov hyperbolic cubic graphs

If X is a geodesic metric space and x ₁; x ₂; x ₃ ∈ X, a geodesic triangle T = {x ₁; x ₂; x ₃} is the union of the three geodesics [x ₁ x ₂], [x ₂ x ₃] and [x ₃ x ₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if any side of T is contained in a δ-neighborhood of the union of the two other sides, for every geodesic triangle T in X. We denote by δ(X) the sharp hyperbolicity constant of X, i.e., δ(X) = inf {δ ≥ 0: X is δ-hyperbolic}. We obtain information about the hyperbolicity constant of cubic graphs (graphs with all of their vertices of degree 3), and prove that for any graph G with bounded degree there exists a cubic graph G* such that G is hyperbolic if and only if G* is hyperbolic. Moreover, we prove that for any cubic graph G with n vertices, we have δ(G) ≤ min {3n/16 + 1; n/4}. We characterize the cubic graphs G with δ(G) ≤ 1. Besides, we prove some inequalities involving the hyperbolicity constant and other parameters for cubic graphs.     

Spanning trees in hyperbolic graphs

We construct spanning trees in locally finite hyperbolic graphs that represent their hyperbolic compactification in a good way: so that the tree has at least one but at most a bounded number of disjoint rays to each boundary point. As a corollary we extend a result of Gromov which says that from every hyperbolic graph with bounded degrees one can construct a tree (disjoint from the graph) with a continuous surjection from the ends of the tree onto the hyperbolic boundary such that the surjection is finite-to-one. We shall construct a tree with these properties as a subgraph of the hyperbolic graph, which in addition is also a spanning tree of that graph.     

Asymptotic connectivity of hyperbolic planar graphs

We investigate further the concept of asymptotic connectivity as defined previously by the first author. In particular, we prove the existence of, and compute an upper bound for, the asymptotic connectivity of almost any regular hyperbolic tiling of the plane. Our results indicate fundamental differences between hyperbolic (in the sense of Gromov) and non-hyperbolic graphs.     

Characterization of Gromov hyperbolic short graphs

To decide when a graph is Gromov hyperbolic is,in general,a very hard problem.In this paper,we solve this problem for the set of short graphs(in an informal way,a graph G is r-short if the shortcuts in the cycles of G have length less than r):an r-short graph G is hyperbolic if and only if S9r(G)is finite,where SR(G):=sup{L(C):C is an R-isometric cycle in G}and we say that a cycle C is R-isometric if dC(x,y)≤dG(x,y)+R for every x,y∈C.     

Approximation of pathwidth of outerplanar graphs

There exists a polynomial time algorithm to compute the pathwidth of outerplanar graphs, but the large exponent makes this algorithm impractical. In this paper, we give an algorithm that, given a biconnected outerplanar graph G, finds a path decomposition of G of pathwidth at most twice the pathwidth of G plus one. To obtain the result, several relations between the pathwidth of a biconnected outerplanar graph and its dual are established.     

Approximation in area of continuous graphs

Summary We prove that graphs of continuous maps with finite area can be approximated weakly as currents and in area by graphs of smooth maps.This article was processed by the author using the style filepljour1m from Springer-Verlag.     

Glauber dynamics on trees and hyperbolic graphs

We study continuous time Glauber dynamics for random configurations with local constraints (e.g. proper coloring, Ising and Potts models) on finite graphs with n vertices and of bounded degree. We show that the relaxation time (defined as the reciprocal of the spectral gap |₁–₂|) for the dynamics on trees and on planar hyperbolic graphs, is polynomial in n. For these hyperbolic graphs, this yields a general polynomial sampling algorithm for random configurations. We then show that for general graphs, if the relaxation time ₂ satisfies ₂=O(1), then the correlation coefficient, and the mutual information, between any local function (which depends only on the configuration in a fixed window) and the boundary conditions, decays exponentially in the distance between the window and the boundary. For the Ising model on a regular tree, this condition is sharp.Research supported by Microsoft graduate fellowship.Supported by a visiting position at INRIA and a PostDoc at Microsoft research.Research supported by NSF Grants DMS-0104073, CCR-0121555 and a Miller Professorship at UC Berkeley.Acknowledgement We are grateful to David Aldous, David Levin, Laurent Saloff-Coste and Peter Winkler for useful discussions. We thank Dror Weitz for helpful comments on [19].     

On fixing boundary points of transitive hyperbolic graphs

We show that there is no one-ended, locally finite, planar, hyperbolic graph such that the stabilizer of one of its hyperbolic boundary points acts transitively on the vertices of the graph. This gives a partial answer to a question by Kaimanovich and Woess.     

The fine structure of octahedron-free graphs

This paper is one of a series of papers in which, for a family L of graphs, we describe the typical structure of graphs not containing any L∈L. In this paper, we prove sharp results about the case L={O₆}, where O₆ is the graph with 6 vertices and 12 edges, given by the edges of an octahedron. Among others, we prove the following results.(a) The vertex set of almost every O₆-free graph can be partitioned into two classes of almost equal sizes, U₁ and U₂, where the graph spanned by U₁ is a C₄-free and that by U₂ is P₃-free.(b) Similar assertions hold when L is the family of all graphs with 6 vertices and 12 edges.(c) If H is a graph with a color-critical edge and χ(H)=p+1, then almost every sH-free graph becomes p-chromatic after the deletion of some s−1 vertices, where sH is the graph formed by s vertex disjoint copies of H.These results are natural extensions of theorems of classical extremal graph theory. To show that results like those above do not hold in great generality, we provide examples for which the analogs of our results do not hold.     

Approximation of periodic solutions for a dissipative hyperbolic equation

This paper studies the numerical approximation of periodic solutions for an exponentially stable linear hyperbolic equation in the presence of a periodic external force $f$ . These approximations are obtained by combining a fixed point algorithm with the Galerkin method. It is known that the energy of the usual discrete models does not decay uniformly with respect to the mesh size. Our aim is to analyze this phenomenon’s consequences on the convergence of the approximation method and its error estimates. We prove that, under appropriate regularity assumptions on $f$ , the approximation method is always convergent. However, our error estimates show that the convergence’s properties are improved if a numerically vanishing viscosity is added to the system. The same is true if the nonhomogeneous term $f$ is monochromatic. To illustrate our theoretical results we present several numerical simulations with finite element approximations of the wave equation in one or two dimensional domains and with different forcing terms.     

Cyclically symmetric hyperbolic spatial graphs in 3-manifolds

The aims of this paper is to prove that every closed connected orientable 3-manifold with an orientation-preserving periodic diffeomorphism contains infinitely many, setwise invariant, spatial graphs whose exteriors are hyperbolic 3-manifolds.     

Existence of constant mean curvature graphs in hyperbolic space

We give an existence result for constant mean curvature graphs in hyperbolic space . Let be a compact domain of a horosphere in whose boundary is mean convex, that is, its mean curvature (as a submanifold of the horosphere) is positive with respect to the inner orientation. If H is a number such that , then there exists a graph over with constant mean curvature H and boundary . Umbilical examples, when is a sphere, show that our hypothesis on H is the best possible. Received July 18, 1997 / Accepted April 24, 1998     

Existence of prescribed mean curvature graphs in hyperbolic space

In this paper we are concerned with questions of existence and uniqueness of graph-like prescribed mean curvature hypersurfaces in hyperbolic space ?ⁿ⁺¹. In the half-space setting, we will study radial graphs over the totally geodesic hypersurface . We prove the following existence result: Let be a bounded domain of class and let . If everywhere on , where denotes the hyperbolic mean curvature of the cylinder over , then for every there is a unique graph over with mean curvature attaining the boundary values on . Further we show the existence of smooth boundary data such that no solution exists in case of for some under the assumption that has a sign.     

Approximation in area of graphs with isolated singularities

It is shown that graphs with finite mass of mappings which are smooth except for isolated points, where they are continuous, can be approximated in area by graphs of smooth maps. The continuity hypothesis is then removed if the dimension n is strictly larger than the codimension N or if the dimension n is at least 3.     

Refined asymptotics for minimal graphs in the hyperbolic space

We study the boundary behaviors of solutions f to the Dirichlet problem for minimal graphs in the hyperbolic space with singular asymptotic boundaries and characterize the boundary behaviors of f at the points strictly located in the tangent cones at the singular points on the boundary. For n =2, we also obtain a refined estimate of f.     

List-edge and list-total colorings of graphs embedded on hyperbolic surfaces

In the paper, we prove that if G is a graph embeddable on a surface of Euler characteristic ε<0 and , then and . This extends a result of Borodin, Kostochka and Woodall [O.V. Borodin, A.V. Kostochka, D.R. Woodall, List-edge and list-total colorings of multigraphs, J. Comb. Theory Series B 71 (1997) 184-204].     

FRACTAL PROPERTIES OF HYPERBOLIC CURVES

In this paper, we study the fractal properties of the hyperbolic curve introduced by J. Belair ([Be]). We obtain some conditions of nowhere-differentiability of this kind of curves and its Bouligand dimension, and find a class of curves which are almost everywhere differertiable and have Bouligand dimensions being greater than one simultaneously.