关于一类代数二部图的研究

摘要

具有高度对称性和很大围长的图在极图理论、纠错编码理论、密码学、网络通信以及量子计算等各种不同的领域内具有重要应用。对于素数幂q和整数k≥2，1995年Lazebnik和Ustimenko利用李群的根系在[16]中提出了一个q-正则的代数二部图D(k，q)，它是边传递的并且围长不小于k+4.自提出以来，这个二部图得到了广泛的关注和研究，不但为一系列的极图问题提供了最佳的上界或下界估计，也为具有优异纠错性能的LDPC码提供了一种很好的构造方法，还可以用来设计快速的对称密码算法和公钥密码算法。本学位论文进一步研究二部图D(k，q)的性质，给出了其中的路径的显式表达公式，证明了关于其围长的一个猜想在几种新的情形下的正确性，提出了D(k，q)的一个新的推广Γ(Ω，q)，深入讨论了推广的二部图Γ（Ω,q）的连通分支数、路径及其表示、自同构、对称性和围长。
　　我们首先给出了二部图D(k，q)的一个等价构造Λk,q,研究了F∞q上的三个线性变换σ、Τ和δ的一些性质，讨论了它们在Fq上的多项式的唯一表示问题。然后我们利用这些线性变换改写了二部图Λk，q的邻接关系，得到了Λk,q中的路径上的顶点之间的一个递推关系。进一步我们还利用齐次多项式ρs（w1，w2,…，wn），给出了Λk,q中始于全零向量的路径上的各顶点用所经过的顶点的颜色（第一个坐标）表示的显式表达公式。特别，当这样的路径上的属于同一顶点集合的相邻顶点的颜色之差取定值时，我们计算了路径上各顶点的所有坐标，并由此证明了关于D(k，q)的围长的猜想A:
　　对所有的奇数k≥3和素数幂q≥4，D（k，q）的围长等于k+5.在（k+5）/2为有限域Fq的特征的幂时是成立的。为了进一步研究猜想A，我们又给出了二项式系数Ck，s=(k+s)!/k!+s!在有限域Fq中的一个推广θb(k,s)=C「s/h」,「k/h」smod h∏j=1 bk+j-1/bj-1,其中b为F*q中的一个h阶元素，s modh表示使得h整除s-s mod h的最小非负整数。我们得到了关于推广的二项式系数θb(k，s）的一系列恒等式。进一步，利用这些恒等式我们计算了当路径上的属于同一顶点集合的相邻顶点的颜色差为等比数列时从全零向量出发可以到达的顶点的坐标，并由此证明了猜想A在(k+5)/2为有限域Fq的特征的幂与q-1的因子的乘积时是成立的。这是当前关于猜想A的最好研究结果。
　　通过将顶点向量除颜色以外的各分量以二元序列集合Ω中的元素来标记的方法，我们还提出了一类新的二部图Γ（Ω,q）:顶点集L(Ω)和R(Ω)皆为Fq上的|Ω|+1长序列的集合，[l]∈L(Ω)和∈R(Ω)在Γ（Ω,q）中邻接当且仅当lα0+ rα0=r*lα，若α0∈Ω,lβ1+rβ1=l*rβ，若β1∈Ω,这里*是一个不在Ω中的一个特别的符号，l*和r*表示顶点的颜色，并且规定*0=*1=η为空序列。二部图Γ(Ω，q)是二部图D(k,q)的一种推广。首先我们给出了二部图Γ(Ω，q)的连通分支上的一些不变量:若α与其逆序序列(α)互异并且都包含于Ω，则存在一个在Γ(Ω，q)的连通分支上不变的量α(·，α).并且这些不变量在不同的连通分支上是可以自由取值的。由此我们得到Γ(Ω，q)的连通分支数的一个下界。然后，我们给出了Γ(Ω，q)的一些自同构，得到了Γ(Ω，q)具有不同层次的对称性所需满足的一些充分条件。特别，我们给出了Γ(Ω，q)是边传递的二部图的一个条件:如果对Ω中任何二元序列，删除其第一个比特或最后一个比特或两个连续的相同比特中的一个比特所得到的序列仍在Ω中，则二部图Γ(Ω,q)是边传递的。我们还对Γ(Ω，q)的始于除颜色以外各坐标都等于零的顶点的路径进行了研究，得到了这样的路径上的各顶点用所经过的顶点的颜色表示的显式表达公式。进一步，我们利用这些表达式，证明了Γ（Ω,q）中的一些特殊环的不存在性。最后，我们得到了Γ(Ω,q)的围长的一些下界估计。特别，除了连通分支数的准确值以外，关于Γ(Ω，q)中的这些研究结果都可推出有关D（k，q）的最佳结果。

目录

摘要

第一章 绪论

1．1 图的基本概念

1．2 二部图D(k，q)的提出及其主要研究结果

1．3 二部图D(k，q)在极图理论中的应用

1．4 二部图D(k，q)在纠错编码理论中的应用

1．5 二部图D(k，q)在密码学中的应用

1．6 本文的主要工作

第二章 二部图D(k，q)的一个等价构造及其中的路径

2．1 二部图D(k，q)的一个等价构造

2．2 线性变换σ、τ和δ在Fq上的多项式

2．3 二部图∧q中的路径

2．4 路径的显式公式表示

第三章 关于二部图D(k，q)的围长的研究

3．1 二部图∧2，q和∧3，q的围长环

3．2 (k+5)／2=ps时猜想A的证明

3．3 关于二项式系数的一个推广

3．4 (k+5)|2ps(q-1)时猜想A的证明

第四章 二部图D(k，g)的一个推广Γ(Ω，q)

4．1 二部图Γ(Ω，q)的连通分支中的不变量

4．2 二部图Γ(Ω，q)的自同构

4．3 二部图Γ(Ω，q)中的路径

4．4 二部图Γ(Ω，q)中的一些特殊环

第五章 总结和展望

5．1 总结

5．2 展望

参考文献

读博期间发表文章目录

致谢

声明