修 論 文

修 ^士 論文

ラ ^{マ ヌ} ジ _{ャ ン} グラ ^{フ の} 構成^{に つ い て の} 考察

三重 大 学 大 学 院 教 育 学 研 究 科 教 科 教 育 専 攻 数 学 教 育 専 修 2 0 6 M O 1 6

藤^田 友 美

2 0 0 8 年2 月1 2 日

別紙様 式第3

論 文 目 録

三重 大 学 大 学 院 教 育 学 研 究 科

別紙様式第⁴

論 文 要

三重大 学大 学 院教育 学研究^科

教科^顔肴 ^{専 攻 教}学^{教肩 章 .喜} 巌 ^{hY9 ゑ} 泉

この論 文^はラ^マヌ ジャ ング ラ^{フ の}構 成に^ついて考察した結果であ る^. 1 章ではD a Nidoff, Sa r n ak ,

V alette によ る 具体的な ラ^マヌ ジャ ング ラ^{フ の}構成^{につ いて}ま と め た^. 有限で連 結なk^‑r eg^ula r グ ラ^{フ X の,} 全^ての非自明 な 固有 値_p が 糾 ≦² 肺 ⁷ を満たすと き, X を ラ^マヌ ジャ ン グ ラフと

いう^. G を群と す る^{. S} を 空^でな^い G の部分集 合とし, S ⁼ S ¹ が成り 立^っと す る^. 演^,点の集 合

V ^‑ a , 辺の集合 ^{E ‑} ((^x,y) ^{: x,}y ^∈ G _{で y} ^{= x s} と な る ^s ∈S が存在す る) ^{で でき る グ ラフ}

Q(^{a ,S}) ^{を ケ ‑ リ ー グ ラフという. 以 下のグ ラフ を考え る. た だし, ここでSP,り ま 1.3 節で定義 す}

る集 合^であ る^.

(^雷) ^{‑ 1 の羊きの, Sp,q に関す る P S L2(q) のケ ‑ リ ー グ ラフ}

