• 検索結果がありません。

9 4 I 9:00 9:20 9:20 9:40 :M L 0:00 :00, :0 2:0 2:0 3:40 II 3:40 4:00 4:00 4:20 4:40 5:40, 5:50 6:50 7: II 9:5 9:35 9:35 9:55 Colored hook formu

N/A
N/A
Protected

Academic year: 2021

シェア "9 4 I 9:00 9:20 9:20 9:40 :M L 0:00 :00, :0 2:0 2:0 3:40 II 3:40 4:00 4:00 4:20 4:40 5:40, 5:50 6:50 7: II 9:5 9:35 9:35 9:55 Colored hook formu"

Copied!
35
0
0

読み込み中.... (全文を見る)

全文

(1)組合せ論サマースクール 2007 プログラム http://staff.aist.go.jp/k.nuida/YS07/. 2007 年 9 月 3 日(月) – 2007 年 9 月 5 日(水) 沖縄、カルチャーリゾートフェストーネ( http://festone.jp/ ) 9 月 2 日(日) 19:30 – 21:00. ウェルカムパーティー. 9 月 3 日(月) 8:55 – 9:00. 開会挨拶. セッション1:組合せ論と代数 9:00 – 9:20 上條 亮(北海道大学) 有限群上の方程式の解の個数 9:20 – 9:40 冨江 雅也(筑波大学) poset 上の組合せ論 9:40 – 10:00 島倉 裕樹(千葉大学) 頂点作用素代数と三重偶符号化. 入門講義1:「点集合、凸集合、アレンジメント」 10:20 – 11:20, 11:30 – 12:30 12:30 – 14:30. 岡本 吉央(豊橋技術科学大学). 昼食. 入門講義2:「組合せデザインとその情報通信への応用」 14:30 – 15:30, 15:40 – 16:40. 神保 雅一(名古屋大学). セッション2:グラフ構造 17:00 – 17:20 潮 和彦(近畿大学) 素数 p と法 q の最小の原始根 g 17:20 – 17:40 宮内 美樹(NTT) グラフのトラックレイアウト 17:40 – 18:05 篠原 英裕(大阪大学) labeled tree の集合と chordal graph の集合の対応について 18:05 – 18:25 渡辺 有祐(統計数理研究所) ビリーフプロパゲーションとループ展開 18:25 – 19:50 夕食. セッション3:組合せ論と表現論 I 19:50 – 20:10 岡田 聡一(名古屋大学) Trace generating functions of plane partitions 20:10 – 20:30 石川 雅雄(鳥取大学) Catalan 数, Motzkin 数, Schr¨oder 数の Hankel 行列式と、その q-analogue 20:30 – 20:50 小須田 雅(琉球大学) GAP による Partition 代数の計算.

(2) 9 月 4 日(火) セッション4:組合せ論と情報テクノロジー I 9:00 – 9:20 縫田 光司(産業技術総合研究所) 電子透かし符号に関するある列挙問題 9:20 – 9:40 萩原 学(産業技術総合研究所) 非正則疑似巡回低密度パリティ検査符号の量子符号化にまつわる組合せ論的アプローチ. 入門講義3:「離散凸解析入門:M 凸関数と L 凸関数」 10:00 – 11:00, 11:10 – 12:10 12:10 – 13:40. 塩浦 昭義(東北大学). 昼食. セッション5:組合せ論と情報テクノロジー II 13:40 – 14:00 藤原 祐一郎(名古屋大学) 畳み込み型レスポンスデータ圧縮回路の組合せ論的設計法 14:00 – 14:20 藤原 洋志(関西学院大学) 正多角形領域に対するオンライン追跡問題. 入門講義4:「曲面上のグラフの染色数」 14:40 – 15:40, 15:50 – 16:50 17:00 –. 中本 敦浩(横浜国立大学). 懇親会. 9 月 5 日(水) セッション6:組合せ論と表現論 II 9:15 – 9:35 沼田 泰英(北海道大学) 対称群のある表現達の指標の重み付き和の組合せ論的表示について 9:35 – 9:55 仲田 研登(大阪大学) Colored hook formula for a generalized young diagrams. セッション7:組合せ論と幾何学 10:15 – 10:35 徳重 典英(琉球大学) A wild configuration chase 10:35 – 11:00 上別府 陽(筑波大学) Homotopy type of the box complexes of graphs without 4-cycle 11:00 – 11:20 村井 聡(大阪大学) Algebraic shifting of strongly edge decomposable spheres 11:20 – 11:40 八森 正泰(筑波大学) 3 次元球面・球体の三角形分割と結び目のその後 11:40 – 11:45 閉会挨拶. 実行委員長 実行委員. 組合せ論サマーセミナー 2007 実行委員会 八森 正泰(筑波大学) 副委員長 上條 亮(北海道大学) 小須田 雅(琉球大学) 萩原 学(産業技術総合研究所) 島倉 裕樹(千葉大学) 縫田 光司(産業技術総合研究所).

(3) 有限群上の方程式の解の個数について 北海道大学大学院理学院 上條 亮. ∗. 有限群論の研究において,有限群上の方程式の解の個数や部分群の個数を調べることは,有限単純 群の分類の研究が主流となる以前に盛んであった.ただ,今や時代遅れと思われるこの研究も,最近 になり,新たな問題や幾何学的手法や組合せ論的手法を用いた別の方向からのアプローチがされてい る.この研究において大きな問題の一つに次の予想である. 予想(Asai-Yoshida[3]). A, G を有限群とする.このとき, |Hom(A, G)| ≡ 0. mod gcd(|A/A0 |, |G|). ここで,A0 は,A の交換子群とする.. A がアーベル群のとき成り立つことは吉田が示した [2].また,この予想は,浅井,庭崎,竹が原ら により,A がいろいろな群で成り立つことがわかっているが,一般的にはまだ未解決である. また,A を n 次巡回群 Cn とすると,次の Frobenius の定理となる. 定理 F (Frobenius の定理) #. G を有限群,n ∈ N とする.このとき, {x ∈ G |xn = 1} ≡ 0. mod gcd(n, |G|). が成り立つ. 一方で,次のような有限群上の方程式の解の個数に関する合同式がある. 定理 I (Iwasaki [1]). G を有限群,H を G の部分群,n ∈ N とするとき, #. {x ∈ G|xn ∈ H} ≡ 0. mod |H|. この定理は Frobenius の定理を含んでいない.含む形に改良できないかというのが私の課題の一つ である.このことについて今まで得られた結果を紹介する. まず,有限群 G のどのような元が n 乗するとその部分群 H の元になるのだろうかと見てみた結果, 次の定理を得た. 定理 1 G を有限群,H をその部分群,n ∈ N とする.G の任意の元 σ に対して, #. {x ∈ HσH |xn ∈ H} ≡ 0. が成り立つ. ∗ 博士後期課程. 2 年,E-mail:kamijo-a@mail.sci.hokudai.ac.jp. mod |H|.

(4) 定理 1 は,さらに拡張することが出来る. 定理 2 G を有限群,H をその部分群,n ∈ N とする.G の任意の元 σ, τ に対して, #. {x ∈ HσH |xn ∈ Hτ H} ≡ 0. mod |H|. が成り立つ. 岩崎史郎氏との共同研究で,定理 1 を置換群的に解釈して証明することが出来た.それは,次の定 理を証明することで解決する. 定理 3 G を有限集合 Ω 上の有限可移置換群とし,n を 2 以上の任意の自然数とする.a ∈ Ω を任意に 一つとり,aσ 6= a となる σ ∈ G を任意に一つとって固定する. 1. Ga := {g ∈ G|ag = a}, Ga,aσ := {g ∈ G|ag = a, (aσ )g = aσ }, Ga n := {x ∈ G|xn ∈ Ga } とする とき, 1. |Ga n ∩ Ga σ| ∈Z |Ga,aσ | が成り立つ. また,Iwasaki の定理を補題 4 の形に拡張することが出来る (佐藤純二氏との研究). これは,Frobenius の定理を含む Iwasaki の定理の改良に影響を与えると考えられる.. ˜ a := G を有限群,H を G の部分群とする.任意の G の元 a に対して,H. \. ai. H と定義する.た. i=0. ˜ a } とする.この集合 C˜a を a H := ai Ha−i とする.このとき,C˜a := {haδh−1 | h ∈ H δ ∈ H を含む弱い H-共役類とよぶことにする.. だし,. ai. 補題 4 G を有限群,H をその部分群とする.G の任意の元 x に対して,x を含む弱い H-共役類を C˜x とする.このとき,G は,弱い H-共役類で分割できる.. G = C˜x1 ∪ C˜x2 ∪ · · · ∪ C˜xr. (disjoint union).. (ここで,x1 = 1G としてよい). また,(C˜xi )n := {αn |α ∈ C˜xi } とすると, #. {x ∈ G|xn ∈ H} = |H| ×. #. { i |(C˜xi )n = C˜1G }. が成り立つ.. 参考文献 [1] S.Iwasaki, ”A Note on the nth Roots Ratio of a Subgroup of a Finite Group”,Jounal of Algebra 78 (1982), 460-474 [2] T.Yoshida, |Hom(A, G)|,J.Algebla 156(1993) 125-156 [3] T.Yoshida and T.Asai, |Hom(A, G)|. ,J.Algebra 160(1993) 273-285.

