数理解析研究所講究録 1440 巻 2005 年 18-23

18

Upper bounds given by an equitablepartition of a primitive association scheme
平坂

貢 (Mitsugu Hirasaka), *2004 年 12 月 13 日

1

序を有限集合 $X$ 上の原始的な置換群で交替群を含まないものとする。
$H$ を $G$ の任意の部分群とするとき、の$G$$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(H):=\{x\in X|x^{H}\neq\{x\}\}$

サイズ $m$ は次の不等式をみたす$($定理$3.2)_{\text{。}}$$|X|\leq(m-1)^{2m}$.

(1)

アソシエーションスキーム (以下、 AS と省略する)という概念について触れておく (詳細は $[2],[3],[8]$ を参照) AS とは $X$ 上可移な置換群の$X\mathrm{x}X$における軌道全体が (二軌道と呼ばれる) 満たす性質を基に定義された組合せ的対象である。 可移な置換群から構成されるものはその典型例である。 しかし、 そうでないものも多数存在する。 これまでに、 可。

移な置換群から構成されるための構造定数や部分構造に関する十分条件を見出す特徴づけや、 置換群論の一般化が多くの研究者によってなされてきた (例えば $[2],[3],[8]$ 参照)。

本研究は AS と Equitable Partition(以下、 EP と略す) に対して不等式 (1) を一般化することを目的としている。

$\mathrm{E}\mathrm{P}$とは置換群の部分群の軌道全体が満たす性質で定義されている頂点集合の分割のことである。 これらの定義は次節で述べよう。

*釜山国立大学数学科所属

182

記号と定義
記号に関しては [2] で与えられているものを使用する。

定義 2.1. $X$ を有限集合とする。 $R_{i}(i=0,1, \ldots, d)$ を $X$ 上の二項関係とする。
ムと呼ばれる。

$(X, \{R_{i}\}_{0\leq i\leq d})$は次の条件を満たすときにアソシエーションスキー

if
1.
2. $R_{0}=\{(x, x)|x\in X\}$ ;3. 任意の に対して が存在して、$\{(x, y)|(y, x)\in R_{i}\}$ ;$\mathrm{U}_{i=0}^{d}R_{i}=X\cross X,$$R_{i}\cap R_{j}=\emptyset$$\mathrm{i}\neq j$$\mathrm{i}’$$\mathrm{i}$4. 任意の$R_{k}$$\mathrm{i},$$j_{1}k$;$R_{i}^{t}=R_{i’}$に対して、次を満たす整数$p_{ij}^{k}$となる。 ただし、

$R_{i}^{f}:=$が存在する :任意の $(x, y)\in$に対して $p_{ij}^{k}=|\{z\in X|(x, z)\in R_{i}, (z_{7}y)\in R_{j}\}|_{\text{。}}$

がつぎの条件を満たす時原始的と呼ばれる :定義 22. ASに対して $(X, R_{i})$ が連結である。
任意の$(X, \{R_{i}\}_{0\leq i\leq d})$$\mathrm{i}\geq 1$

任意の$i$

に対して、$(x, y)\in R_{i}\}|$$k\text{嫁}=p_{ii’}^{0}$と定義する。 このとき、 $k_{i}=|\{y\in R_{i}|$であり、 次の構造定数に関する基本公式が成り立つ :$k_{0}=1$$\forall i,j,$$k_{i}=k_{i’}$,$k_{i}k_{j}= \sum_{h=0}^{d}p_{ij}^{h}k_{h},p_{ij}^{h}k_{h}=p_{hj’}^{0}k_{i}=p_{ih}^{j},k_{j}$補足 1. $G$ が $X$ 上原始的な置換群であれば、 その二軌道全体は原始的なAS をなす。
定義 23. $\pi:=\{C_{i}|1\leq \mathrm{i}\leq m\}$ を $X$ の分割とする、 すなわち、$i=1\cup^{c_{i}=X,C_{i}\cap C_{j}=\emptyset}m$が次の性質を満たす時に$Cj\in\pi$ , 任意のばれる : 任意の$(X, \{R_{i}\}_{0\leq i\leq d})$$\pi$

$C_{i},$

は $x\in C_{i}$ の選び方に依らず、 $i,$ $j,$

$R_{k}$$k$if $i\neq j$ .の Equitable Partition と呼に対して、 $|\{y\in C_{j}|(x, y)\in R_{k}\}|$のみによって決まる。

20$\pi^{*}$と$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)$を次のように定義する :$\pi^{*}:=\{C_{i}\in\pi||C_{i}|>1\}_{7}$$\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi):=\cup C_{i}C_{i}\in\pi^{*}$

3.

知られている結果と主定理
置換群論において次のことが証明されている。

