關(guān)于一類代數(shù)二部圖的研究.pdf

1、具有高度對稱性和很大圍長的圖在極圖理論、糾錯編碼理論、密碼學(xué)、網(wǎng)絡(luò)通信以及量子計算等各種不同的領(lǐng)域內(nèi)具有重要應(yīng)用。對于素數(shù)冪q和整數(shù)k≥2，1995年Lazebnik和Ustimenko利用李群的根系在[16]中提出了一個q-正則的代數(shù)二部圖D(k，q)，它是邊傳遞的并且圍長不小于k+4.自提出以來，這個二部圖得到了廣泛的關(guān)注和研究，不但為一系列的極圖問題提供了最佳的上界或下界估計，也為具有優(yōu)異糾錯性能的LDPC碼提供了一種很好的構(gòu)造方

2、法，還可以用來設(shè)計快速的對稱密碼算法和公鑰密碼算法。本學(xué)位論文進一步研究二部圖D(k，q)的性質(zhì)，給出了其中的路徑的顯式表達公式，證明了關(guān)于其圍長的一個猜想在幾種新的情形下的正確性，提出了D(k，q)的一個新的推廣Γ(Ω，q)，深入討論了推廣的二部圖Γ（Ω,q）的連通分支數(shù)、路徑及其表示、自同構(gòu)、對稱性和圍長。
　　我們首先給出了二部圖D(k，q)的一個等價構(gòu)造Λk,q,研究了F∞q上的三個線性變換σ、Τ和δ的一些性質(zhì)，討論了它們

3、在Fq上的多項式的唯一表示問題。然后我們利用這些線性變換改寫了二部圖Λk，q的鄰接關(guān)系，得到了Λk,q中的路徑上的頂點之間的一個遞推關(guān)系。進一步我們還利用齊次多項式ρs（w1，w2,…，wn），給出了Λk,q中始于全零向量的路徑上的各頂點用所經(jīng)過的頂點的顏色（第一個坐標(biāo)）表示的顯式表達公式。特別，當(dāng)這樣的路徑上的屬于同一頂點集合的相鄰頂點的顏色之差取定值時，我們計算了路徑上各頂點的所有坐標(biāo)，并由此證明了關(guān)于D(k，q)的圍長的猜想A:<

4、br>　　對所有的奇數(shù)k≥3和素數(shù)冪q≥4，D（k，q）的圍長等于k+5.在（k+5）/2為有限域Fq的特征的冪時是成立的。為了進一步研究猜想A，我們又給出了二項式系數(shù)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的最小非負整數(shù)。我們得到了關(guān)于推廣的二項式系數(shù)θb(

5、k，s）的一系列恒等式。進一步，利用這些恒等式我們計算了當(dāng)路徑上的屬于同一頂點集合的相鄰頂點的顏色差為等比數(shù)列時從全零向量出發(fā)可以到達的頂點的坐標(biāo)，并由此證明了猜想A在(k+5)/2為有限域Fq的特征的冪與q-1的因子的乘積時是成立的。這是當(dāng)前關(guān)于猜想A的最好研究結(jié)果。
　　通過將頂點向量除顏色以外的各分量以二元序列集合Ω中的元素來標(biāo)記的方法，我們還提出了一類新的二部圖Γ（Ω,q）:頂點集L(Ω)和R(Ω)皆為Fq上的|Ω|+1長

6、序列的集合，[l]∈L(Ω)和∈R(Ω)在Γ（Ω,q）中鄰接當(dāng)且僅當(dāng)lα0+ rα0=r*lα，若α0∈Ω,lβ1+rβ1=l*rβ，若β1∈Ω,這里*是一個不在Ω中的一個特別的符號，l*和r*表示頂點的顏色，并且規(guī)定*0=*1=η為空序列。二部圖Γ(Ω，q)是二部圖D(k,q)的一種推廣。首先我們給出了二部圖Γ(Ω，q)的連通分支上的一些不變量:若α與其逆序序列(α)互異并且都包含于Ω，則存在一個在Γ(Ω，q)的連通分支上不變的

7、量α(·，α).并且這些不變量在不同的連通分支上是可以自由取值的。由此我們得到Γ(Ω，q)的連通分支數(shù)的一個下界。然后，我們給出了Γ(Ω，q)的一些自同構(gòu)，得到了Γ(Ω，q)具有不同層次的對稱性所需滿足的一些充分條件。特別，我們給出了Γ(Ω，q)是邊傳遞的二部圖的一個條件:如果對Ω中任何二元序列，刪除其第一個比特或最后一個比特或兩個連續(xù)的相同比特中的一個比特所得到的序列仍在Ω中，則二部圖Γ(Ω,q)是邊傳遞的。我們還對Γ(Ω，q)的始于