图的正则覆盖顶点矩阵加权Zeta函数
A Vertex Matrix-Weighted Zeta Function of Regular Coverings of a Graph
DOI: 10.12677/pm.2024.146225, PDF, HTML, XML, 下载: 28  浏览: 62 
作者: 考梦诗:上海理工大学理学院,上海
关键词: Zeta函数顶点矩阵加权图的正则覆盖二部图Zeta Function Vertex Matrix-Weight Regular Covering of Graphs Bipartite Graph
摘要: 本文首先介绍了关于Zeta函数的课题来源及意义,然后介绍了相关研究成果和现状,之后引入了图的顶点矩阵加权的相关定义和定理,再之后给出了图的正则覆盖Zeta函数的行列式表达式及其证明,最后考虑到二部图的特殊性,给出了二部图的覆盖图顶点矩阵加权的Zeta函数。
Abstract: This paper first introduces the origin and significance of Zeta function, then introduces the related research results and the present situation, and then introduces the related definitions and theorems of vertex matrix weighting of graphs, the determinant expression and its proof of zeta functions of regular covering of a graph are given. At last, considering the particularity of bipartite graphs, the weighted Zeta functions of the vertex matrix of bipartite graphs are given.
文章引用:考梦诗. 图的正则覆盖顶点矩阵加权Zeta函数[J]. 理论数学, 2024, 14(6): 36-42. https://doi.org/10.12677/pm.2024.146225

1. 绪论

图的Zeta函数首先是由Ihara [1]提出的正则图的Ihara Zeta函数,他证明了正则图的Ihara Zeta函数的倒数是一个多项式。Sunada [2]提出了图的正则图的Zeta函数和图的基本群之间的统一表示。Hashimoto [3]将Ihara关于正则图的Ihara Zeta函数的结论推广到了非正则图,并证明了它的倒数也是由一个含有边矩阵的行列式构成的多项式。利用非正则图的邻接矩阵,Bass [4]给出了非正则图的Ihara Zeta函数的另一个行列式表达式。之后,Stark和Terras [5]定义了图的边Zeta函数和路Zeta函数。

作为图的矩阵变量Zeta函数,Watanabe和Fukumizu [6]定义了图的矩阵加权Zeta函数,并给出了它的行列式表达式。Iwao Sato [7]等人又介绍了一个矩阵加权函数,并给出了它的行列式表达式。作为一个应用,他们利用图的矩阵加权L-函数的积给出了图的正则覆盖的矩阵加权Zeta函数的一个分解公式。Sato和他的合作者定义了各种加权版本的Zeta函数,并得到这些Zeta函数的行列式表达式。

Ihara Zeta函数是20世纪60年代Yasutaka Ihara提出的一个计算一阶p-元群离散子群中素元的Zeta函数。它可以解释为相应的有限图的一个几何Zeta函数,这是与p-元组相连的Bruhat-Titsbuilding的商。

图上的非回溯随机游动与图的Ihara Zeta函数密切相关。2007年Alon,Benjamini,Lubetzky和Sodin [8]研究了正则图的非回溯随机游动的混合率,证明了正则图上的非回溯随机游动比允许回溯的随机游动具有更快的混合率。2013年Fitzner和Hofstad [9]处理格和环面上非回溯随机游动的收敛性。Krzakala [10]等人利用边矩阵来研究SVD算法。两年后Angel,Friedman和Hoory [11]研究了图的泛覆盖的非回溯谱。图的非回溯谱正是其边矩阵的谱。又过了一年,Kempton [12]证明了Ihara公式的一个加权版本,并得到了正则和半正则二部图的非回溯随机游动的过渡转移矩阵谱。此外,Kempton还证明了Alon等人关于正则图上非回溯随机游动的混合率的结果,并将这一结果推广到半正则二部图。

2019年Norio Konno [13]等人介绍了图G的一个新的加权Ihara Zeta函数,并给出了它的行列式表达式。给出了G的正则覆盖的新的加权Ihara Zeta函数的分解公式,并引入了G的新的加权Ihara L-函数,给出了它的行列式表达式。作为推论,他们给出了G的正则覆盖的新的加权Ihara Zeta函数的分解公式。作为应用,他们给出了Kempton关于正则图和半正则二部图的非回溯随机游动过渡矩阵谱的结果的新证明。

