MAXIMIZATION OF THE FIRST LAPLACE EIGENVALUE OF A FINITE GRAPH TAKUMI GOMYOU AND SHIN NAYATANI

2025-05-02 0 0 3.71MB 17 页 10玖币

侵权投诉

MAXIMIZATION OF THE FIRST LAPLACE EIGENVALUE OF

A FINITE GRAPH

TAKUMI GOMYOU AND SHIN NAYATANI

Abstract. Given a length function on the edge set of a ﬁnite graph, we deﬁne

a vertex-weight and an edge-weight in terms of it and consider the corresponding

graph Laplacian. In this paper, we consider the problem of maximizing the ﬁrst

nonzero eigenvalue of this Laplacian over all edge-length functions subject to a

certain normalization. For an extremal solution of this problem, we prove that

there exists a map from the vertex set to a Euclidean space consisting of ﬁrst

eigenfunctions of the corresponding Laplacian so that the length function can be

explicitly expressed in terms of the map and the Euclidean distance. This is a

graph-analogue of Nadirashvili’s result related to ﬁrst-eigenvalue maximization

problem on a smooth surface. We discuss simple examples and also prove a sim-

ilar result for a maximizing solution of the G¨oring-Helmberg-Wappler problem.

Introduction

Let G= (V, E) be a ﬁnite graph, where V(resp. E) is the set of vertices

(resp. edges). For any pair of a vertex-weight m0:V→R>0and an edge-weight

m1:E→R≥0, one can deﬁne the corresponding Laplacian ∆(m0,m1). If an edge-

length function l:E→R>0is given, following Fujiwara [6], we deﬁne weights m0

and m1suitably in terms of land thus the Laplacian ∆l:= ∆(m0,m1). Then we

regard the length function las a variable and consider the problem of maximizing

the ﬁrst nonzero eigenvalue of the Laplacian ∆lover all choices of lsubject to a

certain normalization. A maximizing length function does not always exist, but

if one exists, we prove that there exists a map φ:V→RNconsisting of ﬁrst

eigenfunctions of the corresponding Laplacian so that the length function can be

explicitly expressed in terms of the map φand the Euclidean distance. Here, N

is some positive integer less than or equal to the multiplicity of the ﬁrst nonzero

eigenvalue. More generally, we prove the same assertion for any extremal solution.

A similar ﬁrst-eigenvalue maximization problem was formulated by G¨oring-

Helmberg-Wappler [7, 8]. They ﬁx a vertex-weight m0and an edge-length function

l, deﬁne the weighted Laplacian ∆(m0,m1)in terms of m0and a choice of edge-weight

m1, and maximize the ﬁrst nonzero eigenvalue of ∆(m0,m1)over all choices of m1

subject to a normalization. They veriﬁed that a maximizing edge-weight always

exists though it may vanish on some edges. If this degeneracy does not happen,

then there exists a map similar to the above one but with the better property that

Key words and phrases. graph, Laplacian, eigenvalue, embedding.

Department of Mathematics, Osaka University, Osaka 560-0043, Japan,

gomyou@cr.math.sci.osaka-u.ac.jp.

Graduate School of Mathematics, Nagoya University, Chikusa-ku, Nagoya 464-8602, Japan,

nayatani@math.nagoya-u.ac.jp.

arXiv:2210.10966v2 [math.CO] 8 Oct 2024

the length function exactly coincides with the pull-back of the Euclidean distance

by the map. Historically, Fiedler [5] considered a special case of this problem, ﬁx-

ing m0≡1 and maximizing the ﬁrst nonzero eigenvalue of the weighted Laplacian

over all choices of m1with mean value one. He calls the maximum value as the

absolute algebraic connectivity of the graph. The condition on m1is identical to

G¨oring et al.’s with the choice l≡1.

Regarding the largeness of the ﬁrst positive eigenvalue of the graph Laplacian,

another direction of study involves expander graphs, that is, a sequence of regular

graphs with ﬁxed degree and growing number of vertices, ensuring that their ﬁrst

positive eigenvalues are uniformly bounded away from zero. Note that for a generic

sequence of such graphs, the ﬁrst positive eigenvalues will decay to zero. For this

subject, the reader is referred to the comprehensive exposition [10].

In the background of the present work, there also is the problem of maximizing

the ﬁrst Laplace eigenvalue on a manifold. The origin of the problem is the cele-

brated work of Hersch [9], who proved that on the two-sphere, the scale-invariant

