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

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

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

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

4、br>　　對(duì)所有的奇數(shù)k≥3和素?cái)?shù)冪q≥4，D（k，q）的圍長(zhǎng)等于k+5.在（k+5）/2為有限域Fq的特征的冪時(shí)是成立的。為了進(jìn)一步研究猜想A，我們又給出了二項(xiàng)式系數(shù)Ck，s=(k+s)!/k!+s!在有限域Fq中的一個(gè)推廣θb(k,s)=C「s/h」,「k/h」smod h∏j=1 bk+j-1/bj-1,其中b為F*q中的一個(gè)h階元素，s modh表示使得h整除s-s mod h的最小非負(fù)整數(shù)。我們得到了關(guān)于推廣的二項(xiàng)式系數(shù)θb(

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

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

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