補題 31([4, 3.3.6]). $G$ が $X$ 上原始的な置換群で、 $\sigma\in G-\{1_{G}\}$ ならの $X$ 上のば、 $G$ のランクは高々 $|\pi|-|\pi^{*}|+1$ である。 ただし、 は$\pi$$\langle\sigma\rangle$軌道全体からなる $X$ の分割である。
定理 32 $([4, 3.3.\mathrm{D}])$ . 任意の $m\geq 4$ に対して次の性質を満たす整数$\beta_{m}$が存在する : もし $G$ が $X$ 上原始的で交替群を含まない置換群で $G$ がそのサポートのサイズが $m$ である元を含むならば $|X|\leq\beta_{m}$ となる。
「上の定理における$\beta_{m}$として $(m-1)^{2m}$ を用いることができる。 しかしながら、 この上限はあまりにも大雑把な見積もりである。」 ということが [4] に記してある。

これらの結果を一般化したものが次の補題と定理である。
命題 33. もしが原始的 AS で、でを満たすものならば、$(X, \{R_{i}\}_{0\leq i\leq d})$$\pi^{*}\neq\emptyset$$\pi$

が $(X, \{R_{i}\}_{0\leq i\leq d})$ の $EF$

$d\leq|\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)|-|\pi^{*}|$

定理 34. もし $(X, \{R_{i}\}_{0\leq:\leq d})$ が原始的 AS でである。

$d\geq 2_{\text{、}}\pi$

が $(X\}\{R_{i}\}_{0\leq i\leq d})$の $EF$ で $\pi^{*}\neq\emptyset$ を満たすものならば、 $|X|<(m-1)^{2m}$

ただし $m:=$$|\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)|_{\text{。}}$

補足 2. 補題 3.1 は命題 33 の系として得られるが、 $d\geq 2$ という仮定のために定理 32 は定理 34 の系としては得られない。

4

証明の概略

命題 33 を証明するためには少々込み入った議論が必要になる。 しかし、 命題 33 を弱めた不等式の証明は容易である。 ま$d+1\leq|\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)|$21

た、 定理 3.4 の証明もその不等式を用いてなされる。 よって、本講演録では$d+1\leq|\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)|$の証明とそれを用いた定理 34 の証明の概略を記述する。

簡便のために次の補題が成り立つ。

$S:=\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)$

補題 4.1. 任意の$R_{i}$と記し、 $x\in S$ を固定しておく。 このときに対して、$R_{\dot{n}}(x)\cap S\neq\emptyset_{\text{。}}$が-意的に存在する。 $x\in S$ なので、 $|C_{j}|\geq 2$の定義から、 任意のである。 それゆえ、 $y\in C_{\mathrm{i}}-\{x\}$ が存在する。
である。
$C_{k}\in\pi-\pi^{*}$ と任意の瓦に対して、 $|R_{i}(x)\cap C_{k}|=|R_{i}(y)$ ロ$|C_{k}|=1$ であることを鑑みると、 上の式は $R_{i}(x)-S=$ 鳥 $(y)-S$ を意味(証明)$x$を含む$\pi^{*}$の元$C_{j}$$\mathrm{E}\mathrm{P}$$C_{k}|$する。

が存在すると仮定
背理法を用いて証明する。 $R_{i}(x)\cap S=\emptyset$ となる
すると、 前段落の議論から、 $R_{i}(x)=R_{i}(y)$ である。 このことは AS の定を意味する、 ただし $(x, y)\in R_{h\circ}$ 構造定数の基 x. 公式よ義から$=k_{h}$ である。 このことは $R_{i’}(x)$ が $(X, R_{h})$ の連結成分
り、$R_{i}$$p_{i\dot{\mathrm{z}}^{7}}^{h}=k_{i}$$p_{hi}^{i}=k_{h}/k_{i}p_{ii}^{h},$を含むことを意味するので、 原始性の仮定に矛盾する。
補題 42.

$d+1\leq|\mathrm{s}\mathrm{u}\mathrm{p}\mathrm{p}(\pi)|$(証明) 補題 4.1 より直ちに導かれる。

これより定理 34 の証明に入る。と上の異なる二点 $x,$ を固定しておく。 一般性を失うこと$C_{1}\in\pi^{*}$

なく$R_{1}$$C_{1}$$y$

を $(x_{7}y)$ を含む二項関係と仮定してよい。 鍵となるのが次の命題である。

命題 43. $k_{1}<(m-1)^{2}$ もしくは $k_{i}\leq m$ となる$\mathrm{i}$が存在する、 ただし$m:=|S|_{0}$(証明) 簡便のために $Z:=R_{1}(X)-S$ とする。 もし $|Z|\leq(m-2)^{2}$ であれば、$k_{1}=|R_{1}(x)|\leq m-1+(m-2)^{2}<(m-1)^{2}$