(5) Poset における組み合わせ論 冨江 雅也 筑波大学数理物質科学研究科博士後期課程2年. 1. これまでにしたこと 1990年前半 Bjorner は順序の入っていない有限集合から定まる Factor-order, Subword-order. に関して考察を行い Mobius 関数を計算した。その結果を踏まえて最近2006年 Bjorner, Sagan,. Vatter は Rooted-forest(各 component が最小元を持つ tree 構造であるような Poset) から Generalizedsubword-order を定義し同様に Mobius 関数を計算した。いっぽう同じ論文で彼らは Rooted-forest でない場合について以下ように予想を立てていた。 Conjecture 1   P := {a, b, c | a < c, b < c } とする。このとき P から定まる Generalizedsubword-order Pb および Mobius 関数 µ に関して µ(ai , cj ) = Ti+j (X)|X j−i f or 0 ≤ i ≤ j が成り立つ。但し {Tn (X) | n ∈ N} は第一種 Chebyshev 多項式である。 その予想に対して筆者は以下の形で肯定的に解決した s (X) を以下で特徴付けられる多項式とする。(s = 2 Definition 1 s (≥ 2), m ∈ N としたとき、Tm のときは Chebyshev 多項式となる。) (1)  T0s (X) = 1, T1s (X) = (s − 1)X s s s (X) + Tm+2 (X) = sX · Tm+1 (X) (2)  Tm s Tm (X) を用いて Ps = {a1 , · · · as , c | ai < c, f or i = 1, · · · r} のメビウス関数を記述した。. Theorem 1 s(≥ 2), 0 ≤ m ≤ n ,{am } ∈ {ai1 · · · aim | i1 , · · · im ∈ {1, · · · s}} とする。このとき s µ({am }, cn ) は Tm+n (X) における X n−m の係数になる。. 2. これからしたいこと. Finite かつ Graded な poset に対して ab-index 及び Quasi-symmetric-function(以下 Qsym と略 記) を定義することができる。その中でも Euler poset 等はより良い c = a + b, d = ab + ba とした cdindex を持つことが知られている。一方 Stembridge は P-partition を拡張した Enriched-P-partition なるものを考えそれらの間に Stembridge map を定義した。このとき cd-index というものは Qsym の言葉に翻訳すると Enriched-P-partition に相当するもので Peak-algebra と呼ばれるものになって いる。また Billera, Ehrenborg, Readdy は超平面配置 (より一般的に oriented matroid) から導かれ る Poset の ab-index はそれらの Intersection lattice の ab-index に c-2d index を作用させたものであ 1.

(6) る事を発見した。そして最近 Hetyei は Poset における Chebyshev 変換を定義しその性質を調べた。 さらに Billera, Ehrenborg, Hsiao, Readdy, Willigenburg らによって Stembridge map, c-2d index 及び Chebyshev 変換の間に密接な繋がりがあることが示唆されている。講演ではいくつかの open. problem とともにこの分野についてお話します。. 2.

(7) 頂点作用素代数と三重偶符号 島倉 裕樹 (Hiroki Shimakura) 千葉大学大学院理学研究科. e-mail: shima@math.s.chiba-u.ac.jp. 序 頂点作用素代数 (VOA) はある種の公理を満たす代数的な (無限個の) 積構造を持つ無限 次元線形空間である. 組合せ論的対象物との関係は古くから知られていて, 例えば格子や 符号に付随する VOA がある. また, デザインやグラフを用いて VOA の対称性を理解す る手法が提案されるなど, 組合せ論的な手法や対象物を用いた研究が活発にされている. 今回はその中でも二元線形符号について考える. 二元線形符号に付随する VOA の拡大 である枠付き VOA はモンスター単純群を自己同型群に持つムーンシャイン加群などの 良い例を大量に含む重要なクラスである. 枠付き VOA は二元線形符号を用いて記述され るため, 符号の問題に帰着させて VOA の性質を調べることが基本的な手法の一つとなる. 最近, 枠付き正則 VOA の研究には本稿で述べる三重偶符号が重要な役割を果たすことが 台湾の国立成功大学の Lam 氏と愛知教育大の山内氏の研究によって明らかにされた. こ れを動機として, 筆者, Lam 氏と上武大学の別宮氏によって三重偶符号の共同研究を行っ ており, その一部をここで紹介する.. 1. 準備. 簡単に符号といくつかの言葉の定義からはじめよう. 長さ n の k 次元二元線形符号 (binary linear code) C とは F2 上の n 次元線形空間 Fn2 の k 次元部分空間のことを いう. 今後, 二元線形符号のみを扱うので, 略して単に符号ということにする. Fn2 の基底 ∑ ci ei を (c1 , c2 , . . . , cn ) と記述する. 二つ {e1 , e2 , . . . , en } を固定しておき, Fn2 の元 c = の符号が同型であるとは, この基底の元の置換の作用によって一致することをいう. Fn2 の 元 c の重さ (weight) とは 0 でない成分の数であり wt(c) と書く. 符号が重偶 (doubly even) であるとは, 全ての元の重さが 4 で割り切れることをいい, 三重偶 (triply even) であるとは すべての元の重さが 8 で割り切れることをいう. Fn2 上には自然な内積 h, i が ∑n ある. すなわち, x, y ∈ Fn2 に対して, hx, yi = i=1 xi yi mod 2 である. 符号 C に対し て, C ⊥ = {x ∈ Fn2 | hx, yi = 0 ∀y ∈ C} を双対符号 (dual code) という. 符号 C が自. 1.

(8) 己直交 (self-orthogonal) とは, C ⊂ C ⊥ を満たすことをいい, 自己双対 (self-dual) とは C ⊥ = C を満たすことをいう. 長さ n1 の符号 C1 と長さ n2 の符号 C2 の直和とは長さ n1 + n2 の符号 C1 ⊕ C2 である1 . また, 自明でない二つの符号の直和で表せない符合を分 解不可能な符号という.. 2. 極大三重偶符号の構成と分類. まず, 写像 ϕ : Fn2 → F2n 2 , c 7→ (c, c) を考える. 長さ n の符号 C に対して, 長さ 2n の符 n n 号 Φ(C) を F2 hϕ(C), (1 , 0 )i と定義する. 極大三重偶符号の構成法としては, 次がある. 命題 2.1. C を分解不可能な重偶自己双対符号とする. このとき, Φ(C) は分解不可能な 極大三重偶符号2 である.. VOA の研究の立場から, 次の問題の解決が重要である. 長さが 16 の倍数である三重偶符号の分類をせよ. 特に極大なものを分類せよ. 次のことが計算機を用いて確かめられている. 命題 2.2.. (1) 長さ 16 の極大三重偶符号は Reed-Muller 符号 RM (1, 4) と同型になる3 .. (2) 長さ 32 の極大三重偶符号は RM (1, 4) ⊕ RM (1, 4) と Φ(d+ 16 ) のいずれかと同型に + なる. ただし, d16 は長さ 16 の分解不可能な自己双対重偶符号である.4 したがって, 長さ 48 の極大三重偶符号の分類が当面の目標となっている. まず, 長さ 24 の分解不可能な自己双対符号は 7 個ある. よって, 命題 2.1 を適用することで 7 個の長さ 48 の極大三重偶符号が得られる. また, 命題 2.2 から直和として 2 個の長さ 48 の極大三 重偶符号が得られる. 現在のところこれら 9 個以外は知られていない5 . ゆえに, 長さ 48 の極大三重偶符号はこのいずれかに同型であることを示す方針で研究を進めている. 簡単に現在得られている結果について紹介する. 次の補題は具体的な計算から得られる. 補題 2.3. 長さ 48 の極大三重偶符号は重さ 24 の元を含む. この補題と長さ 24 の極大三重偶符号の分類を用いることで次の結果を得ている. 命題 2.4. 長さ 48 の極大三重偶符号の次元は 16 以下である. 等号が成立するのは, RM (1, 4) ⊕ RM (1, 4) ⊕ RM (1, 4) と同型であるときに限る. しかし, まだ計算機を用いて分類を完了させられる状況にない. もうしばらく理論的な 考察によって研究を進める必要があると思われる. 1 n1 +n2 F2 2. n2 1 の基底としては Fn 2 , F2 のそれぞれの基底の和集合を考えている C の長さが必然的に 8 の倍数となるので, Φ(C) の長さは 16 の倍数である. 3 H8 で [8, 4, 4] ハミング符号を表すとすると, RM (1, 4) ∼ = Φ(H8 ) である 4 長さ 16 の分解不可能な自己双対重偶符号は同型を除いて唯一つである. 5 実は長さが 16 の倍数の分解不可能な極大三重偶符号は命題 2.1 で得られるものしか知られていない.. 2.

