The dual Cheeger constant and spectra of infinite graphs

In this article we study the top of the spectrum of the normalized Laplace operator on infinite graphs. We introduce the dual Cheeger constant and show that it controls the top of the spectrum from above and below in a similar way as the Cheeger constant controls the bottom of the spectrum. Moreover, we show that the dual Cheeger constant at infinity can be used to characterize that the essential spectrum of the normalized Laplace operator shrinks to one point.     

On a weighted total variation minimization problem

The present article is devoted to the study of a constrained weighted total variation minimization problem, which may be viewed as a relaxation of a generalized Cheeger problem and is motivated by landslide modeling. Using the fact that the set of minimizers is invariant by a wide class of monotone transformations, we prove that level sets of minimizers are generalized Cheeger sets and obtain qualitative properties of the minimizers: they are all bounded and all achieve their essential supremum on a set of positive measure.     

Small 3-Manifolds of Large Genus

In this paper we prove the Cheeger inequality for infinite weighted graphs endowed with 'corresponding' measure. This measure has already been developed in the study of tree lattices. Our graphs have finite volumes. A similar theory has already been developed for manifolds of finite volumes.     

Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering

The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data. This is an NP-hard problem that can be relaxed in the spectral graph theory, where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian. In this paper, we first give new notations to describe the paths, among critical eigenvectors of the graph 1-Laplacian, realizing sets with prescribed genus. We introduce the pseudo-orthogonality to characterize m₃(G), a special eigenvalue for the graph 1-Laplacian. Furthermore, we use it to give an upper bound for the third graph Cheeger constant h₃(G), that is, h₃(G) 6 m₃(G). This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k - 1 Cheeger constants. Eventually, we apply these results to give a method and a numerical algorithm to compute m₃(G), based on a generalized inverse power method.     

Total variation and Cheeger sets in Gauss space

The aim of this paper is to study the isoperimetric problem with fixed volume inside convex sets and other related geometric variational problems in the Gauss space, in both the finite and infinite dimensional case. We first study the finite dimensional case, proving the existence of a maximal Cheeger set which is convex inside any bounded convex set. We also prove the uniqueness and convexity of solutions of the isoperimetric problem with fixed volume inside any convex set. Then we extend these results in the context of the abstract Wiener space, and for that we study the total variation denoising problem in this context.     

The 1-Laplacian Cheeger Cut: Theory and Algorithms

This paper presents a detailed review of both theory and algorithms for the Cheeger cut based on the graph 1-Laplacian. In virtue of the cell structure of the feasible set, we propose a cell descend (CD) framework for achieving the Cheeger cut. While plugging the relaxation to guarantee the decrease of the objective value in the feasible set, from which both the inverse power (IP) method and the steepest descent (SD) method can also be recovered, we are able to get two specified CD methods. Comparisons of all these methods are conducted on several typical graphs.     

Isoperimetric estimates in products

In a product M ₁ × M ₂ of Riemannian manifolds, the least perimeter required to enclose given volume among general regions is at least 1/√ 2 times that among regions of product form, assuming that the isoperimetric profiles of M ₁ and M ₂ are concave. This result sharpens earlier work of Grigor'yan, generalizes results of Bollobás and Leader and of Barthe, and yields a lower bound on the Cheeger isoperimetric constant of a product.     

Solutions of the Cheeger problem via torsion functions

The Cheeger problem for a bounded domain Ω⊂RN, N>1 consists in minimizing the quotients |∂E|/|E| among all smooth subdomains E⊂Ω and the Cheeger constant h(Ω) is the minimum of these quotients. Let be the p-torsion function, that is, the solution of torsional creep problem −Δp?p=1 in Ω, ?p=0 on ∂Ω, where Δpu:=div(|∇u|^p−2∇u) is the p-Laplacian operator, p>1. The paper emphasizes the connection between these problems. We prove that . Moreover, we deduce the relation limp→¹⁺‖?p_‖L¹(Ω)?CNlimp→¹⁺‖?p_‖L^∞(Ω) where CN is a constant depending only of N and h(Ω), explicitely given in the paper. An eigenfunction u∈BV(Ω)∩L^∞(Ω) of the Dirichlet 1-Laplacian is obtained as the strong L¹ limit, as p→¹⁺, of a subsequence of the family {?p/‖?p_‖L¹(Ω)}_p>1. Almost all t-level sets Et of u are Cheeger sets and our estimates of u on the Cheeger set |E₀| yield |B₁|hN(B₁)?|E₀|hN(Ω), where B₁ is the unit ball in RN. For Ω convex we obtain u=|E₀|⁻¹χE₀.     

Some compactness theorems via m-Bakry–Émery and m-modified Ricci curvatures with negative m

Stimulated by S. Ohta and W. Wylie, we establish some compactness theorems for complete Riemannian manifolds via m-Bakry–Émery and m-modified Ricci curvatures with negative m. Our results may be considered as generalizations of the classical compactness theorems via Ricci curvature due to S.B. Myers, W. Ambrose, G.J. Galloway, and J. Cheeger, M. Gromov, and M. Taylor, and relax some previous compactness criteria for complete Riemannian manifolds via m-Bakry–Émery and m-modified Ricci curvatures obtained when m is a positive constant or infinity.     