なであり、補題が成立するので、 $|Z|>(m-2)^{2}$ と仮定してよい。
らば、構造定数の変換公式と $R_{1}(x)-S=R_{1’}(y)-S=\emptyset$ から $|Z|\leq p_{11’}^{1}=$$R_{1}\neq R_{1’}$22$p_{11}^{1}=|R_{1}(x)\cap R_{1’}(y)|\leq m$である。 一方、 $k_{1}=|R_{1}(x)|\leq m+|Z|\leq 2m$なので補題が成り立つ。 よって $R_{1}=R_{1’}$ と仮定してよい。
このこ$p_{11^{J}}^{1}=|R_{1}(x)\cap R_{1}(y)|\geq|Z|\geq k_{1}-m$ であることに注意する.
$\geq k_{1}-m+2$ を証明することができる。とと原始性の考察により、$p_{11}^{1},$( $|X|$ の上限を $m$ の関数によって与えるだけなら後者の不等式は必要ではない。)$R_{i}\cap(Z\mathrm{x}Z)$の構造に注目しよう。 $|Z|>(m-2)^{2}$ の仮定と、 任意の$z\in Z$ に対して $|Z|-m\leq p_{11’}^{1}=|R_{1}(x)\cap R_{1}(z)|\leq|Z\cap R_{1}(z)|$なので、 有向グラフ $(Z, R_{i}\cap(Z\cross Z))$ の最小次数と $|R_{1}(z)\cap R_{1}(w)|,$ $z,$ $w\in Z$は十分に大きいことがわかる。 この議論を精密に行うと、 2, $w\in Z$ で$(z, w)\not\in R_{1}\cup R_{0}$ となる二元が存在して、 $|R_{1}(z)\cap R_{1}(w)|\geq k_{1}-3m+6$という不等式が得られる。
一般性を失うことなく、 $(z, w)\in R_{2}$ と仮定してよい。 もし $R_{2}(x)-S=\emptyset$
ならば、 $k_{2}\leq m$ であり、 補題が成立。 それゆえ、 $u\in R_{2}(x)-S$ が存在すると仮定してよい。 このとき、 $x,$ $y\in R_{2’}(u)$ なので、 構造定数に関する基本公式により、$k_{2’}k_{2}>p_{22}^{1},k_{1}\geq k_{1}$である。 すなわち、$k_{2}\geq\sqrt{k_{1}}$.

である。

構造定数に関する基本公式と得られた不等式により、$k_{1}k_{1}=k_{1}k_{1}/= \sum_{h=0}^{d}p_{11’}hk_{h}\geq k_{1}k_{0}+p_{11’}^{1}k_{1}+p_{11’}^{2}k_{2}\geq$$k_{1}+(k_{1}-m+3)k_{1}+(k_{1}-3m+6)\sqrt{k_{1}}$.

に関する二次式が 0 以下で押さに関して整理すると、えられるのがわかる。 これを解いて補題が得られる。

上の式を$\sqrt{k_{1}}$$\sqrt{k_{1}}$

補題 42 と命題 43 と原始性により、$|X|\leq 1+k_{1}+k_{1}^{2}+\cdots+k_{1}^{d}$

く $k_{1}^{\mathrm{d}+1}=(m-1)^{2m}$.となり、 定理 34 が証明された。

以下は参考文献である。 なお、 本稿で取り上げていないものも含まれている。

23

参考文献
[1] Z. Arad, E. Fisman, M. Muzychuk, Generalized table algebras, Israel
J. Math. 114, (1999), pp. 29-60.

[2] E. Bannai, T. Ito, Algebraic Combinatorics, 1984.
Benjarnin / Cummings, Menlo Park,$\mathrm{I}:\mathrm{A}\mathrm{s}\mathrm{s}\mathrm{o}\mathrm{c}\mathrm{i}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$Schemes,$\mathrm{C}\mathrm{A}$[3]$\mathrm{A}.\mathrm{E}$. Brouwer,$\mathrm{A}.\mathrm{M}$. Cohen, A. Neumaier, Distance-Regular Graphs,

Springer- Verlag, 1989.
.Dixon, B.Mortimer, Permutation groups, Graduate Texts inMathematics, 163. Springer- Verlag, New York, 1996.

[4]$\mathrm{J}.\mathrm{D}$[5]$\mathrm{C}.\mathrm{D}$. Godsil, W. Martin, Quotients of association schemes, J. Combin. Theory Ser. $A,$ $69$ (1995), no. 2, 185-199.

[6] M.Hirasaka, H.Kang, K.Kim, Characterization of association
schemes by equitable partitions, Euro. J. Comb., to appear.
[7] H. Wielandt, Finite permutation groups, Translated from the German by R. Bercov, Academic Press, New York-London, 1964

[8] P.-H. Zieschang, An AIgebraic Approach to Association Schemes,Lecture Notes in Mathematics 1628, Springer, 1996.