(9) 素数pと法pの最小の原始根g 潮 和彦 (近畿大学理工学部情報学科) Theorem F. Let p be prime and a be integer. Then ap ≡ a (mod p). Corollaly F1. Let p be prime and (a, p) = 1. Then ap−1 ≡ 1 (mod p). Corollaly F2. Let p be prime and (a, p) = 1. Then sap−1 ≡ s (mod p) for 1 ≤ s ≤ p − 1. Definition. When san−1 ≡ s (mod n), let ai = sai−1 mod n (i = 1, 2, ..., n) for 1 ≤ s ≤ n − 1. Find the first i (i = 2, 3, ..., n) such that ai = s. Put the i be L. Then the sequence a1 (= s), a2 (= sa), a3 (= sa2 ), ..., aL (= s) is called an L-orbit starting s. When there exist (n − 1) L-orbits starting 1, 2, ..., n − 1, we say that n admits L-orbits. Note. Let p be prime. It is a widely known result that p admits p-orbits and that a is called a primitive root w.r.t. mod p. Especially, the least a denoted g is called a least primitive root w.r.t mod p. Example 1. (p, g) = (2, 1), (3, 2), (5, 2), (7, 3), (11, 2), (13, 2), (17, 3), (19, 2), (23, 5), (29, 2), (31, 3), (37, 2), (41, 6), (43, 3), (47, 5), (53, 2), (59, 2), (61, 2), (67, 2), (71, 7), (73, 5), (79, 3), (83, 2), (89, 3), (97, 5). (p, g) = (5, 2) p-orbit : 1, 2, 4, 3, 1 (p − 1)-cycle C = (1, 2, 4, 3). (p, g) = (7, 3) p-orbit : 1, 3, 2, 6, 4, 5, 1 (p − 1)-cycle C = (1, 3, 2, 6, 4, 5). Definition. Let Kn∗ denote the symmetric complete digraph of n vertices. The symmetric complete multi-digraph λKn∗ is the symmetric complete digraph Kn∗ in which every edge is taken λ times. Let Ck be the directed cycle on k vertices.The Ck -t-foil is a digraph of t edge-disjoint Ck ’s with a common vertex. When λKn∗ is decomposed into edge-disjoint sum of Ck -t-foils, we say that λKn∗ has a Ck -t-foil decomposition. Moreover, when n = (k − 1)t + 1 and every vertex of λKn∗ appears in the same number of Ck -t-foils, we say that λKn∗ has a tightly balanced Ck -t-foil decomposition. This decomposition is a type of resolvable Ck -foil designs. Example 2. (n, g) = (13, 2) n-orbit : 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1 (n − 1)-cycle C = (1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7). C5 -3-foil = (13, 1, 2, 4, 8) ∪ (13, 3, 6, 12, 11) ∪ (13, 9, 5, 10, 7). C5 -3-foil = (13, 2, 4, 8, 3) ∪ (13, 6, 12, 11, 9) ∪ (13, 5, 10, 7, 1). C5 -3-foil = (13, 4, 8, 3, 6) ∪ (13, 12, 11, 9, 5) ∪ (13, 10, 7, 1, 2). C5 -3-foil = (13, 8, 3, 6, 12) ∪ (13, 11, 9, 5, 10) ∪ (13, 7, 1, 2, 4). ∗ . These C5 -3-foils comprise a tightly balanced C5 -3-foil decomposition of 5K13 Conjecture. λKn∗ has a tightly balanced Ck -t-foil decomposition if and only if λ ≡ 0 (mod k) and n = (k − 1)t + 1.. Department of Informatics, Faculty of Science and Technology, Kinki University, Osaka 577-8502, JAPAN. Email:ushio@info.kindai.ac.jp Tel:+81-6-6721-2332 (ext. 5409) Fax:+81-6-6727-2024.

(10) グラフのトラックレイアウト 宮内美樹 日本電信電話株式会社. NTT. コミュニケーション科学基礎研究所. グラフ G=(V,E)の頂点集合 V を 2 つの部分集合 A と B に分けて,G の辺がすべて A の頂点と B の頂点とを結ぶ辺になっているようにできるとき G を 2 部グラフという.この分割集合 A, B を 部集合と呼び,A, B の頂点の個数がそれぞれ m, n のとき,G = Gm,n で表す.もし G が A の頂点 と B の頂点を結ぶ辺を全て含んでいれば G は完全 2 部グラフと呼ばれ G=Km,n で表す. グラフ G の辺上に次数 2 の頂点を幾つか付け加えて得られるグラフを G の細分という.付け 加えられた次数 2 の頂点を細分点と呼ぶ.グラフはまたそれ自身の細分ともみなす. 集合 S の全順序というのは,S 上の全順序≤σのことをさす.集合 S はσによって順序付けられ ているというように,全順序≤σのことを簡単に全順序σとも書くことにする.グラフ G の頂点順 序というのは,頂点集合 V(G)上の全順序σのことである. 頂点集合 V(G)の分割{Vi : 1≤ i≤ t}が G の頂点 t-彩色であるとは,任意の辺 vw∈E(G)に対して, v ∈Vi かつ w ∈Vj ならば i≠ j が成り立つときのことを言う. G の頂点 t-彩色{Vi : 1≤ i≤ t}の各 部分集合 Vi が <i によって順序づけられているとき,順序集合 (Vi, <i) をトラックと呼び,{(Vi, <i) : 1 ≤ i ≤t} を G の t-トラック割り当て と呼ぶ.各部分集合での順序がわかっているときは, 単にトラック割り当てを{ Vi : 1 ≤ i ≤ t}とも表記する. トラック割り当てにおける X-交差とは,異なる i と j で v <i x かつ y <j w となるような 2 辺 vw と xy のことを言う.E(G)の分割{Ei : 1 ≤ i ≤ k} のことを,G の辺 k-彩色と言う.辺 vw ∈ Ei は色 i に彩色されていると言う.グラフ G の (k, t)-トラックレイアウトとは,G の t-トラッ ク割り当てと,同色の X-交差を持たない G の辺 k 彩色からなるものを言う.(k, t)-トラックレイ アウトを持つグラフのことを (k, t)-トラックグラフという. グラフ G の頂点の順序において,L(e) と R(e) をそれぞれ,G の辺 e ∈ E(G)の両端点で,L(e) <σR(e)を満たすものとする.L(e) <σL( f )なる,異なる 2 辺 e, f ∈E(G) に対して,e と f がネスト しているとは, L(e) <σL( f ) <σR( f ) <σR(e) を満たすときをいう. グラフ G のキューとは, 辺集合 E(G)の部分集合 E’⊆ E(G) で E’ のどの辺もネストしていな い部分集合を言う.グラフ G の k-キューレイアウトとは,G の頂点順序σと辺集合 E(G)の分割 {Es : 1 ≤ s ≤ k} からなるセットで,各分割集合 Es が頂点順序σに対して,キューとなっているも のをいう.k-キューレイアウトを持つグラフを k-キューグラフと呼ぶ.グラフ G のキュー数 qn(G)とは G が k-キューグラフとなるような最小の k のことである.. 今回は,グラフの細分の(k,2)-トラックレイアウトについてキュー数と関連付けられた結果を 紹介するとともに最新の成果を発表する..