X ^{P'q ‑} g(^PSL2(q)^,Sp,q)

と^, (^苦) ^‑:1 のと き^の, ち,q に 関 す るP G L2'q' ^{のケ ‑ リ ー グ ラフ}

X ^{P'q ‑} Q(^{P GL2}(q)^,Sp,q)

t

は^, 抄^{+ 1})^{‑r e}g^ula r のグ ラ^フ であ り, p

8 < q のと き に^{つ い}ては, どの2 頂 点 も 何本^かの辺 に よっ て

つ な が^{っ て い}る連 結グ ラフであ る^こと が 示 さ れている^. ま た, ラ^マヌジャ ング ラフであ り,

のと き^, 大 き なgi ^{rth と 大 き な}彩 色数^{を 持つ} 良いグ ラフ であ ること が 示 さ れている^.

= 1

2 章では^これ^の頂 点^の群を位 数^{4 の}部 分群^で左から割^っ た も^のに^つ いて考察^{し て い}る, つま りこ こ からは, 鳳 長^の集 合v を群に限 ら ず集 合とし_, 鳳 長^の集合V には右^から 群^G が作用 ^{し て い}る と す る^.

(^雷) ^{‑ 1 のと き, ZP,q をSp,q に関する 町P S L2(q) のケ ‑ リ ー グ ラフと す る･}

Z^{P'q ‑} Q(^H＼^{P S L2}(q)^,Sp,q)^I

(^雷) ^{ニ ー1 のと き, ZP,q をSp,q に関 す る 町P G L2(q) のケ ‑ リ ー グ ラフと す る一}

Z^{P'q ‑} Q(^H＼^{P G L2}(q)^,Sp,q)^･

こ のグ ラ^フは 頂 点推移 的で はな^いが, 也^{+ 1})^‑reg ul a r であ ること には変わ り は な く, X ^P,q の連 結 性 が_p⁸ < q のと き に 示せた^のに 対し て, Z ^P,9 では_p > 5_, p⁷ < q のと き, た だし, p⁷ < q ≦p⁸ に

ついては3,5, l l_, 1 7,2 9,4 1 以 外^のと きに, 連 結^であ ること を 示 す^こと ができ た^. ま た, ル ^ー プ が な^い Z^P,り^こ対し て, p > 5_{, p}⁸ < q を満たす奇 素数p,q で, ラ^{マ ヌ} ジャ ング ラフ であ り^, 良^いグ ラ

フ であ る と^いう^こと を示 す^こと ができ た^.

目 次

序 文

1 グラフ X ^P,q

l.1 グ ラ^{フ ‥ ‥ ‥ ‥ ‥ . . ‥} 1.2 四 元数 . ‥ ‥ ‥ ‥ ‥ . ‥

‥

‥

‥ . ‥ ‥

1.3 グ ラフ X ^P,q と Y^P,q 2 グラ^{フ Z P,q}

2.1 グラフ Z ^P,q と D ^P,q

2.2 グラ^フ Z ^P,q の連 結 性と大き なgi ^{rt h . ‥ . . . . . .}

3 頂 点 推 移 的でないラ^マヌジャ ングラフ

3.1 頂 点 推 移 的^でないf^{a m}il_y ^of ^{e x}_p ^{a n}d^{e r s} と良い グ ラ^フ 3^.2 頂 点 推 移 的でな ^いラ^{マ ヌ} ジャン グ ラ^{フ .}

A p p^{e n} di^x

●●●

1 1 1

1 1 3 5

8 8 19 2 3 2 3 31 3 6

序 文

この論文 は ラ^マ ヌジャン グ ラ^{フ の}構 成に^つ いて考 察し た結 果^であ る^{･ 1} 章^では ^D a vidoff, S a r n ak , Valette[¹】^{に よ る具}

体 的 なラ ^マヌ ジャ ^ン グ ラフ の構 成に^{つ い} てま と め た^. こ こ で いうグ ラ^フと は^, 右の よう な頂 点と, 辺 か ら な るも^{の で}あ る^. グ ラ^フ X ^の全ての頂 点から 同^{じ k} 本 ず^つ 辺 が出てい る と き,

グ_ラフ X は k ^‑r eg ^ula r であ る と^いう^. 右^の例は2 ^‑r eg ^ula r の グ ラ^フで あ る^.

定 義 ^{o .o .1 .} 有 限^で連 結 なk^{‑r e}_g^ula r グラフ X の_, 全て の非 自 明 な 固 有 値_p がIp[ ^≦2 杯 ⁷ を満たすとき, X を ラ^マ ヌ ジャ ^ン グ ラ^フと^い う^.

[

∵

G を群とする^. S を空でな^い G ^の部 分集^{合と し, S = S ‑l が}

成り 立 ^つ とする^. 頂 点^の集 合^{v ‑} G , 辺 の集 合^{E ‑} ((^I,y) ^{‥ x,}y ^∈ G _{で y} ^{‑ x s} となる^s ∈

s が存 在 する) ^{でできる グ ラフQ}(^{G ,S}) ^{を ケ ‑ リ ー グ ラフという･ 以下の グ ラフを考え る･}

た だ し^{, こ こ で} S_p

,q は1 ･3 節^で定 義 する集 合^であ る^･

(ⁱ)^{p ‑ 1 の ときの, Sp,q に関 する PSL2(q) の ケ ‑ リ ー グ ラフ}

X ^{P,q ‑} Q(^PSL2(q)^{, S}p^,q)

と, (^冒) ^{‑ 1 1 の と きの, Sp,q に関 する P G L2(q) のケ ‑ リ ー グラフ}

X ^{P,q ‑} Q(^{PG L2}(q)^{, S}p,q)

は, (p + 1) ^{‑r e}g ^ula r の グラフ であ り, p ≧⁵,p^{8 <} q ^のと き に ^{つ い て}は, どの 2 頂 点 も 何 本か の辺 に よ ^っ て ^つ なが っ てい る連 結 グラフ で あること が 示されてい る^. ま た^, 全^ての v i, Vj ^∈ V で α(^{v i}) ^{‑ V}j となる グ ラフ X の自己同型写像^α が存 在 する とき, 頂 点 推 移 的で あ る と^いうが, こ の グラフは頂 点推 移 的 なグ ラフ であ る^. そ して, X ^P,q の, あ る頂 点か ら 同じ頂 点 ^‑ と ^つなが る道^の数に^{つ い て,} 以 下^の公式が作ら れ た^.

定 理 ^{0 .0 .2} ( ^{トレ ー ス公式})^{. k ‑r e}g^ul^{a r} で連 結 な^{ル ー} プ が ない 単 純 グラ^フを X とする^･ そ

の頂 点^の集 合を V とする^. 全て の m ∈ N U(⁰) ^で

∑ ∑ ^{fm ‑2,,x ‑ (k ‑ 1)}

x ∈V O≦r≦写

た だ し, U m は ^m 次^のチ ^{ェ ビ シ ェ フ}多 項 式, す なわち, m ∈ N U (⁰) ^{で U m}(^{c o sO}) ^‑

sin( ^{m + 1})⁰/ ^{sin O を満たす 式である. こ の公式に対して, ラマヌ ジャ ン予想を使 うこと に}

よ り, p ≧⁵,p^{8 <} q を満たす 奇 素 数_p,q で q が十 分 大き^い とき, グ ラフ X ^P,q は, ラ^マ ヌ ジャ ン グラフで あ ること が 示 され た^. そ して これ が D a vid^o圧, S^{a r n a}k, V^alette[¹] ^{に よ る}

具 体 的 なラ ^マヌ ジャ ング ラ^{フ の}例であ る^. ま た^{, こ こ で}仮 定にな^っ て い る_p⁸ < q は ^{X P,q}

の連 結 性と単 純 性を 示す も^{の で}あり, 連 結で単 純 な グラフ であ れば^この範 囲^でな くとも 成 り 立 ^つ. ま た, あ る頂 点から同 じ頂 点に戻る, いく^つ かの辺 で でき た道をサ ^ー キッ ト と^い

うが, そ^の 中^で最小 ^のも^の を_{g i}^rtb と呼ぶ^. さら に, 隣 接し た2 点が同じ色に な らない よ うに塗り分 ける ときに 必要 な 色^の数^の最小値を彩 色 数とい う^. 当 然, 辺 が増え れば彩 色 数 は大き くなる が, g i^rth は大きく ならな^い. む し ろ 小さ く な^っ て し まうこともあ る^.

以 下 ^の グラフ は X ^3,5_, x ^{3,l l}_, x ^{5,1 1} の グ ラ^{フ で}あ る^. ど れ も連 結グ ラ^フ で あ り, ラ^マ ヌ ジャ ングラフ でもあ る^.

x ^3,5 のグ_ラフ : gi ^{rt h は 6}

X ^{3,1 1} の グ_ラフ : gi^{rth は9}

x ^{5,1 1} のグ_ラフ : g i^rth は 6

近 年, 情 報 化 社 会の発 展に よ り, よ り良^い通信 網が望ま れ て^い る^. 通 信^の途 絶え にく さ だけを考え れば, ど^{の 2} 地 点 も^つ なが^っ ていれば ^一 番 良^いと^いえ る^{. こ}れ は, グラ^{フ で い}

えば^, 任 意^{の 2} 頂 点が隣 接して い る完 全 グラ^フ と^いう^こと で あ る^. 同じ頂 点 数^であ れば,

こ の状 態が ^一 番 彩 色 数が大 きい^. し か し, 現 実に考え る と, これ では経 済 面^{で の}負 担が大 き く なる^. 逆に経 済 面だ けを 求め, ひ と ^{つ の}経 路^です ^{べて の}地 点を カ^{バ ー} し ようとする と,

一 本^の線でな ければ^, 最 初^の例^の よう な形になる^. こ の グラ^フは サ イ ク^ル グラフ で, 同じ 頂 点 数であれば, こ の状 態が ^一 番gi^rt h が大 きい ^. し か しこれ^では経 路が 少な す ぎ^{, どこ} か で ト ラ ブ^ルが起^これば, そ ^の先の通 信が途絶^{えて し まう可能 性が高い . 良い通 信 網は,}

こ の 2 ^つ の相 反 する面を最 大 限に持 ち 合わ せ る通 信 網である と ^いう^こと で あ る^. これ は,

つ ま り, 大_きな_gi^rth と大きな 彩 色 数を あ わ せ持 ^つ グラ^フを作る^こと と同 意^であ る^{. 1 9 5 9} 年に Erd6s に よ り, こ の よう なグ ラ^フが存 在 する^こと は 示されてい る^{. この} よう なグ ラ^フ を良^い グラフと呼ぶ^. グ_ラフ X ^P,q は, p,q が_p⁸ < q, p ≧⁵ を満たす 奇 素 数^で,(^壁)^{q I‑ iJ}

のとき, 大きなgi ^{rt h を持ち, 大き}な彩 色 数^を持^{つ. つ} ま り, こ の条 件^の グラ^フ X ^P,q は良

い グラフ であ る^{. 2} 章からは別^の 良^いグ_ラフ で あ り, ラ^マヌ ジャ ング ラ^{フ で}あ るグ_ラフを 構 成 する^こと に ^{つ い} て考 察を行^っ た^.

2 章^で新た に作^っ たグ_ラフ Z ^P,q の頂 点は X ^P,q の頂 点 ^PSL ₂(^q)^{, PG L2}(^q) ^{を2 .1 節で定 義}

する位 数^{4 の}部 分 群 H で左 か ら割^っ たも^の で あ る^{. この}章か ら次^の よう な グラ^フ を ケ ^‑ リ ^ー グ_ラフと いう^こと にする^. G を群とする^. S を空^でな^い G の部 分集合と し, S ⁼ S ‑¹ が成り 立 ^っ とする^. 頂 点^の集^合 V に は G が右から 作 用 して い る とする^. 頂 点^の集 合 V と 辺 ^の集 合 ^{E ‑} ((^{I, y}) ^{: I,y ∈ V で y ‑ x s となる s ∈ S が存 在 する}) ^{で できる グ ラ}

フ Q(^V,S) ^{を ケ ‑ リ ー グラフということ にする･} (^冒) ^{‑ 1 の と き, ZP,q k Sp,q に関 する}

H＼^{P SL2}(^q) ^{のケ ‑ リ ー グラフ とする･}

Z ^{P'q ‑} Q(^H＼^PSL2(q)^,Sp^,q) ^･

(^冨) ^{ニ ー1 のとき, Z P,q を Sp,q に関 する 町P G L2(q) のケ ‑ リ ー グ ラフとする･}

Z^{P,q ‑} Q(^H ＼^{PG L2}(q)^{, S}p,q)^･

つ ま り, 頂 点^の集合は H＼^{PS L2}(^q)^{, H}＼^{P G L2}(^q) ^{であ り, これ は どちらも 群ではない･ ま}

た^{, この} グ ラ^フは頂 点 推 移 的では な^い. そ^の た め に^{, X P,q で}は頂 点 の集 合に対 応 する群

の単 位元 に ^{つ い ての}み考え れば 良^{か っ た ところ が, そ れ だ けでは}すまず, 様^々 なケ ^{ー ス} に

つ い て考え る 必要ができ た^･ し か し, (^{p + 1}) ^{‑r egula r であ ること に は変わ り はなく, 定理}

2.2.6 では, X ^P,q の連 結 性が_p⁸ < q ^のと き に 示 せ た^のに対して, Z ^P,q では_p ≧^5, p

7 < q のとき, た だ し, p⁷ < q ≦p⁸ に^つ いては_p が 3, 5_, l l_, 17, 2 9_, 4 1 以外^のときに, 連 結^であ る^こと を 示す^こと ができ た^. ま た, ル ^ー プ がな^{い ZP,q} に対して, X ^P,q 同様に, あ る頂 点か ら同じ頂 点 ^‑ と^つなが る道^の数に^つ い て以 下^の 公式が できた^･ た だ し, sQl(p ^m)^{, S}Q2(p^m)

は ^{1 .}3 節, 3^.1 節で定 義 する数であ る^.

定理 0.0.3 (^{ZP,q の トレ ー ス公式})^{. ル ー プ がない Z P,q で}卜^打＼^Vl ^{‑ n と お き,} p,q を_p ≧ 5, p⁸ < q を満たす 奇 素 数とする^.

q + 1 2(^{q ‑ 1})

2(q + I)

と おく^･ 全て の m ∈ N U(⁰) ^に対し

x∈ H＼^{V O}≦^r≦^m/²

̲P q 里

q P̲

q P̲

q

‑ 1 か ^つ _p ^≡1 ( ^{m od 4}) ^{の と き})

‑ 1 か つ p ^≡3 ( ^{m od 4}) ^{の と き})

ニ ^ー 1 か ^つ _p ≡1 (^{m od 4) の と き})

‑ ‑ ¹ か ^つ _p ^≡ 3 (^{m od 4}) ^{の と き})

n 3

2: ∑ ^{f‑ ‑2r,I ‑}芸^{sQl(pm) '}言^{c v sQ2(p m) ･}