quantity λ1(g)Area(g), where gis a Riemannian metric and Area(g) is the area

of g, is maximized by the metrics of round spheres in R3. Motivated by Hersch’s

result, Berger [1] asked whether on an arbitrary compact manifold of dimension

n, the scale-invariant quantity λ1(g)Vol(g)2/n was bounded from above by a con-

stant depending only on the manifold. Then Urakawa [22] found an explicit family

of metrics gt,t > 0, on the three-sphere for which the quantity λ1(gt)Vol(gt)2/3,

where Vol(g) is the volume of g, diverges to inﬁnity as t→ ∞. This answers in the

negative the above question of Berger. Later, Colbois-Dodziuk [3] proved, by glu-

ing Urakawa’s metrics or their analogues on higher dimensional spheres to a given

manifold, that the quantity λ1(g)Vol(g)2/n is unbounded on any compact mani-

fold. On the other hand, for surfaces, rich progress has been made on the Berger

problem and also the problem of maximizing λ1(g)Area(g) (which is equivalent to

maximizing λ1(g) under the normalization Area(g) = 1). The ﬁrst result (after

Hersch) is due to Yang-Yau [23], who proved that λ1(g)Area(g)≤8π(γ+1), where

γis the genus of the surface. (Later El Souﬁ-Ilias [4] remarked that the constant

on the right-hand side could be improved to 8πγ+3

2.) Since the work of Yang-

Yau, many important works were done and many interesting results were proved.

For these, we refer the reader to [13, 16, 17, 11, 19, 18, 15, 21, 12]. Here, we only

mention the result of Nadirashvili, which states that if a Riemannian metric gis an

extremal solution of the problem of maximizing λ1(g)Area(g) on a compact surface

M, then there exist ﬁrst eigenfunctions φ1, . . . , φNof the corresponding Laplacian

such that φ= (φ1, . . . , φN): M→RNis an isometric immersion; Therefore, φis

a minimal immersion into the sphere SN−1(p2/λ1(g)) by the Takahashi theorem.

Our main result is regarded as a discrete analogue of this result of Nadirashvili.

For the study of the eigenvalues of the graph Laplacian from the perspective of

diﬀerential geometry, the reader is referred to the comprehensive monograph [2].

This paper is organized as follows. In Section 1, we consider the graph Laplacian

deﬁned from an edge-length function and formulate a maximization problem for the

ﬁrst nonzero eigenvalue of this Laplacian. We state a Nadirashvili-type theorem

for an extremal solution of this problem. This is the main theorem and it is proved

in Section 2, where a weak converse of the theorem is also proved. In Section 3, we

ﬁnd extremal solutions of the above problem for some graphs by numerical means.

We also ﬁnd the maps by ﬁrst eigenfunctions of the main theorem. In Section 4,

we prove an analogous result for a maximizing solution of the G¨oring-Helmberg-

Wappler problem.

1. Preliminaries, Problem and Main Result

Let G= (V, E) be a ﬁnite connected graph, where Vand Eare the sets of

vertices and (undirected) edges, respectively. We assume that Gis simple, that is,

that Ghas no loops nor multiple edges. Let uv denote the edge whose endpoints are

uand v.Gbeing undirected means that uv =vu. Choose weights m0:V→R>0

and m1:E→R≥0, and let RVdenote the set of functions φ:V→R, equipped

with the inner product

⟨φ1, φ2⟩=X

u∈V

m0(u)φ1(u)φ2(u), φ1, φ2∈RV.

Then the graph Laplacian is a positive symmetric linear operator ∆(m0,m1):RV→

RV, deﬁned by

(1.1) (∆(m0,m1)φ)(u) = X

v∼u

m1(uv)

m0(u)(φ(u)−φ(v)) , u ∈V,

where we write v∼uif uv ∈E. Note that ∆(m0,m1)has only real and nonnegative

eigenvalues, always has eigenvalue 0, and the corresponding eigenspace consists

precisely of constant functions on Vif E′={uv ∈E|m1(uv)>0}is connected,

which we assume from here on. The second smallest eigenvalue of ∆(m0,m1), which

is positive, will be denoted by λ1(G, (m0, m1)) and referred to as the ﬁrst nonzero

eigenvalue of ∆(m0,m1). It is a standard fact that λ1(G, (m0, m1)) is characterized

variationally as

λ1(G, (m0, m1)) = min