(11) Labeled tree の集合から作る弦グラフの集合 篠原英裕(大阪大学情報科学研究科M2). グラフ G が弦グラフであるとは、任意の長さ 4 以上のサイクルが弦を持つこと である。弦グラフにはさまざまな特徴が存在する。たとえば、隣接点の集合がク リークである点を 1 つずつ消していくことによりすべての頂点を消すことができ ることなどがある。今回扱うクリーク木の存在もまた著しい特徴の一つである。木 T が G のクリーク木であるとは、(1)T の頂点集合は G の極大クリークの集合であ り、(2)T で Qi が Qh と Qj を結ぶ path の上に存在するならば Qh ∩ Qj ⊂ Qi が成 立する、ことを言う。しかしながら弦グラフが与えられたとき一般にはクリーク 木は一つとは限らない。したがって弦グラフに対してクリーク木と呼ばれるラベ ル付き木の集合が対応していると考えるほうが正しい。逆にラベル付き木の集合 に対して、それらをクリーク木全体とするような弦グラフが存在するか否かとい う問題を考えるのも自然である。この問題に対しては次の定理を得た。. Theorem 1. (H. Shinohara 2007 preprint) L を頂点集合 V (|V | = k) を共有する ラベル付き木の集合とする。このとき L をクリーク木全体として持つ弦グラフが 存在する必要十分条件は「任意のペア L1 , L2 ∈ L に対して L1 で辺であって L2 で 辺でない頂点のペア u, v に対して L2 上の u と v を結ぶ任意の点 w をとる。この とき w が L1 \uv において u と同じ連結部分に入っているならば L1 ∪ vw\uv も L の元である。」 弦グラフにはさまざまな応用が存在するので、この条件を満たす与えられたラベ ル付き木の集合に対して実際に弦グラフを列挙するのも有意義な問題である。 (も ちろんクリーク数と極大クリークの数を固定した弦グラフをすべて持ってきてそ れらのクリーク木全体が L であるか否か判定するという効率の悪い方法は自明に 存在するが。)今回は minimal separator に属する点集合を最小にする弦グラフの 構成アルゴリズムを示し、さらにその弦グラフをクリーク木の集合を保ったまま 変形する方法をすべて記述する。可能ならば列挙アルゴリズムを用意したい。. 1.

(12) 分配関数のループ展開 渡辺 有祐∗. まえがき. 1 1.1. 今日の話のテーマ. 播法による周辺確率分布の近似性能について知りたいの だが、煩雑さを避けるため分配関数の近似について研究 している。. 「(有限)グラフ上で定義された確率分布」の分配関 数(規格化定数)を求める問題が研究のテーマである。 たとえば、平面格子上の Ising Model における Gibbs 確 率分布は「グラフ上で定義された確率分布」の典型例で ある。その分配関数を求めることは自由エネルギーを求 めることに対応している。 分配関数の計算はすべての状態についての足しあげ を行えば原理的には計算できるが、それにはグラフの頂 点数に関して、指数オーダーの計算が必要になってしま う。実際、この問題は NP 困難であることが知られてい る。よって何らかの近似手法が不可欠であるが、その代 表的な手法として、ベーテ近似がある。. ループ展開の解説. 2 2.1. グラフ構造を持った確率分布.  まず最初に記号等を整理する。. Definition 1 (グラフの定義). 有限集合 V = {i1 , . . . , iN },E ⊂ V × V が与えられたと き、この対 G := (V, E) を有向グラフという。(j, i) ∈ E が i から j への有向辺を表す。V を頂点集合、E を(有 向)辺集合という。特に、E が対称(i.e. (j, i) ∈ E ⇔. (i, j) ∈ E )かつ対角を含まない(i.e. (i, i) ∈ / E )とき G を単純無向グラフという。. 最近、Chertkov and Chernyak [1] は真の分配関数を ベーテ近似の周りで(計算可能な量を使って)展開する. この論文では単純無向グラフのみを考え, 以下ではそ. 公式を与えた。以下この公式をループ展開と呼ぶ。こ. れを単にグラフと呼ぶ. の展開にはグラフ的な楽しみがあり、今回の話の中心的. また、(j, i) と (i, j) を同一視したものを ji(= ij) と書 ˜ を(無向)辺集合と呼ぶ。 き、その集まりを E. テーマである。ループ展開においては和の各項がグラフ の ”一般化ループ ”に対応し、それらをすべて足し上げ ることで真の分配関数を得る。項の個数は有限ではある ものの指数オーダーであるのでこの足し上げを実行する ことは現実的には不可能である。. 1.2. 研究の動機. N (i) は頂点 i に隣接する頂点の集合を表す。di := |N (i)| を頂点 i の次数という。 Definition 2 (グラフの状態空間). グラフ G = (V, E) ∏ に対して、有限集合の直積 χ := i∈V χi を与える。こ れを G の状態空間という。特に x = (xi )i∈V ∈ χ を G の状態という。. 歴史的にはグラフ構造を持った確率分布の周辺確率分 布(一変数確率分布)を求める問題は、AI などの分野に おいて現れ、確率伝播法というアルゴリズムが使われて きた。このアルゴリズムはグラフが(本質的に)ツリー のときに正しい周辺確率分布を求めてくれる。 また近年考案された、効率の非常に高い誤り訂正符号 の方式に、LDPC 符号、ターボ符号というものがある。 これが本質的に必ずしもツリーでないグラフに対して ヒューリスティックに確率伝播法を適用したものである ことが解明され、注目を集めた。 確率伝播法による周辺確率分布の計算と、ベーテ近似 による分配関数の計算は密接に関係する。本来は確率伝 ∗ 統計数理研究所,. 106-8569 東京都港区南麻布 4-6-7, tel.03-34461501, e-mail watay@ism.ac, Institute of Statistical Mathematics, 4-6-7, Minami-Azabu, Minato-Ku, Tokyo, 106-8569. 以下すべて、χi = {0, 1} として考える。. Definition 3. (G, χ):状態空間つきグラフに対して、 ˜ 、ψji : χj × χi −→ R≥0 を G のポテンシャルと ji ∈ E 呼び、その全体を Ψ = {ψji }ji∈E˜ と書く。. ∏ (G, χ, Ψ) から p(x) = Z1 ji∈E˜ ψji (xj , xi ) のように して χ 上の確率分布 p が定まる。ここで、x = (xi )i∈V で,Z は規格化定数(分配関数)である。. 2.2. 確率伝播法. 確率伝播法 (Belief Propagation) 1 は、周辺確率分布. {pi (xi )}i∈V や分配関数 Z を計算する簡単な近似アルゴ 1 閉路のあるグラフに対しては特に loopy belief propagation と 区別して呼ぶことも多い。本論分では区別しない。.

