اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA transfer principle and applications to eigenvalue estimates for graphs
59
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
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 La
placian. 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 gr
eater than $13.92$. We also find new upper bounds for the average degree of contact graphs in $mathbb{R}^4$ and $mathbb{R}^5$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