φ⟨∆(m0,m1)φ, φ⟩

⟨φ, φ⟩

= min

φPuv∈Em1(uv)(φ(u)−φ(v))2

Pu∈Vm0(u)φ(u)2,(1.2)

where the minimum is taken over all nonzero functions φsuch that

Pu∈Vm0(u)φ(u) = 0, meaning that φis orthogonal to constant functions, that is,

eigenfunctions of the eigenvalue 0.

Other than the operator language, we can employ the matrix language to de-

scribe the graph Laplacian. To do so, we write V={1,...,|V|} and choose the

orthonormal basis

ei:j∈V7→ δij

pm0(i)∈R, i ∈V,

of RV. Then the corresponding representation matrix L:= L(m0,m1)of the Lapla-

cian ∆(m0,m1)is given by L=D−1/2L0D−1/2, where D= diag(m0(1), . . . , m0(|V|))

and L0has diagonal components

(L0)ii =X

j∼i

m1(ij), i ∈V

and oﬀ-diagonal components

(L0)ij =



−m1(ij), ij ∈E,

0, ij /∈E.

The matrix Lis positive, symmetric, and has eigenvalue 0 with eigenvector x0=

pm0(1),...,pm0(|V|). Note also that the variational characterization (1.2) of

λ1(G, (m0, m1)) is expressed as

λ1(G, (m0, m1)) = min

Lx ·x

x·x,

where ·denotes the Euclidean inner product on R|V|and the minimum is taken

over all nonzero vectors x∈R|V|such that x·x0= 0.

Remark 1.Associated with the operator-matrix correspondence above, it should

be noted that given a vector x= (x1, . . . , xn)∈R|V|, the corresponding function

φ∈RVis given by

φ(i) = xi/pm0(i),1≤i≤ |V|.

If φ, ψ ∈RVcorrespond to x, y ∈R|V|, respectively, then ⟨φ, ψ⟩=x·y. This

observation is necessary in working with explicit examples in Section 3.

We now formulate a ﬁrst-eigenvalue maximization problem whose variable is the

edge-length function l:E→R>0. Following Fujiwara [6], for a given l, we deﬁne

a vertex-weight m0:V→R>0and an edge-weight m1:E→R>0by

m0(u) = X

v∼u

l(uv), u ∈Vand m1(uv) = 1

l(uv), uv ∈E,

respectively. Let ∆ldenote the corresponding Laplacian.

Problem 1.1. Over all edge-length functions l, subject to the normalization

(1.3) X

u∈V

m0(u) = 2 X

uv∈E

l(uv) = 1,

maximize the ﬁrst nonzero eigenvalue λ1(G, l)of ∆l.

Remark 2.In the deﬁnition of the weighted Laplacian, it is standard to assume

that m0(u) = Pv∼um1(u, v) (cf. [2]). The above deﬁnition of ∆lby Fujiwara

deviates from this convention. However, it has a merit (cf. [6]): the eigenvalues

of the Laplacian of a compact Riemannian manifold (M, g) are approximated in a

certain coarse sense by the eigenvalues of Fujiwara’s Laplacian of 1/n-nets in M

equipped with appropriate graph structures and edge-length functions ln≡1/n,

as n→ ∞.

The squared edge-length function l2is regarded as a graph analogue of the

Riemannian metric. For c > 0, we have ∆cl =1

c2∆l, which is consistent with

the relation ∆c2g=1

c2∆gfor the Reimannian Laplacian under the rescaling of

Riemannian metric g.

Following El Souﬁ-Ilias [4] (see also [17]), we introduce the following deﬁnition:

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

MAXIMIZATIONOFTHEFIRSTLAPLACEEIGENVALUEOFAFINITEGRAPHTAKUMIGOMYOUANDSHINNAYATANIAbstract.Givenalengthfunctionontheedgesetofafinitegraph,wedefineavertex-weightandanedge-weightintermsofitandconsiderthecorrespondinggraphLaplacian.Inthispaper,weconsidertheproblemofmaximizingthefirstnonzeroeigenvalueofth...

展开>> 收起<<

MAXIMIZATION OF THE FIRST LAPLACE EIGENVALUE OF A FINITE GRAPH TAKUMI GOMYOU AND SHIN NAYATANI.pdf

共17页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

MAXIMIZATION OF THE FIRST LAPLACE EIGENVALUE OF A FINITE GRAPH TAKUMI GOMYOU AND SHIN NAYATANI

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: