Harnack and mean value inequalities on graphs

We prove a Harnack inequality for positive harmonic functions on graphs which is similar to a classical result of Yau on Riemannian manifolds. Also, we prove a mean value inequality of nonnegative subharmonic functions on graphs.     

阿贝尔齐性图上一种改进的关于Dirichlet特征值的Harnack型不等式

在本文中, 我们证明了在阿贝尔齐性图上一种改进的关于Dirichlet特征值的Harnack 型不等式,由此, 利用此Harnack 型不等式得到Dirichlet特征值的一个下界估计, 推广了 Chung 和 Yau 关于齐性图的一些结果.     

Some Inequalities for Superharmonic Functions on Graphs

An inequality for superharmonic functions on Riemannian manifolds due to S.Y. Cheng and S-T. Yau is adapted to the setting of graphs. A number of corollaries are discussed, including a Harnack inequality for graphs having at most quadratic growth and satisfying a certain connectedness condition.     

Kato’s inequality and Liouville theorems on locally finite graphs

In this paper, we study the Kato’s inequality on locally finite graphs. We also study the application of Kato’s inequality to Ginzburg-Landau equations on such graphs. Interesting properties of elliptic and parabolic equations on the graphs and a Liouville type theorem are also derived.     

Graphs satisfying inequality θ(G)θ(G)

In this paper, we study the edge clique cover number of squares of graphs. More specifically, we study the inequality θ(G²)θ(G) where θ(G) is the edge clique cover number of a graph G. We show that any graph G with at most θ(G) vertices satisfies the inequality. Among the graphs with more than θ(G) vertices, we find some graphs violating the inequality and show that dually chordal graphs and power-chordal graphs satisfy the inequality. Especially, we give an exact formula computing θ(T²) for a tree T.     

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.     

图上曲率维数不等式的若干等价性质

本文研究局部有限图上的曲率维数不等式CD(n,K)的若干等价性质,包括梯度估计、Poincaré不等式和逆Poincaré不等式.还得到了局部有限图上的修正曲率维数不等式CDE′(∞,K)的其中一个等价性质,即梯度估计.     

Harnack inequalities for graphs with non-negative Ricci curvature

We establish a Harnack inequality for finite connected graphs with non-negative Ricci curvature. As a consequence, we derive an eigenvalue lower bound, extending previous results for Ricci flat graphs.     

Some results on resistance distances and resistance matrices

In this paper, we obtain formulas for resistance distances and Kirchhoff index of subdivision graphs. An application of resistance distances to the bipartiteness of graphs is given. We also give an interlacing inequality for eigenvalues of the resistance matrix and the Laplacian matrix.     

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.     

Random graphons and a weak Positivstellensatz for graphs

In an earlier article, the authors proved that limits of convergent graph sequences can be described by various structures, including certain 2‐variable real functions called graphons, random graph models satisfying certain consistency conditions, and normalized, multiplicative and reflection positive graph parameters. In this article we show that each of these structures has a related, relaxed version, which are also equivalent. Using this, we describe a further structure equivalent to graph limits, namely probability measures on countable graphs that are ergodic with respect to the group of permutations of the nodes. As an application, we prove an analogue of the Positivstellensatz for graphs: we show that every linear inequality between subgraph densities that holds asymptotically for all graphs has a formal proof in the following sense: it can be approximated arbitrarily well by another valid inequality that is a “sum of squares” in the algebra of partially labeled graphs. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Modified Logarithmic Sobolev Inequalities in Discrete Settings

Motivated by the rate at which the entropy of an ergodic Markov chain relative to its stationary distribution decays to zero, we study modified versions of logarithmic Sobolev inequalities in the discrete setting of finite Markov chains and graphs. These inequalities turn out to be weaker than the standard log-Sobolev inequality, but stronger than the Poincare’ (spectral gap) inequality. We show that, in contrast with the spectral gap, for bounded degree expander graphs, various log-Sobolev constants go to zero with the size of the graph. We also derive a hypercontractivity formulation equivalent to our main modified log-Sobolev inequality. Along the way we survey various recent results that have been obtained in this topic by other researchers.      

Variation on a theorem of König

A min-max property of bipartite graphs is stated; it is a variation on the theorem of König ‘maximum matching = minimum covering’; one shows that a certain inequality holds for any graph and the equality for bipartite graphs is derived from a simple network flow model.     

On the effect of major vertices on the number of light edges