Random walks and local cuts in graphs

For a specified subset S of vertices in a graph G we consider local cuts that separate a subset of S. We consider the local Cheeger constant which is the minimum Cheeger ratio over all subsets of S, and we examine the relationship between the local Cheeger constant and the Dirichlet eigenvalue of the induced subgraph on S. These relationships are summarized in a local Cheeger inequality. The proofs are based on the methods of establishing isoperimetric inequalities using random walks and the spectral methods for eigenvalues with Dirichlet boundary conditions.     

Laplacians and the Cheeger Inequality for Directed Graphs

We consider Laplacians for directed graphs and examine their eigenvalues. We introduce a notion of a circulation in a directed graph and its connection with the Rayleigh quotient. We then define a Cheeger constant and establish the Cheeger inequality for directed graphs. These relations can be used to deal with various problems that often arise in the study of non-reversible Markov chains including bounding the rate of convergence and deriving comparison theorems.Received September 8, 2004     

Cheeger–Chern–Simons Theory and Differential String Classes

We construct new concrete examples of relative differential characters, which we call Cheeger–Chern–Simons characters. They combine the well-known Cheeger–Simons characters with Chern–Simons forms. In the same way as Cheeger–Simons characters generalize Chern–Simons invariants of oriented closed manifolds, Cheeger–Chern–Simons characters generalize Chern–Simons invariants of oriented manifolds with boundary. We study the differential cohomology of compact Lie groups G and their classifying spaces BG. We show that the even degree differential cohomology of BG canonically splits into Cheeger–Simons characters and topologically trivial characters. We discuss the transgression in principal G-bundles and in the universal bundle. We introduce two methods to lift the universal transgression to a differential cohomology valued map. They generalize the Dijkgraaf–Witten correspondence between 3-dimensional Chern–Simons theories and Wess–Zumino–Witten terms to fully extended higher-order Chern–Simons theories. Using these lifts, we also prove two versions of a differential Hopf theorem. Using Cheeger–Chern–Simons characters and transgression, we introduce the notion of differential trivializations of universal characteristic classes. It generalizes well-established notions of differential String classes to arbitrary degree. Specializing to the class \({\frac{1}{2} p_1 \in H^4(B{\rm Spin}_n;\mathbb{Z})}\), we recover isomorphism classes of geometric string structures on Spin _n -bundles with connection and the corresponding spin structures on the free loop space. The Cheeger–Chern–Simons character associated with the class \({\frac{1}{2} p_1}\) together with its transgressions to loop space and higher mapping spaces defines a Chern–Simons theory, extended down to points. Differential String classes provide trivializations of this extended Chern–Simons theory. This setting immediately generalizes to arbitrary degree: for any universal characteristic class of principal G-bundles, we have an associated Cheeger–Chern–Simons character and extended Chern–Simons theory. Differential trivialization classes yield trivializations of this extended Chern–Simons theory.     

Cheeger Type Sobolev Spaces for Metric Space Targets

In this paper, we consider the natural generalization of Cheeger type Sobolev spaces to maps into a metric space. We solve Dirichlet problem for CAT(0)-space targets, and obtain some results about the relation between Cheeger type Sobolev spaces for maps into a Banach space and those for maps into a subset of that Banach space. We also prove the minimality of upper pointwise Lipschitz constant functions for locally Lipschitz maps into an Alexandrov space of curvature bounded above.     

Differential Characters and Multiplicative Cohomology

We compare the groups of differential characters of Cheeger and Simons to Karoobi's multiplicative cohomology.     

Spectral gap,isoperimetry and concentration on trees

We consider the nearest-neighbor model on the finite tree T with generator L. We obtain a twosided estimate of the spectral gap by factor 2. We also identify explicitly the Lipschitzian norm of the operator(-L)~(-1) in propriate functional space. This leads to the identification of the best constant in the generalized Cheeger isoperimetric inequality on the tree, and to transportation-information inequalities.     

The Cheeger constant of curved tubes

We compute the Cheeger constant of tubular neighbourhoods of complete curves in an arbitrary dimensional Euclidean space and raise a question about curved spherical shells.     

An extension of Bonnet–Myers theorem

We give a complementary generalization of the extensions of Bonnet–Myers theorem obtained by Calabi and also Cheeger–Gromov–Taylor.

     

Uniqueness of Locally Symmetric Brownian Motion on Laakso Spaces

We consider the spaces introduced by Laakso in 2000 and, building on the work of Barlow, Bass, Kumagai, and Teplyaev, prove the existence and uniqueness of a local symmetry invariant diffusion via heat kernel estimates. This work also builds upon works of Cheeger, Barlow and Bass, as well as the author.     

Logarithmic Sobolev,isoperimetry and transport inequalities on graphs

In this paper,we study some functional inequalities(such as Poincaré inequality,logarithmic Sobolev inequality,generalized Cheeger isoperimetric inequality,transportation-information inequality and transportation-entropy inequality) for reversible nearest-neighbor Markov processes on connected finite graphs by means of(random) path method.We provide estimates of the involved constants.