2021年Zhu [14]定义了图G的顶点加权Bartholdi Zeta函数,并给出了其对应的行列式表达式,之后还定义了顶点加权Bartholdi L-函数,并证明了图G的正则覆盖下的顶点加权Bartholdi Zeta函数是图G的顶点加权Bartholdi L-函数的乘积。

2. 顶点矩阵加权的Zeta函数

这里所提到的图都是有限的简单图。 G=( V( G ),E( G ) ) 是一个连通图,其中 V( G ) 是它的顶点集, E( G ) 是它的无向边集。uv表示连接点uv的一条边,弧 ( u,v ) 是连接从uv一条有向边。 D( G )={ ( u,v ),( v,u )|uvE( G ) } 。对于有向边 e=( u,v )D( G ) ,让 u=o( e ) v=t( e ) 。此外, e 1 =( v,u ) 表示 e=( u,v ) 的逆。

G中长度为n的路P是一系列边 P=( e 1 , e 2 ,, e n ) ,其中要满足 e i D( G ) t( e i )=o( e i+1 )( 1in1 )

对于路 P=( e 1 , e 2 ,, e n ) | P |=n o( P )=o( e 1 ) 并且 t( P )=t( e n ) ,当存在 i( 1in1 ) 使得 e i+1 1 = e i 时,称这条路有回溯,当 o( P )=t( P ) 时,称这条路是一个圈。圈 C=( e 1 , e 2 ,, e n ) 的逆是圈 C 1 =( e n 1 , e n1 1 ,, e 1 1 )

对于两个圈 C 1 =( e 1 , e 2 ,, e m ) C 2 =( f 1 , f 2 ,, f m ) 如果存在k使得对于所有的j f j = e j+k ,那么称这两个圈是等价的。一般而言圈C的逆和它本身是不等价的。 [ C ] 表示圈C的等价类,即所有与C等价的圈的集合。 B r 表示圈B进行r次循环得到的圈,这种圈称作圈B的幂次。如果圈C没有回溯,那么就称它是约化的。此外如果圈C不是严格比它小的一个圈的幂次,那么就称这个圈是素圈。事实上,图G的每个约化的素圈的等价类唯一对应图G在点v的基本群 π 1 ( G,v ) 的共轭类。

G=( V( G ),E( G ) ) 是一个有限连通图,其中 V( G )={ v 1 ,, v n } E( G )={ e 1 ,, e m } 并且 D( G )={ e 1 , e 1 1 , e m 1 } 。令 w:V( G ) C k×k 表示一个函数。对于G中的圈 C=( e 1 , e 2 ,, e r ) W C =w( t( e 1 ) )w( t( e r ) ) ,并且函数满足表达式 w( e 1 )=w ( e ) 1

定义1. 图的顶点矩阵加权Zeta函数定义为:

ζ G ( w )= [ C ] det ( I W C ) 1

其中, [ C ] 跑遍G中约化的素圈的所有等价类。

首先定义三个 2mk×2mk 矩阵, B= ( B e,f ) e,fD( G ) J 0 = ( J e,f ) e,fD( G ) U

