An official website of the United States government
Abstract We study the volume growth of metric balls as a function of the radius in discrete spaces and focus on the relationship between volume growth and discrete curvature. We improve volume growth bounds under a lower bound on the so-called Ollivier curvature and discuss similar results under other types of discrete Ricci curvature. Following recent work in the continuous setting of Riemannian manifolds (by the 1st author), we then bound the eigenvalues of the Laplacian of a graph under bounds on the volume growth. In particular, $$\lambda _2$$ of the graph can be bounded using a weighted discrete Hardy inequality and the higher eigenvalues of the graph can be bounded by the eigenvalues of a tridiagonal matrix times a multiplicative factor, both of which only depend on the volume growth of the graph. As a direct application, we relate the eigenvalues to the Cheeger isoperimetric constant. Using these methods, we describe classes of graphs for which the Cheeger inequality is tight on the 2nd eigenvalue (i.e. the 1st nonzero eigenvalue). We also describe a method for proving Buser’s Inequality in graphs, particularly under a lower bound assumption on curvature.
more »
« less
Systolic inequalities for the number of vertices
Inspired by the classical Riemannian systolic inequality of Gromov, we present a combinatorial analogue providing a lower bound on the number of vertices of a simplicial complex in terms of its edge-path systole. Similarly to the Riemannian case, where the inequality holds under a topological assumption of “essentiality”, our proofs rely on a combinatorial analogue of that assumption. Under a stronger assumption, expressed in terms of cohomology cup-length, we improve our results quantitatively. We also illustrate our methods in the continuous setting, generalizing and improving quantitatively the Minkowski principle of Balacheff and Karam; a corollary of this result is the extension of the Guth–Nakamura cup-length systolic bound from manifolds to complexes.
more »
« less
- Award ID(s):
- 1926686
- PAR ID:
- 10447681
- Date Published:
- Journal Name:
- Journal of Topology and Analysis
- ISSN:
- 1793-5253
- Page Range / eLocation ID:
- 1 to 23
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We study the universality of superconcentration for the free energy in the Sherrington–Kirkpatrick model. In [10], Chatterjee showed that when the system consists of spins and Gaussian disorders, the variance of this quantity is superconcentrated by establishing an upper bound of order , in contrast to the bound obtained from the Gaussian–Poincaré inequality. In this paper, we show that superconcentration indeed holds for any choice of centered disorders with finite third moment, where the upper bound is expressed in terms of an auxiliary nondecreasing function that arises in the representation of the disorder as for standard normal. Under an additional regularity assumption on , we further show that the variance is of order at most .more » « less
-
Abstract Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations $Ax = b$ , where the coordinates of the vector x are restricted to take values in some small subset (e.g. $$\{\pm 1\}$$ ) of the underlying field. The classical ways of bounding this quantity are to use either a rank bound observation due to Odlyzko or a vector anti-concentration inequality due to Halász. The former gives a stronger conclusion except when the number of equations is significantly smaller than the number of variables; even in such situations, the hypotheses of Halász’s inequality are quite hard to verify in practice. In this paper, using a novel approach to the anti-concentration problem for vector sums, we obtain new Halász-type inequalities that beat the Odlyzko bound even in settings where the number of equations is comparable to the number of variables. In addition to being stronger, our inequalities have hypotheses that are considerably easier to verify. We present two applications of our inequalities to combinatorial (random) matrix theory: (i) we obtain the first non-trivial upper bound on the number of $$n\times n$$ Hadamard matrices and (ii) we improve a recent bound of Deneanu and Vu on the probability of normality of a random $$\{\pm 1\}$$ matrix.more » « less
-
We consider finite $$2$$ -complexes $$X$$ that arise as quotients of Fuchsian buildings by subgroups of the combinatorial automorphism group, which we assume act freely and cocompactly. We show that locally CAT( $-1$ ) metrics on $$X$$ , which are piecewise hyperbolic and satisfy a natural non-singularity condition at vertices, are marked length spectrum rigid within certain classes of negatively curved, piecewise Riemannian metrics on $$X$$ . As a key step in our proof, we show that the marked length spectrum function for such metrics determines the volume of $$X$$ .more » « less
-
Following ideas of Caffarelli and Silvestre in [20], and using recent progress in hyperbolic fillings, we define fractional p-Laplacians (−∆p)θ with 0 < θ < 1 on any compact, doubling metric measure space (Z, d, ν), and prove existence, regularity and stability for the non- homogenous non-local equation (−∆p)θu = f. These results, in turn, rest on the new existence, global Hölder regularity and stability theorems that we prove for the Neumann problem for p-Laplacians ∆p, 1 < p < ∞, in bounded domains of measure metric spaces endowed with a doubling measure that supports a Poincaré inequality. Our work also includes as special cases much of the previous results by other authors in the Euclidean, Riemannian and Carnot group settings. Unlike other recent contributions in the metric measure spaces context, our work does not rely on the assumption that (Z, d, ν) supports a Poincaré inequality.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1142/S179352532350005X