This paper presents an inequality satisfied by planar graphs of minimum degree five. For the purposes of this paper, an edge of a graph is light if the weight of the edge, or the sum of the degrees of the vertices incident with it, is at most eleven. The inequality presented shows that planar graphs of minimum degree five have a large number of light edges. This inequality improves upon a recent inequality of Borodin and Sanders, which showed that 7/15 times the number of edges of weight 10 plus 1/5 times the number of edges of weight 11 is at least 12. These constants 7/15 and 1/5 were shown to be best possible. The inequality in this paper shows that, for this type of graph, the presence of vertices of degree at least eight increases the number of light edges. A graph is presented which shows that the coefficient obtained for the number of degree eight vertices is best possible. © 1996 John Wiley & Sons, Inc.     

A Harnack inequality for Dirichlet eigenvalues

We prove a Harnack inequality for Dirichlet eigenfunctions of abelian homogeneous graphs and their convex subgraphs. We derive lower bounds for Dirichlet eigenvalues using the Harnack inequality. We also consider a randomization problem in connection with combinatorial games using Dirichlet eigenvalues. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 247–257, 2000     

Graphs Between the Elliptic and Parabolic Harnack Inequalities

We present graphs that satisfy the uniform elliptic Harnack inequality, for harmonic functions, but not the stronger parabolic one, for solutions of the discrete heat equation. It is known that the parabolic Harnack inequality is equivalent to the conjunction of a volume regularity and a L ² Poincaré inequality. The first example of graph satisfying the elliptic but not the parabolic Harnack inequality is due to M. Barlow and R. Bass. It satisfies the volume regularity and not the Poincaré inequality. We construct another example that does not satisfy the volume regularity.     

An Alexandrov–Fenchel-Type Inequality in Hyperbolic Space with an Application to a Penrose Inequality

We prove a sharp Alexandrov–Fenchel-type inequality for star-shaped, strictly mean convex hypersurfaces in hyperbolic n-space, n ≥ 3. The argument uses two new monotone quantities along the inverse mean curvature flow. As an application we establish, in any dimension, an optimal Penrose inequality for asymptotically hyperbolic graphs carrying a minimal horizon, with the equality occurring if and only if the graph is an anti-de Sitter–Schwarzschild solution. This sharpens previous results by Dahl–Gicquaud–Sakovich and settles, for this class of initial data sets, the conjectured Penrose inequality for time-symmetric space–times with negative cosmological constant. We also explain how our methods can be easily adapted to derive an optimal Penrose inequality for asymptotically locally hyperbolic graphs in any dimension n ≥ 3. When the horizon has the topology of a compact surface of genus at least one, this provides an affirmative answer, for this class of initial data sets, to a question posed by Gibbons, Chru?ciel and Simon on the validity of a Penrose-type inequality for exotic black holes.     

Global gradient estimate on graph and its applications

Continuing our previous work(ar Xiv:1509.07981v1),we derive another global gradient estimate for positive functions,particularly for positive solutions to the heat equation on finite or locally finite graphs.In general,the gradient estimate in the present paper is independent of our previous one.As applications,it can be used to get an upper bound and a lower bound of the heat kernel on locally finite graphs.These global gradient estimates can be compared with the Li–Yau inequality on graphs contributed by Bauer et al.[J.Differential Geom.,99,359–409(2015)].In many topics,such as eigenvalue estimate and heat kernel estimate(not including the Liouville type theorems),replacing the Li–Yau inequality by the global gradient estimate,we can get similar results.     

Cut sets and normed cohomology with applications to percolation

We discuss an inequality for graphs, which relates the distances between components of any minimal cut set to the lengths of generators for the homology of the graph. Our motivation arises from percolation theory. In particular this result is applied to Cayley graphs of finite presentations of groups with one end, where it gives an exponential bound on the number of minimal cut sets, and thereby shows that the critical probability for percolation on these graphs is neither zero nor one. We further show for this same class of graphs that the critical probability for the coalescence of all infinite components into a single one is neither zero nor one.

     

On the discrete version of Picone's identity

For a real number p with 1<p we consider the first eigenvalues of the p-Laplacian on graphs, and estimates for the solutions of p-Laplace equations on graphs. We provide a discrete version of Picone's identity and its application. More precisely, we prove a Barta-type inequality for graphs with boundary. Finally, we provide a discrete version of the anti-maximum principle.