Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA transfer principle and applications to eigenvalue estimates for graphs
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In this paper, we prove a variant of the Burger-Brooks transfer principle which, combined with recent eigenvalue bounds for surfaces, allows to obtain upper bounds on the eigenvalues of graphs as a function of their genus. More precisely, we show the existence of a universal constants $C$ such that the $k$-th eigenvalue $lambda_k^{nr}$ of the normalized Laplacian of a graph $G$ of (geometric) genus $g$ on $n$ vertices satisfies $$lambda_k^{nr}(G) leq C frac{d_{max}(g+k)}{n},$$ where $d_{max}$ denotes the maximum valence of vertices of the graph. This result is tight up to a change in the value of the constant $C$, and improves recent results of Kelner, Lee, Price and Teng on bounded genus graphs. To show that the transfer theorem might be of independent interest, we relate eigenvalues of the Laplacian on a metric graph to the eigenvalues of its simple graph models, and discuss an application to the mesh partitioning problem, extending pioneering results of Miller-Teng-Thurston-Vavasis and Spielman-Tang to arbitrary meshes.
rate research
Read More
Given a compact Riemannian manifold (M n , g) with boundary $partial$M , we give an estimate for the quotient $partial$M f d$mu$ g M f d$mu$ g , where f is a smooth positive function defined on M that satisfies some inequality involving the scalar Laplacian. By the mean value lemma established in [37], we provide a differential inequality for f which, under some curvature assumptions, can be interpreted in terms of Bessel functions. As an application of our main result, a direct proof is given of the Faber-Krahn inequalities for Dirichlet and Robin Laplacian. Also, a new estimate is established for the eigenvalues of the Dirac operator that involves a positive root of Bessel function besides the scalar curvature. Independently, we extend the Robin Laplacian on functions to differential forms. We prove that this natural extension defines a self-adjoint and elliptic operator whose spectrum is discrete and consists of positive real eigenvalues. In particular, we characterize its first eigenvalue and provide a lower bound of it in terms of Bessel functions.
We show that the asymptotic dimension of a geodesic space that is homeomorphic to a subset in the plane is at most three. In particular, the asymptotic dimension of the plane and any planar graph is at most three.
A rigidity theory is developed for frameworks in a metric space with two types of distance constraints. Mixed sparsity graph characterisations are obtained for the infinitesimal and continuous rigidity of completely regular bar-joint frameworks in a variety of such contexts. The main results are combinatorial characterisations for (i) frameworks restricted to surfaces with both Euclidean and geodesic distance constraints, (ii) frameworks in the plane with Euclidean and non-Euclidean distance constraints, and (iii) direction-length frameworks in the non-Euclidean plane.
A bar-joint framework $(G,p)$ in a (non-Euclidean) real normed plane $X$ is the combination of a finite, simple graph $G$ and a placement $p$ of the vertices in $X$. A framework $(G,p)$ is globally rigid in $X$ if every other framework $(G,q)$ in $X$ with the same edge lengths as $(G,p)$ arises from an isometry of $X$. The weaker property of local rigidity in normed planes (where only $(G,q)$ within a neighbourhood of $(G,p)$ are considered) has been studied by several researchers over the last 5 years after being introduced by Kitson and Power for $ell_p$-norms. However global rigidity is an unexplored area for general normed spaces, despite being intensely studied in the Euclidean context by many groups over the last 40 years. In order to understand global rigidity in $X$, we introduce new generalised rigid body motions in normed planes where the norm is determined by an analytic function. This theory allows us to deduce several geometric and combinatorial results concerning the global rigidity of bar-joint frameworks in $X$.
A contact graph of a packing of closed balls is a graph with balls as vertices and pairs of tangent balls as edges. We prove that the average degree of the contact graph of a packing of balls (with possibly different radii) in $mathbb{R}^3$ is not greater than $13.92$. We also find new upper bounds for the average degree of contact graphs in $mathbb{R}^4$ and $mathbb{R}^5$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