B e,f ={ I k t( e )=o( f ) 0 , J e,f ={ I k f= e 1 0 ,

U=diag( w( t( e 1 ) ),w( t( e 1 1 ) ),w( t( e 2 ) ),,w( t( e m ) ),w( t( e m 1 ) ) ) .

之后便可以得到如下结果:

定理2. G是一个n个点m条边的有限连通图 w:V( G ) k×k 表示一个函数,则图的顶点矩阵加权Zeta函数的倒数可以写成:

ζ G ( w ) 1 = [ C ] det( I W C )=det( I 2mk U( B J 0 ) )

为了进一步得到Zeta函数的行列式表达,定义两个分块矩阵: A ˜ = A ˜ ( G )= ( A xy ) x,yV( G )

A xy ={ ( I k w( y )w( x ) ) 1 w( y ) ( x,y )D( G ) 0 ,

D ˜ = D ˜ ( G )= ( D xy ) x,yV( G ) 是一个准对角矩阵定义为:

D xx = o( e )=x ( I k w( t( e ) )w( t( e 1 ) ) ) 1 w( t( e ) )w( t( e 1 ) ).

定理3. G是一个n个点m条边的有限连通图。 w:V( G ) k×k 表示一个函数,并且对于所有的 eD( G )det( I k w( t( e i ) )w( t( e i 1 ) ) )0 ,则图的顶点矩阵加权Zeta函数的倒数可以写成:

ζ G ( w ) 1 =det( I nk A ˜ + D ˜ ) i=1 m det( I k w( t( e i ) )w( t( e i 1 ) ) )

3. 图的正则覆盖顶点矩阵加权Zeta函数

G是一个有限连通图,Γ是一个阶为r的群。对于映射 α:D( G )Γ ,对于任一个 ( u,v )D( G ) ,如果满足 α( ( v,u ) )=α ( ( u,v ) ) 1 ,则称这个映射是一般电压分配。 ( G,α ) 叫做一个一般电压图。这个图 G α 被称作电压在Γ或图G的Γ-覆盖上的图G的导出图覆盖,其中 V( G α )=V( G )×Γ ( ( u,h ),( v,k ) )D( G α ) ,当且仅当 ( u,v )D( G ) 并且 k=hα( u,v ) 。自然投射 π: G α G 定义为 π( u,h )=u 。Γ-覆盖 G α 是一个图G | Γ | -折叠正则覆盖。此外[4],对于图G的每一个正则覆盖都存在一个群Γ,使得这个正则覆盖是图G的一个Γ-覆盖。

对于Γ-覆盖 G α ,令 v g =( v,g ) e g =( e,g ) ,其中 vV( G ) eD( G ) gΓ 。则根据正则覆盖的定义有 e g 1 = ( e 1 ) gα( e )

G是一个n个点m条边的有限连通图,w是图G的一个顶点加权。则由w导出的图 G α 的点加权 w ˜ :V( G α ) C k×k 定义为:

w ˜ ( u,g )= w ˜ ( u g )=w( u ),( u,g )V( G α ) .

之后,令 | Γ |=r 。定义三个 2mkr×2mkr 维矩阵 B ˜ ( G α )= ( B ˜ e g , f h ) e g , f h D( G α ) ,

J ˜ 0 ( G α )= ( J ˜ e g , f h ) e g , f h D( G α ) U ˜ 如下:

B ˜ e g , f h ={ I k t( e g )=o( f h ) 0 , J ˜ e g , f h ={ I k f h = e g 1 0

U ˜ = I r U

再然后对于任一个 gΓ ,定义一个 nk×nk 维矩阵 A g = ( A xy,g ) x,yV( G )

A xy,g ={ ( I k w( y )w( x ) ) 1 w( y ) ( x,y )D( G )α( x,y )=g 0

根据之前定义的矩阵,可以得到: A ˜ ( G )= gΓ A g

对于方阵 M 1 , M 2 ,, M S M 1 M 2 M S 表示 M 1 , M 2 ,, M S 的分块对角和矩阵,如果 M 1 = M 2 == M S =M ,则将它们的分块对角和写成 sM= M 1 M 2 M S

定理4. G是一个n个点m条边的有限连通图。w是该图的一个点加权,并且对于所有的

eD( G )det( I k w( t( e i ) )w( t( e i 1 ) ) )0 。Γ是一个阶为r的群, α:D( G )Γ 是一个一般电压分配。 ρ 1 =1, ρ 2 ,, ρ t 是Γ的所有不相等的不可约表示,对于每个i d i =deg ρ i 表示 ρ i 的度。则图 G α 的顶点矩

阵加权Zeta函数的倒数可以写成:

ζ G α ( w ˜ ) 1 =det( I 2mrk U ˜ ( B ˜ ( G α ) J ˜ 0 ( G α ) ) ) = ζ G ( w ) 1 j=2 t { i=1 m det ( I k w( t( e i ) )w( t( e i 1 ) ) ) d j ×det( I nk d j gΓ ρ j ( g ) A g + I d j D ˜ ( G ) ) } d j .

证明。由定理2和定理3得

ζ G α ( w ˜ ) 1 =det( I 2mrk U ˜ ( B ˜ ( G α ) J ˜ 0 ( G α ) ) ) =det( I nrk A ˜ ( G α )+ D ˜ ( G α ) ) i=1 m det ( I k w( t( e i ) )w( t( e i 1 ) ) ) r

对于每个 gΓ 定义一个 r×r 维矩阵 P g = ( P hl ( g ) ) h,lΓ

P hl ( g ) ={ 1 l=hg 0

G α 中的点分成r个分块:

( v 1 ,1 ),( v 2 ,1 ),,( v n ,1 );( v 1 , g 2 ),( v 2 , g 2 ),,( v n , g 2 );;( v 1 , g r ),( v 2 , g r ),,( v n , g r )

G α 的定义可以得到 A ˜ ( G α )= gΓ P g A g 。对于 e ˜ π 1 ( e ) eD( G ) ,因为 w ˜ ( t( e ˜ ) )=w( t( e ) ) w ˜ ( t( e ˜ 1 ) )=w( t( e 1 ) ) ,所以有

( D ˜ ( G α ) ) u g , u g = o( e ˜ )= u g [ I k w ˜ ( t( e ˜ ) ) w ˜ ( t( e ˜ 1 ) ) ] 1 w ˜ ( t( e ˜ ) ) w ˜ ( t( e ˜ 1 ) ) = o( e )=u [ I k w( t( e ) )w( t( e 1 ) ) ] 1 w( t( e ) )w( t( e 1 ) ) = ( D ˜ ( G ) ) uu

因此 D ˜ ( G α )= I r D ˜ ( G )

ρ 为Γ的右正则表示。 ρ 1 =1, ρ 2 ,, ρ t 是Γ的所有不相等的不可约表示,对于每个i d i =deg ρ i 表示 ρ i 的度,其中 d 1 =1 。对于每个 gΓ ,有 ρ( g )= P g 。由群的表示理论知[5] [12],存在一个可逆矩阵P,使得

P 1 ρ( g )P=( 1 ) d 2 ρ 2 ( g ) d t ρ t ( g ) ,其中 gΓ

所以可以得到

( P 1 I nk ) A ˜ ( G α )( P I nk )= gΓ { ( 1 ) d 2 ρ 2 ( g ) d t ρ t ( g ) } A g

因此

ζ G α ( w ˜ ) 1 = j=1 t { i=1 m det ( I k w( t( e i ) )w( t( e i 1 ) ) ) d j × det( I nk d j gΓ ρ j ( g ) A g + I d j D ˜ ( G ) ) } d j = ζ G ( w ) 1 j=2 t { i=1 m det ( I k w( t( e i ) )w( t( e i 1 ) ) ) d j × det( I nk d j gΓ ρ j ( g ) A g + I d j D ˜ ( G ) ) } d j .

4. 二部图的正则覆盖Zeta函数

G X,Y 是一个 n 1 个点在X中, n 2 个点在Y中并且有m条边的有限连通二部图。 w:X x×y ,Y y×x 表示一个函数。对于 G X,Y 中的圈 C=( e 1 , e 2 ,, e r ) ,令 W C =w( t( e 1 ) )w( t( e 2 ) )w( t( e r ) ) 。Γ是一个r阶的群, α:D( G )Γ 是一个一般电压分配。在Γ-覆盖 G X,Y α 中,定义 G X,Y α 的顶点矩阵加权为 w ˜ ( u,g )= w ˜ ( u g )=w( u )

首先还是先定义三个矩阵 B ¯ = ( B ¯ e g , f h ) e g , f h D( G X,Y α ) J ¯ 0 = ( J ¯ e g , f h ) e g , f h D( G X,Y α ) U ¯

B ¯ e g , f h ={ I y t( e g )=o( f h ),t( e )X I x t( e g )=o( f h ),t( e )Y 0 , J ¯ e g , f h ={ I y f h = e g 1 ,t( e )X I x f h = e g 1 ,t( e )Y 0

U ¯ = I r U ^

再定义两个矩阵 A ¯ g = ( A ¯ uv,g ) u,vXY D ¯

A ¯ uv,g ={ ( Iw( v )w( u ) ) 1 w( v ) ( u,v )D( G X,Y )α( u,v )=g 0

D ¯ = I r D ^

则可以得到如下结果:

定理5. G X,Y 是一个 n 1 个点在X中, n 2 个点在Y中并且有m条边的有限连通二部图。w是上述定义的 G X,Y 的一个顶点矩阵加权。Γ是一个r阶的群, α:D( G )Γ 是一个一般电压分配。此外, ρ 1 =1, ρ 2 ,, ρ t 是Γ的所有不相等不可约的表示,并且对于每个i d i =deg ρ i ρ i 的度。则 G X,Y α 的顶点矩阵加权zeta函数的倒数可以写成:

ζ G X,Y α ( w ˜ ) 1 =det( I U ¯ ( B ¯ J ¯ 0 ) ) = ζ G X,Y ( w ) 1 j=2 t { i=1 m det ( Iw( t( e i ) )w( t( e i 1 ) ) ) d j × det( I gΓ ρ j ( g ) A ¯ g + I d j D ^ ) } d j .

参考文献

[1] Ihara, Y. (1966) On Discrete Subgroups of the Two by Two Projective Linear Group over p-Adic Fields. Journal of the Mathematical Society of Japan, 18, 219-235.
https://doi.org/10.2969/jmsj/01830219
[2] Kotani, M. and Sunada, T. (2000) Zeta Functions of Finite Graphs. The University of Tokyo. Journal of Mathematical Sciences, 7, 7-25.
[3] Hashimoto, K.I. (1989) Zeta Functions of Finite Graphs and Representations of p-Adic Groups. Advanced Studies in Pure Mathematics, 15, 211-280.
https://doi.org/10.2969/aspm/01510211
[4] Bass, H. (1992) The Ihara-Selberg Zeta Function of a Tree Lattice. International Journal of Mathematics, 3, 717-797.
https://doi.org/10.1142/s0129167x92000357
[5] Stark, H.M. and Terras, A.A. (1996) Zeta Functions of Finite Graphs and Coverings. Advances in Mathematics, 121, 124-165.
https://doi.org/10.1006/aima.1996.0050
[6] He, Y. (2011) Graph Zeta Function and Gauge Theories. Journal of High Energy Physics, 2011, 64.
https://doi.org/10.1007/jhep03(2011)064
[7] Sato, I., Mitsuhashi, H. and Morita, H. (2013) A Matrix-Weighted Zeta Function of a Graph. Linear and Multilinear Algebra, 62, 114-125.
https://doi.org/10.1080/03081087.2013.764496
[8] Alon, N., Benjamini, I., Lubetzky, E. and Sodin, S. (2007) Non-Backtracking Random Walks Mix Faster. Communications in Contemporary Mathematics, 9, 585-603.
https://doi.org/10.1142/s0219199707002551
[9] Fitzner, R. and van der Hofstad, R. (2013) Non-Backtracking Random Walk. Journal of Statistical Physics, 150, 264-284.
https://doi.org/10.1007/s10955-012-0684-6
[10] Krzakala, F., Moore, C., Mossel, E., Neeman, J., Sly, A., Zdeborová, L., et al. (2013) Spectral Redemption in Clustering Sparse Networks. Proceedings of the National Academy of Sciences, 110, 20935-20940.
https://doi.org/10.1073/pnas.1312486110
[11] Angel, O., Friedman, J. and Hoory, S. (2014) The Non-Backtracking Spectrum of the Universal Cover of a Graph. Transactions of the American Mathematical Society, 367, 4287-4318.
https://doi.org/10.1090/s0002-9947-2014-06255-7
[12] Kempton, M. (2015) High Dimensional Spectral Graph Theory and Non-Backtracking Random Walks on Graphs. ProQuest LLC, 94.
[13] Konno, N., Mitsuhashi, H., Morita, H. and Sato, I. (2019) A New Weighted Ihara Zeta Function for a Graph. Linear Algebra and Its Applications, 571, 154-179.
https://doi.org/10.1016/j.laa.2019.02.022
[14] Zhu, L. (2021) A Vertex Weighted Bartholdi Zeta Function for a Graph. Linear Algebra and Its Applications, 621, 254-271.
https://doi.org/10.1016/j.laa.2021.03.024