(13) リズムとして知られている。以下ではそのアルゴリズム を説明する。[2]. 2. 12 11. 1 6 7. 3. 8 9. 4 5. Algorithm 1 (Belief Propagation). 1. ∀(j, i) ∈ E に対して、初期時刻 t = 0 におけ |χj | る i から j へのメッセージを mt=0 を (j,i) ∈ R 1 m(j,i) (xj ) = |χj | ∀xj ∈ χj と初期化する。. 2.3.1. 10. Loop 展開の例. 図 1:. まず具体例でやってみる。このグラフの分配関数を展 開してみる。. 2. 次に、t = 0, 1, . . . で mt+1 (j,i) (xj ) = ω. ∑. ψji (xj , xi ). xi ∈χi. ∏. Z = 1 + βl + βr + βl β67 βr γ6 γ7. mt(i,k) (xi ). k∈N (i)\{j}. (1) のようにしてメッセージを更新していく。ここで、 ∑ ω は xj mt+1 (j,i) (xj ) = 1 とするような規格化定 数。これをメッセージが収束するまで繰り返し、. {m∗(j,i) }(j,i)∈E を得る。 3. p(x) の周辺確率分布 pi (xi ), pji (xj , xi ) の近似とし て、 ∏ bi (xi ) := ω m∗(i,j) (xi ) (2). ここで、βl = β12 β23 β34 β45 β56 β61 , βr = β78 β89 β9(10). β(10)(11) β(11)(12) β(12)1 とおいた。いま、ZB = 1 になる ようにしていて、式(5)の右辺第一項が ZB に相当し ている。残りの 3 項が真の分配関数との差であり、図 1 の右側の三つの部分グラフに対応している。. 2.3.2. 定理. Theorem 1 (Loop Expansion).. m∗(i,k0 ) (xi ) (3). dC,i を C の中で見た頂点 i の次数として、. 4. 最後に分配関数 log Z の近似は ∑ ∑ log ZB = bji (xj , xi ) log ψji (xj , xi ) ˜ xj xi ji∈E. +. ∑. (di − 1). i∈V. ˜C ij∈E. βij. ∏. fdC,i (γi ). (7). i∈VC. 研究の現状. 3. 式(6)において、いくつかの項を足し上げれば近似. bji (xj , xi ) log bji (xj , xi ). ˜ xj xi ji∈E. ∑. がよくなることが期待できる。一般には指数個の項が出 てきてしまうが、平面グラフの場合には一部の項を一気. bi (xi ) log bi (xi ) (4). xi. に Pfaffian を使って足しあげることができる。実験をし てみると相互作用が弱い領域ではこの方法で近似がか. によって与える。これを分配関数のベーテ近似と. なり改善されるが、強い領域では改善されないことがわ. いう。. かる. G が tree(閉路のないグラフ) の場合はこのアルゴリ ズムによって、近似ではなく真の周辺分布と分配関数が 求まることが簡単に確認できる。. 2.3. ∏. r(C) :=. ∑ ∑. (6). ここで、G は G の部分グラフ全体2 を表し、C = (EC , VC )、. を使う。. −. r(C)). C⊂G. k0 ∈N (i)\{j}. k∈N (j)\{i}. ∑. Z = ZB (1 +. j∈N (i). bji (xj , xi ) := ω ψji (xj , xi ) ∏ ∏ m∗(j,k) (xj ) ×. (5). Loop 展開. Loop 展開の導出については概略のみ説明する。この 展開を導くにはまず (G, χ, ψ) に対して確率伝播法を適 用し、収束メッセージ {m∗ (i,j) } を得る必要がある。こ. 参考文献 [1] M. Chertkov and V.Y. Chernyak. “Loop series for discrete statistical models on graphs.” Journal of Statistical Mechanics, page P06009, 2006a. [2] J. Pearl “Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference “ Morgan Kaufman, 1988. [3] M. E. Fisher, “On the Dimer Solution of Planar Ising Models” J. Math. Phys., 7:1776-1781, 1966. の解から {βij }ij∈E˜ , {γi }i∈V という量を計算する。定義 は省略するが、とにかくこのような量が収束メッセージ から簡単に計算できる。 さらに、x ∈ R に対して、{fn (x)}∞ n=0 を、f0 (x) =. 1, f1 (x) = 0, fn+1 (x) = xfn (x) + fn−1 (x) によって帰納 的に定めておく。. 2 正確には辺集合 E の空でない部分集合の誘導する部分グラフ全 体。|G| = 2|E| − 1. 式(6)第一項目の 1 が空部分グラフに対応して いる。.

(14) Trace Generating Functions of Plane Partitions Soichi OKADA Graduate School of Mathematics, Nagoya University A plane partition is an array of non-negative integers π11 π = π21 .. .. π12 π22 .. .. π13 π23 .. .. ··· ···. P satisfying i,j πi,j < ∞ and πi,j ≥ πi,j+1 , πi,j ≥ πi+1,j for all i and j. A plane partition π is identified with its diagram {(i, j, k) ∈ P3 : 1 ≤ k ≤ πi,j }, where P is the set of positive integers, and can be visualized as a stack of unit cubes. For positive integers a, b and c, we denote by P(a, b, c) the set of all plane partitions whose diagrams are contained in the a × b × c box. Given a plane partition π = (πi,j ), we define the k-th trace tk (π) by putting X tk (π) = πi,i+k . In this talk, we follow an idea of Okounkov and Reshetikhin to prove Gansner’s formula b−1 Y. X. t (π). qkk. π∈P(a,b,∞) k=−a+1. where q[i, j] =. Qj. k=i qk. X. =. a Y b Y. −1. (1 − q[−i + 1, j − 1]). ,. i=1 j=1. and its finite analogue b−1 Y. t (π). qkk. a−1 a−2 1 = q−a+1 q−a+2 · · · q−1. −c. s(ca ) (z1 , z2 , · · · , za+b ),. π∈P(a,b,c) k=−a+1. where s(ca ) is the Schur function corresponding to the rectangular Young diagram (ca ) and zi = q[−a + 1, −a + i − 1] (1 ≤ i ≤ a + b).. 1.

(15) Catalan 数, Motzkin 数, Schr¨oder 数の Hankel 行列式と その q-analogue∗ 石川 雅雄 鳥取大学 鳥取市湖山町南 4 – 101 ishikawa@fed.tottori-u.ac.jp. Mathematics Subject Classifications: Primary 05A15; Secondary 05A17, 05E05, 05E10. Keywords: Catalan numbers, Fibonacci numbers, Hankel determinants.. 1. Introduction この講演では Catalan 数の Hankel determinants が 1 になるという事実の q-analogue を考える.. Catalan 数は、よく知られているように平面上のあるグラフの path の数え上げで実現される。また、 この Catalan 数を Motzkin 数や Schr¨ oder 数のような別のグラフの path を数え上げる数に置き換 えると, どのようになるかを考察する. Catalan 数 cn =. ¡ ¢. 2n 1 n+1 n. (n = 0, 1, 2, . . . ) は漸化式 c0 = 1, cn =. n−1 X. cn−1−1 ck. (1.1). k=0. を満たすことは、よく知られている [4]. Catalan 数から作られる n 次の Hankel 行列.  Mnt. ct.   ct+1 =  ..  . ct+n−1. ct+1 ct+2 .. . ct+n.  ct+n−1  ct+n   ..   .. ... ... .. .. (1.2). . . . ct+2n−2. を考えるとき. det Mn0 = det Mn1 = 1,. (1.3). det Mn2. (1.4). = n + 1, 1 det Mn3 = (n + 1)(n + 2)(2n + 3) 6. (1.5). ということが知られている [1, 3]. また.  Snt. ct + ct+1.   ct+1 + ct+2 = ..   . ct+n−1 + ct+n. ct+1 + ct+2. .... ct+n−1 + ct+n. ct+2 + ct+3 .. .. ... .. .. ct+n + ct+n+1 .. .. ct+n + ct+n+1. .... ct+2n−2 + ct+2n−1. ∗ 本講は著者と和歌山大学の田川裕之氏の最近の共同研究である.. 1.      . (1.6).

(16) という n 次の Hankel 行列を考えると. det Mn0 = f2n. (1.7). det Mn1. (1.8). = f2n+1. が成り立つことが知られている [1, 2]. ここで fn は Fibonacci 数 (漸化式 f0 = f1 = 1, fn =. fn−1 + fn−2 で定義される) である.. 2. 目標 Catalan 数の q-analogue として、いくつかの候補が知られているが、ここで cn (q) を c0 (q) = 1 と cn (q) =. n−1 X. q (k+1)(n−1−k) cn−1−k (q)ck (q). (2.1). k=0. によって定義される多項式とする. また, Hankel 行列 (1.2) の q-analogue として ³ ´ Mnt (q) = q (i−j)(i−j+1)/2 ci+j+t−2 (q) 1≤i,j≤n. (2.2). を考えると, 次の定理が示せる.. Theorem 2.1. n ≥ 1 が自然数のとき det Mn0 (q) = det Mn1 (q) = 1. (2.3). また、現段階では予想であるが、次の式が成り立つことが観察される。. Conjecture 2.2. n ≥ 1 が自然数のとき det Mn2 (q) = [n + 1]q , [n + 1]q [n + 2]q ((1 + q 2 )[n + 1]q + q n+1 ) det Mn3 (q) = [3]q [2]q が成り立つ. ここで [n]q =. 1−q n 1−q. (2.4) (2.5). は q-整数である.. さらに q-Motzkin numbers mn (q) と q-Schr¨ oder numbers sn (q) を m0 (q) = s0 (q) = 1,. mn (q) = q 2n−1 mn−1 (q) +. n−2 X. q 2(k+2)(n−2−k) mn−2−k (q)mk (q),. (2.6). k=0. sn (q) = q 2n−1 sn−1 (q) +. n−1 X. q 2(k+2)(n−1−k) sn−1−k (q)sk (q). (2.7). k=0. によって定義する. 紙面の関係上、これ以上の結果は割愛するが非常に面白い予想が得られる.. 参考文献 [1] A. Benjamin, N. Cameron, J. Quinn and C. Yerger, “Catalan Determinants — A Combinatorial Approach”, preprint. [2] A. Cvetkovi´e, P. Rajkovi´e and M. Ivkovi´e, “Catalan numbers, the Hankel transform, and Fibonacci numbers”, J. Integer Seq. 5 (2002), Article 02.1.3. [3] M.E. Mays and J. Wojciechowski, “A determinant property of Catalan numbers” Discrete Math. 211 (2000), 125 – 133. [4] R. Stanely, Enumerative Combinatorics, Volume 1, 2, Cambridge University Press, 1997.. 2.

(17) Gap による Partition 代数の計算 琉球大学 理学部 小須田 雅. Partition 代数の定義 始めに次のような合コンの座席表を考える。. 2 空のテーブルは無いものとする 3 テーブルに属する男女の組合せのみに注目し,どのグループがどのテー ブルに着席するか,同じグループ内で誰がどの席に座るかは問題とし ない 上の条件を満たす座席表が1つ作られたとして,それを図に表すことを考え る。例えば座席表 {{f1 , m1 , m2 , m4 }, {f2 }, {f3 , f4 }{f5 , m3 }, {m5 }} に対して, 図 1 左のような図が得られる。 次にこの座席表の積について考える。座席表 w1 , w2 の積は,図 1 の右図の ように2つの図を重ねて,連結成分に注目して描きなおしたものと定義する。 ただし,両端と結ばれていないテーブルが出現したときは,それらを取り除 き,取り除いた数だけ Q 倍する (Q ∈ C)。この図は再び座席表を表すことに なる。このようにして座席表に積を定義しそれを C 上線形に拡張したものを A 型の合コン代数 (Partition 代数) と呼び,An (Q) と書くことにする。. f1. f2 T2 T1. f3. f4. f5. w1 w 2 w1. T3 T4 T5. =Q w2. m1 m2 m3 m4 m5 図 1: 座席表とその積. この代数の次元について考えてみる。基底は座席表で表されるので,dim An (Q) は,可能な座席表の総数に等しい。テーブルに着席する男女の構成には制限 が無いので,その数は全体の人数(個数)2n の集合分割の数である Bell 数. 1.

(18) B(2n) に等しいことがわかる。ちなみに Bell 数の始めの数項は,次のように なる。(n が奇数の項は括弧でくくってある。). (1), 2, (5), 15, (52), 203, (877), 4140, (21147), 115975, . . . 。. Young 図形の変形ゲーム 始めに十分な長さの横一列の Young 図形を λ(0) とする。λ(0) に次のルー ルを n 回繰り返して得られる λ(n) 達を列挙し,それらが得られるまでの過程 を樹形図としてあらわす。 ルール Young 図形 λ(i) の (inner) corner にある box を取り除き,λ(i+1/2) を作り,λ(i+1/2) の (outer) corner に box を1つ加えて λ(i+1) を作る。 実際にこのルールで樹形図を作ると,次のようなものが得られる。各 Young 図形に添えた数字は,そこへ到達するまでの道の数である。同じ段にある数 字を2乗して和をとると Bell 数 B(2n) となる。. 0-th 1-st 2-nd. 1. 1. 2. 3. 1. 1. 3-rd 5. 10. 6. 6. 1. 2. 1. 図 2: An (Q) の Bratteli 図形. 研究テーマと GAP の利用方法 始めに定義した代数 An (Q) の次元と上で定義した樹形図の道の数の2乗和 がともに Bell 数 B(2n) に等しいことに注目し,その間の自然な全単射を構成 することを現在試みているが,n の増加に伴い,An (Q) の次元が爆発してし まうため,数式処理ソフトの利用が不可欠である。. GAP は Groups Algorithms and Programming の略で,その名前から推測 されるように群,とくに有限群の研究のためのソフトである。有限群はすべ て何らかの対称群に含まれ,対称群の各元は順列として表されることから,. GAP は順列(リスト)の扱いが得意である。GAP のこの特徴を活用しなが ら研究を進めている。. 2.

(19) 電子透かし符号に関連するある列挙問題 縫田. 光司(NUIDA, Koji). 産業技術総合研究所 情報セキュリティ研究センター k.nuida@aist.go.jp. 1. 電子透かし符号とは. 電子透かしとは、CD や DVD、コンピューターのファイルなどの電子 的なデータに付加的な情報を埋め込む技術、もしくはその埋め込まれた情 報自体を指します。 「電子」の付かない透かし、例えば日本の紙幣に入れ られた透かしは作り主が日本銀行であることを保証してくれるため、偽 造防止に役立ちます。同様に電子透かしも、音楽ファイルなどの電子化 された著作物に著作者や販売者のデータを埋め込むことで、著作物の偽 造や不正コピーを発見するために用いられています [1]。 電子透かしの利用法として、例えばデジタルコンテンツをユーザーに 配信する際、ユーザーの ID を電子透かしとして予め埋め込んでおくこと で、不正コピーを作った犯人を突き止めよう、といった応用が考えられ ています。そのためには透かしが容易に改竄されない必要がありますが、 複数のユーザーが協力すると透かしの一部を検出できてしまう [2] ため、 その部分が改竄されても効果が殆ど落ちないように透かしを設計する必 要があります。そのための符号が電子透かし符号(結託耐性符号)です。. 2. Marking Assumption. 以下、符号語 w は長さ m で、各ビット wi は 0 または 1 の値を取るも のとします(w ∈ {0, 1}m )。u1 , . . . , uℓ を結託している悪いユーザー達、 w1 , . . . , wℓ を各々の符号語とすると、各々の j ビット目が全て一致してい る場合を除いてはそのビットが検知されて(従って改竄されて)しまうと いうのは上に述べた通りです。逆に、j ビット目が全て一致している場合 にはそのビットが改竄されない、という仮定は Marking Assumption と呼ばれ、この分野の研究の殆どで採用されています: 仮定 1 (Marking Assumption) 各 1 ≤ j ≤ m について、もし w1,j = w2,j = · · · = wℓ,j なら、改竄後の符号語 y において yj = w1,j となる。. 1.

(20) Marking Assumption の下では、改竄後の符号語 y が与えられたとき、 結託しているユーザー集団(ℓ 人)の候補の集合は Pℓ (y) = {{u1 , . . . , uℓ } ∈ Zℓ | 1 ≤ u1 < u2 < · · · < uℓ ≤ N, yj ∈ {w1,j , . . . , wℓ,j } for all 1 ≤ j ≤ m} (ただし N は総ユーザー数)となります。話者らが提案した方式 [3] では、 Pℓ (y) の元を列挙することで高確率での犯人特定を実現しています。. 3. 件の列挙問題 上述した Pℓ (y) の元の列挙問題は、以下のように定式化できます。. 問題 1 行列 x = (xi,j )1≤i≤N,1≤j≤m ∈ MN,m ({0, 1}) と長さ m のベクトル y = (y1 , . . . , ym ) ∈ {0, 1}m 、正の整数 j が与えられたとき、以下の条件. (MA) 任意の 1 ≤ j ≤ m について yj ∈ {xi1 ,j , xi2 ,j , . . . , xiℓ ,j } を満たす {1, . . . , N } の ℓ 元部分集合 {i1 , . . . , iℓ } を列挙せよ。 この問題を定義通りに解くと Ω(N ℓ ) の計算量となりますが、想定され る応用ではユーザー数 N が百万だの一億だのといった膨大な数になり得 るため、ℓ 乗のオーダーでは実用上厳しく、より効率的な方法が必要とな ります。そのような効率的な列挙アルゴリズムがあるといいなあ、とい うのが話者の最近の願いです。今回の発表ではこのようなお話をします。. 参考文献 [1] 「JASRAC の違法音楽配信サイト対策」 、INTERNET Watch、 http://internet.watch.impress.co.jp/www/article/2003/ 0217/special.htm [2] D. Boneh and J. Shaw, “Collusion-secure fingerprinting for digital data”, IEEE Trans. Inform. Theory 44 (1998) pp.480–491 [3] K. Nuida, M. Hagiwara, T. Kitagawa, H. Watanabe, K. Ogawa, S. Fujitsu, and H. Imai, “A tracing algorithm for short 2-secure probabilistic fingerprinting codes strongly protecting innocent users”, 4th Annual IEEE Consumer Communications and Networking Conference (CCNC 2007) DRM Workshop, Nevada, USA, Jan. 11, 2007 2.

(21) 非正則疑似巡回低密度パリティ検査符号の量 子符号化にまつわる組合せ論的アプローチ 萩原学. 2007/09/04 9:20-9:40 本講演では量子誤り訂正符号の構成方法について議論する。対象とする量子 符号は CSS 符号と呼ばれる。CSS 符号はねじれ条件を満たす古典符号の対から 構成されるが、どのような古典符号で構成するかにより、取り扱う数学が変わる。 古典符号の中でも、とりわけ重要であって盛んに研究されている符号の一つに擬 似巡回 LDPC 符号がある。 擬似巡回 LDPC 符号が盛んに研究される理由は実装面と理論面の両面にある。 実装面として、非常によい誤り訂正特性を短い符号長(符号を構成するビット 数)で実現することにある。 (誤り訂正符号は符号長を無限長にすることで、理論 限界まで誤り訂正能力を上げられることが知られている。擬似巡回 LDPC 符号は、 わずか数千の符号長で実用的に十分意味のある誤り訂正が実現される。他に重要 な点として、符号化器と復号器の設計もしやすさも挙げられる。そういった利点の 数々から、IEEE802.11n(高速無線 LAN の規格。2.4GHz/5GHz の周波数帯を用 いて、100Mbps 以上の公称速度をターゲットとしている)や IEEE802.16e(高 速無線 MAN の規格。通称 Mobile WiMAX。伝送距離 1∼3Km、最大伝送速度 21Mbps としている)における誤り訂正符号の標準化仕様として選定されている。 理論面として、重要な点は簡便な符号の記述法である。古典符号を特徴付ける パリティ検査行列を、符号長に比べて非常に小さなインデックス行列(整数を要素 に持つ行列)によって記述する。例えば、IEEE802 で選定されている擬似巡回符 号のパリティ検査行列を表すインデックス行列のサイズは、行数が最大の場合で も12×24で済む。インデックス行列のエントリーを数学的に扱うことは、符 号の性質を解析することに直結する。特にそのエントリーが整数であることから、 離散数学、有限環、代数的組合せ論などが貢献できるフィールドと期待できる。 本講演では、擬似巡回符号の組が量子誤り訂正符号を構成する為の条件を紹 介し、IEEE802.16e で選定された古典符号を量子誤り訂正符号に拡張できるかど うか考察した結果を紹介する。 Acknowledgement: This research was partially supported by Grants-inAid for Young Scientists (B), 18700017, 2006..

(22) 畳み込み型レスポンスデータ圧縮回路の 組合せ論的設計法 藤原祐一郎 名古屋大学大学院情報科学研究科 集積回路の設計および故障の自己診断などのために,スキャンテストと 呼ばれるテスト方式が広く利用されている.しかしながら,集積度が非 常に高い電子回路においては,スキャンテストに必要となるコストが大 きな問題となる.特に,テストで利用するデータ量はコストの主因の一 つとなっている.このため現在では,欠陥発見性能を実用的な範囲で維 持しつつ,メモリー内に記憶すべきテストデータ量を圧縮することが不 可欠となっている. 本発表ではまずはじめに,未知論理値が期待データ内に存在する状況 に対応するために考案された,X-compact と呼ばれる圧縮技術について組 合せ論的観点から概説する.X-compact 技術を応用したスキャンテストで は,X-code と呼ばれる次のような符号を用いる. (1) (1) (1) (2) (2) (2) x1 = (x1 , x2 , . . . , xm ) および x2 = (x1 , x2 , . . . , xm ) を F2 上での m 次 元ベクトルとする.x1 と x2 の superimposed sum x1 ∨ x2 は, (1). (2). (1). (2). (1). (2). x1 ∨ x2 = (x1 ∨ x1 , x2 ∨ x2 , . . . , xm ∨ xm ), ( j). (l). ( j). (l). ただし xi = xk = 0 のとき xi ∨ xk = 0,そうでないとき 1 と定義され る.また,x1 ∨ x2 = x1 が成り立つとき,x1 は x2 を cover するという. X を F2 上の m 次元ベクトルからなる濃度 n の集合とする.任意の正 の整数 e ≤ e に対して,任意の d 個以下の X の元からなる superimposed sum が残りの n − x 個の元から選ばれたどの e 個の元の和も cover しない とき,X を (m, n, e, x) X-code と呼ぶ. 我々は X-code と組合せデザイン,グラフおよびハイパーグラフの関 係を用いたレスポンスデータ圧縮回路の設計方法を紹介する.さらに Xcompact 技術の一例として,畳み込み型レスポンスデータ圧縮を応用した 圧縮回路の一般的設計方法を与える。.

(23) 正多角形領域に対するオンライン追跡問題 藤原 洋志 関西学院大学. 

(24)   

(25) .  

(26)  

(27)  

(28) 

(29)    .

(30)    

(31) 

(32)  .  . 

(33)           

(34)       

(35) 

(36)     

(37)       

(38)                 ! 

(39)     " #     

(40)  

(41) ! $

(42)   

(43)         

(44)  

(45)  

(46)   %   

(47)   

(48)     

(49)

(50) "            

(51) ! &                   '  

(52)     !   %   

(53)       

(54)     % 

(55)     "     ! (  % 

(56)    

(57)  %         

(58)  

(59)        

(60)    "           

(61) "   

(62) ! & 

(63)     

(64) 

(65)   

(66)  

(67)   

(68) 

(69) "    "       "

(70)  ! (    

(71)  

(72) "  

(73)      " 

(74)       

(75)   

(76) "

(77) 

(78) "     ' 

(79)

(80) "       Æ  

(81) !  "

(82)

(83) " )

(84)   * " "   

(85) "  "     '   

(86) 

(87)    

(88) 

(89)  

(90)    

(91)  

(92)  '  

(93) + ! &   

(94)  

(95)  

(96) 

(97) " '

(98) " " 

(99)     

(100)

(101) " 

(102)   

(103)  ' " !   %   

(104)  

(105)    " 

(106)

(107)   *      

(108)   *         ! &    

(109)    " 

(110)     

(111)  

(112) ! 

(113)  

(114) 

(115)  

(116)       , - .   /  

(117)    

(118)  

(119) .      - # +     ! &

(120)

(121) 

(122) 

(123)          

(124) 

(125)  0 

(126)  

(127)       "  È , ! 

(128) 

(129)   

(130)   - .,  ,      , /%      " *

(131) "  ./ - 10 2  0 0    1   

(132)    

(133)     

(134) " 0 0 "

(135)    3"

(136) "

(137)   

(138) 0

(139) " 0 ! 

(140)        

(141)    

(142) 

(143)     

(144)  

(145) " ,

(146) "  

(147)  ! & 

(148) " 

(149)   

(150) "    

(151)     

(152)       "           '! 0  

(153) 

(154) 

(155)   

(156)     

(157)   "  

(158)  

(159)  

(160) %  4   

(161) " 

(162)       

(163) 

(164)  

(165) !  

(166)  5% # %          

(167) 

(168) 

(169)   

(170)    ' 

(171) 

(172)    %   

(173)   

(174)   % ./

(175)    ./      

(176)   6

(177) ! . . 

(178)

(179)   . &  "    

(180) 

(181)  

(182)     " *

(183) "    !     

(184) 

(185) 

(186)            

(187)    7   8 &      

(188) 

(189)   "        

(190)   

(191)    " %  

(192) 

(193)     !  8      % ./     7   

(194) 0 

(195)  

(196)  % 

(197)       9      

(198) 4  0 9! ./ $   % "

(199)      ! #.

(200) .  . .  . 1. . .  #8 $

(201) 

(202) : 

(203)   ' 

(204) ! . . 5. ;. <. =. >. ?. #@.  

(205)   +!@@ #!5# !+5 +!@@ 5!5? +!<# ;!=< !+5 &  #8 :          

(206) !.     # 

(207).  . 

(208). 

(209) . .    

(210)   . # 

(211).  . 

(212) . . . .  .    

(213)   . 

(214) .

(215)    

(216)  

(217). 

(218)   

(219)   .     . &   

(220) "  

(221) 

(222) 4 "

(223) !  

(224) 

(225)   

(226)  % 

(227)     

(228) "

(229) 6

(230) .    ¬         ! A  ¬. 

(231)   

(232) 

(233)  B. / - È  ¬ 

(234)  2    ¬%   . /   "  

(235)        

(236)  "  

(237) " ! & 

(238) 

(239) 

(240)    " " 

(241) '

(242) 

(243)   C

(244)  

(245) "

(246)   

(247)     ! &   

(248) % 

(249) 

(250)   

(251)  

(252) 

(253)     

(254)    

(255) 8 $

(256)  *' "

(257) "      "

(258) ! A        "    

(259)   

(260) %         "    44   

(261)   " %   

(262) .  .  .  . 

(263) 

(264) 

(265) 

(266) . # 0! D"

(267)

(268) " ,! 3E

(269) !             ! : " 

(270)    F % #??>! + G!  "

(271)

(272) " (! )

(273)  ! $

(274) 

(275)  ' "  

(276) !  

(277)   !     "

(278) % ?8+?H+#% #??!  C! 1! C

(279)  % )! 0! C %

(280) " I! I! 1 ! :        ! #  

(281)   % ##.+/8+@>H+@% #??@! 5 I! 1 

(282) " ,! 3! & 

(283) ! 04 " Æ

(284)    " 

(285) "  

(286)   ! 

(287)      $%  +>%    +@+H+@>% #?>;! +.

(288) 対称群のある表現たちの指標の重み付き和 の組合せ論的表示について 沼田 泰英. µ = (µ1 ≥ µ2 ≥ · · · ) をどの重複度も l で割り切ることができる m の 分割とする. µ に対して, aµ,l を m/l 個の 長さ l の巡回置換の積 Y. (j +. (i,j)=(i00 l+i0 ,j)∈µ. i¡1 X. µk , j +. k=1. i X k=1. µk , j +. i+1 X. µk , . . . , j +. i+l¡1 X. k=1. µk ). k=1. として定義する.. Example 1. µ = (2, 2, 2, 1, 1, 1) のとき, aµ,3 = (1, 3, 5)(2, 4, 6)(7, 8, 9) で ある. 次の様に, standard tableaux を作り, 縦に l 個ずつ数字を読んで いき, 巡回置換を作っていけば, aµ,l を得ることができる: 1 2 3 4 1 2 7 5 6 Ã 3 4 8 Ã (1, 3, 5)(2, 4, 6)(7, 8, 9). 7 5 6 9 8 9 Young subgroup Sµ = S{ 1,...,µ1 } × S{ µ1 +1,...,µ1 +µ2 } × · · · と l 次巡回 群 Cl = haµ,l i の半直積 Hµ (l) = Sµ o Cl を考える. このとき, Zµ (k; l) を 1 次元表現 Hµ (l) → C× ; Sµ 3 σ 7→ 1, Cl 3 aµ,l 7→ ζlk (ただし √ ζlk = exp(2πk ¡1/l)) として定義し, Mµ (k; l) を m 次対称群 Sm への誘 xSm 導表現 Zµ (k; l)Hµ (l) とする. このとき, cycle type が ρ である σ ∈ Sm に対して, Mµ (k; l) たちの指標を重みをつけて和をとって得られる値 l¡1 X. ζlik Char(Mµ (k; l))(σ). k=0. を考える. この値を, Young diagram Dµ 上の, ある条件を満たすタイ リング (marked (ρ, l)-tableux on µ) の総数として表示することができ た (すなわち, この値に組合せ論的表示を与えることができた) ので報 告する. Pl¡1 ik まず, k=0 ζl Char(Mµ (k; l))(σ) の組合せ論的表示に必要となる組 合せ論的対象 (marked (ρ, l)-tableux on µ) を定義する. その定義のた めに必要となる, (ρ, l)-tableux on µ をまず次のように定義する. 1.

(289) 2. NUMATA, YASUHIDE. Definition 2. µ の Young diagram Dµ = { (i, j) ∈ N2 1 • j • µi } と m の分割 ρ = (ρ1 ≥ ρ2 ≥ · · · ) に対して, 次の条件を満たす写像 T を (ρ, l)-tableaux on µ と呼ぶ: • T は Dµ から N への写像. すなわち, Young diagram Dµ の箱に 整数を書き込む. • すべての k に対して, |T ¡1 ({ k })| = ρk . すなわち, 丁度 ρk 個の 箱に k が書きこまれている. • すべての k に対して, n, i, j が存在し, ª © T ¡1 ({ k }) = (i + i0 , j + j 0 ) (i0 , j 0 ) ∈ D(nl ) . すなわち, k が書き込まれた箱達は l × n の長方形をなす. • j • k を満たす全ての (i, j), (i, k) ∈ Dµ に対して,. T (i, j) • T (i, k). すなわち, 各行では, 書き込まれた数字は弱い意味で単調増加.. Example 3. つぎは, ((6, 3, 3, 3), 3)-tableaux on (3, 3, 3, 2, 2, 2): 1 1 1 3 3 3. 1 2 1 2 1 2, 4 4 4. 1 1 1 2 2 2. 1 3 1 3 1 3, 4 4 4. 1 1 1 2 2 2. 1 4 1 4 1 4, 3 3 3. 2 2 2 1 1 1. 3 4 3 4 3 4. 1 1 1. また, marked (ρ, l)-tableaux on µ を次のように定義する.. Definition 4. 次の条件を満たす写像の組 (T, c) を marked (ρ, l)-tableau on µ と呼ぶ: • T は (ρ, l)-tableau on µ, • c は { i ρi 6= 0 } から Z/lZ への写像. 写像 c を c : { i ρi 6= 0 } → { 1, . . . , l } と同一視し, この時, 次が成立する.. Theorem 5. 全ての重複度が l で割り切ることができる m の分割 µ と cycle type が ρ である σ ∈ Sm に対して次が成立する, l¡1 X. ζlik Char(Mµ (k; l))(σ) = | { marked (ρ, l)-tableaux on µ } |.. k=0. さらに, 一般の分割 µ に対する行の入れ換えのなす巡回群と Young subgroup との半直積の群において, 同様な結果を得ている. 北海道大学大学院理学研究院 E-mail address: nu@math.sci.hokudai.ac.jp.

参照

関連したドキュメント

サービス時間: 平日 9:00 ~ 17:00 (土日祝を除く ).. 納品書に記載のある「製品にアクセスする」ボタンをクリックし、 My HPE Software Center にログインを頂き

演題番号 P1-1 ~ P1-37 P2-1 ~ P2-36 ポスター貼付  9:00 ~ 11:00  9:00 ~ 11:00 ポスター閲覧 11:00 ~ 18:20 11:00 ~ 17:50 発表(ディスカッション) 18:20 ~

〜 3日 4日 9日 14日 4日 20日 21日 25日 28日 23日 16日 18日 4月 4月 4月 7月 8月 9月 9月 9月 9月 12月 1月

   遠くに住んでいる、家に入られることに抵抗感があるなどの 療養中の子どもへの直接支援の難しさを、 IT という手段を使えば

1月 2月 3月 4月 5月 6月 7月 8月 9月 10月 11月 12月.

令和4年3月8日(火) 9:00 ~ 9:50 10:10 ~ 11:00 11:20 ~ 12:10 国  語 理  科 英  語 令和4年3月9日(水) 9:00 ~ 9:50 10:10 ~

授業内容 授業目的.. 春学期:2019年4月1日(月)8:50~4月3日(水)16:50

全国で64回開催 9月 4日 ワークショップ終了 9月 10日 募集締め切り. 9月