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

发布时间：2018-11-15 07:52

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

【相似文献】