82

数理解析研究所講究録
第2003巻 2016年 82-95

ハミンググラフ H(n, m) の埋め込みを含む最大な m 距離集合の分類
愛知教育大学

数学教育講座野崎寛

Hiroshi Nozaki

Department of Mathematics Education
Aichi University of Education

はじめに

1

本稿では,主に [1] の内容を紹介する.ユークリッド空間 \mathbb{R}^{n} の有限部分
集合 X おいて, X の互いに異なる2点間のユークリッド距離の種類の個数|\{d(x, y)|x, y\in X, x\neq y\}| が m のとき,
X\subset \mathbb{R}^{d} が m 距離集合のとき,いる

X は m 距離集合と呼ばれる.

X のサイズの上界|X|\leq\left(\begin{ar ay}{l} d+7n\ m \end{ar ay}\right) が知られて[4]. 距離集合の主な問題のひとつは,距離の個数 m と次元 d を固定したとき,最大な m 距離集合 X を決定分類することである.最大1距離集

合は,任意の次元 d において, d+1 点の正則単体 (regular simplex) である.

最大2距離集合は, d\leq 7 において分類されている [8, 11]. Lisoněk [11] は\mathbb{R}^{8} 上の最大2距離集合をひとつ構成しており,これは, m\geq 2 において,
上界 |X|\leq\left(\begin{ar ay}{l} d+m\ m \end{ar ay}\right) を達成する唯一の既知の集合である. \mathbb{R}^{2} 上の m 距離集

合は m\leq 5 で分類されている[6, 14, 15]. \mathbb{R}^{2} 上の6距離集合は,分類は未解決だが,2つ最大なものが知られている [17]. \mathbb{R}^{3} 上の最大3距離集合は,正二十面体の頂点集合のみである [16]. 表1, 2で,知られている最大距離集
合のサイズ |X| と,その非同型 (等長写像が存在しない) な距離集合の個数\# を示す.
いくつかの例外を除いて,知られている最も大きなm

距離集合は,ジョンソンスキーム J(n_{-}m) の埋め込みである.次の様に記号を準備する.実数

83

表1

x_{i} ,

表2

m=2

d=2

自然数 $\lambda$_{i} に対して,(x_{1}^{$\lambda$_{1} , \ldots, x_{n}^{$\lambda$_{n} )= ( x_{1},.

,x\mathrm{l} ,.\tilde{$\lambda$_{1}

.

.

.

,

\displaystyle\frac{x_{n},\ldots,x_{n}{$\lambda$_{n}) \in \mathbb{R}^{$\lambda$_{1}+\cdots+$\lambda$_{n}(x_{1}^{$\lambda$_{1} ) は x_{1}^{$\lambda$_{1} と略記される. \mathrm{x}=(x_{1}, \ldots, x_{n})\in \mathbb{R}^{n} に対して,\mathrm{x}^{P}=(x_{1}, \ldots, x_{n})^{P}=\{(x_{ $\sigma$(1)}, \ldots, x_{ $\sigma$(n)})| $\sigma$\in S_{n}\}\subset \mathbb{R}^{n},ここで,S_{n} は対称群である. J(n, m) の m 距離集合としての埋め込みは,次の様に表される.

\tilde{J}(n, m)=(1^{m}, 0^{n-7n})^{P}\subset \mathbb{R}^{n}である \mathbb{R}^{n} のベ\tilde{J}(n, m) は成分1, 0 の個数が,それぞれ n,
クトル全体の集合となる. \tilde{J}(n, m) の各ベクトルの成分和が一定であることから, \tilde{J}(n, m) は \mathbb{R}^{n-1} の距離集合であるとみなすことが出来る.ジョン

つまり,

n-m

m

ソンスキームのボーズメスナー代数 (隣接代数) の幕等元 (半正定値行列) の振る舞いを見れば,次元 n-1 がジョンソンスキームの m 距離集合の埋め込
みを含む最小な次元であることが確認できる.Bannai‐Sato Shigezumi [5]は,\tilde{J}(n, m) を含む極大なX\subset \mathbb{R}^{n} が,mm距離集合について調べている.

m

距離集合

距離集合の性質を保ったまま,新たな元 \mathrm{x}\in \mathbb{R}^{n}\backslash X が加えられないとき, X は m 距離集合として極大であるという.[5] では,\tilde{J}(n, m)

が m 距離集合として極大であるときの必要十分条件を与えている.さらに,

m\leq 5 のとき,

(n, m)=(9,4) の場合を除いて, \tilde{J}(n,m) を含む最大な m

距離集合の分類を与えている. (n, m)=(9,4) の場合は,[2] で分類された.

本稿では,[5] でジョンソンスキームに対して行った議論を,ハミング
スキーム H(n, m) に対して行う.ここで,次のような記号を準備する.

84

X_{i}\subset \mathbb{R}^{n} に対して,( X\mathrm{l}

,

.

.

.

,

X_{m} ) =\{(\mathrm{x}_{1}, \ldots, \mathrm{x}_{m})|\mathrm{x}_{i}\in X_{i}\}\subset \mathbb{R}^{mn},(X_{1}, \ldots, X_{m})^{P}=\{(\mathrm{x}_{ $\sigma$(1)}, \ldots, \mathrm{x}_{ $\sigma$(m)})|\mathrm{x}_{i}\in X_{i}, $\sigma$\in S_{m}\}\subset \mathbb{R}^{mn}
ハミングスキーム H(n, m) の埋め込みは,\tilde{H}(n, m)=((1,0^{n-1})^{P}

,

.

.

.

,

( 1, 0^{n-1})^{P})mと表される. \mathrm{j}_{k}\in \mathbb{R}^{mn} を,\mathrm{j}_{k}= (On,

.

.

.

,

0^{n},\sim^{1^{n}

,

On,

.

.

.

,

0^{n} )

k‐th blockと定義すれば,任意の \mathrm{x}\in\tilde{H}(n, m)となる.ここで,,

k\in\{1, . . . , m\} に対して, (\mathrm{x},\mathrm{j}_{k})=1(, ) は標準内積であるとする.したがって, \tilde{H}(n, m) は,\mathbb{R}^{m(n-1)} 上の m 距離集合であると見なすことが出来る.ハミングスキームのボーズメスナー代数の幕等元をみることで,次元 m(n-1) はハミングス
キームの m 距離集合としての埋め込みを含む,最小な次元であることが分かる.

本稿は,主に以下の新たに得られた結果を紹介する.第2節では, \tilde{H}(n, m)に m 距離集合の性質を保ったまま加えられることが出来るベクトルの表示を与える.第3節では,ある簡明な方法により, \overline{H}(n, 2) を含む,最大な2距離集合の分類を与える.第4節では,\tilde{H}(n, m) がm

距離集合として極大であることの必要十分条件と, \overline{H}(n, m) が極大でない n の最大値が m^{2}+m-1

であることを紹介する.第5節では, m\geq 4 における,\tilde{H}(n, m) を含む最大な m 距離集合の分類を紹介し,その証明の概略を与える.表3, 4, 5で,\tilde{H}(n, m) を含む最大な与えている.

m

距離集合 X\subset \mathbb{R}^{d}=\mathbb{R}^{m(n-1)} の元の個数 |X| を

85

表3

表4

m=2

表5

2

m=3

m=4

\tilde{H}(n, m) に付け加えられるベクトル\tilde{H}(n, m) の元 \mathrm{y}\in \mathbb{R}^{mn} を次の様に表す.

\displaystyle \mathrm{y}=(y_{1}, \ldots, y_{mn})=\mathrm{y}(q_{i})=\sum_{i=1}^{m}\mathrm{e}_{(i-1)n+q_{i} ,ここで, \mathrm{e}_{i} は \mathbb{R}^{mn} における基本ベクトル,qi\in\{1, . . . , n\} である. \mathrm{x}=距離の性質を保っ(\mathrm{x}_{1}, \ldots, \mathrm{x}_{m})=(x_{1}, \ldots, x_{mn})\in \mathbb{R}^{mn}(\mathrm{x}_{i}\in \mathbb{R}^{n}) が,たまま, \tilde{H}(n, m) に加えられるとする.つまり,任意の k\in\{1, . . . , m\}に対して, (\mathrm{x},\mathrm{j}_{k})=1 であり,任意の y\in\tilde{H}(n, m) に対して, d(\mathrm{x}, \mathrm{y})\in\{I, \sqrt{4}, . . . \sqrt{2m}\} とならなければならない. i を固定し, qj\neq q_{\dot{j}}', i\neq i にm

対して qi=q_{\overline{i}} となる,{qi}, \{q_{\overline{i} \} に対して, d ( \mathrm{x} y(qi))2—d (x, \mathrm{y}(q_{\overline{i} ) ^{2} を
,

考えれば,

x_{(j-1)n+q_{\dot{}}}-x_{(j-1)n+q_{j}'}\in\{0, \pm 1, . . . , \pm(m-1)\}が成り立つことが分かる.つまり,各ブロック \mathrm{x}_{j} の成分の差は整数である
ことが分かった.さらに, \mathrm{x}_{j} の成分の和が1であることに注意すれば, \mathrm{x}_{j}は次の様に表すことが出来る.

\mathrm{x}_{j}\in \mathfrak{x}_{j}=p_{j}(k_{0}^{(j)}, \ldots, k_{t_{\dot{} }^{(j)})

86=(\displaystyle\frac{k_{0}^{(j)}{n}k_{1}^{(j)},(\frac{k_{0}^{(j)}{n}-1)^{k_{2}^{(j)}, (\displaystyle\frac{k_{0}^{(j)}{n}-t_{j}+1)^{k_{t_{j}^{(j)}\ldots,

ここで,0\leq k_{i}^{(j)}, \displaystyle \sum_{i=1}^{t_{j} k_{i}^{(j)} =n, k_{0}^{(j)} =1+\displaystyle \sum_{i=1}^{t_{j}}(i-1)k_{i}^{(j)} \in \mathbb{Z},

1\leq t_{j}\leq m,\displaystyle \sum_{j=1}^{m} tj\leq 2m-1
\mathrm{x}\in \mathfrak{x}j,

(2.1)

.

\mathrm{y}\in\overline{H}(n, m) に対して,

l_{i}^{(j)}(\mathrm{x}, \mathrm{y})=l_{i}^{(j)}=|\{q|y_{(j-1)n+q}=1, x_{(j-1)n+q}=k_{0}^{(j)}/n-i+1\}|\in\{0 1 \}.
,と定義すれば,d(\displaystyle\mathrm{x},\mathrm{y})^{2}=\sum_{j=1}^{m}(1-n2k_{0}^{(j)}-\frac{k_{0}^{(j)^{2} {n}+\sum_{i=1}^{t_{j} i^{2}k_{i}^{(j)}+2\sum_{i=1}^{t_{j} il_{i}^{(j)}(2.2)と表すことが出来る.

3

m=2 の場合\tilde{H}(n, 2) を含む極大な2距離集合の分類を,簡明な方法を用いて与える. \mathrm{x}\in \mathbb{R}^{2n} が, \tilde{H}(n, 2) へ2距離の性質を保ったまま付け加えら
この節では,

れると仮定する.式(2.1) より,(tl, t2 ) =(1,1) (2, 1),,る.よって,\mathrm{x}または (1,2) となは,\displaystyle\mathrm{x}\in(\frac{k_{0}^{(1)}{n}k_{1}^{(1)},(\frac{k_{0}^{(1)}{n}-1)^{n-k_{1}^{(1)} ^{P}\frac{1}{n} )^{P}と表せる,ここで k_{0}^{(1)}=1+n-k_{1}^{(1)}式(2.2) より, \mathrm{y}\in\tilde{H}(n, 2) に対して,d(\displaystyle \mathrm{x}, \mathrm{y})^{2}=-1-\frac{1}{n}+k_{0}^{(1)}-\frac{k_{0}^{(1)^{2} }{n}+2l_{1}^{(1)}+4l_{2}^{(1)}\in\{2, 4\}87となる.このことから,-1-\displaystyle \frac{1}{n}+k_{0}^{(1)}-\frac{k_{0}^{(1)^{2} {n}=0となり,

n=k^{(1)}+1+2/(k_{0}^{(1)}-1) を得る.ここで可能な値は, (n, k_{0}^{(1)})=(5,2) (5, 3) のみであり, \mathrm{x} は,

X_{1}=( \displaystyle \frac{2}{5}4, -\frac{3}{5})^{P}, \displaystle\frac{1}5 )^{P},

または

X2=(\displayst le\left(\begin{ar y}{l 3^{ }&2^{ }\ \overline{5}&-\overline{5} \end{ar y}\right),\frac{1}5 )^{P}に含まれる. X_{1}\cup X_{2} の任意の2点問の距離を考慮すれば,\tilde{H}(n, 2) を含む

極大な2距離集合は,ブロックの置換を除いて,( \displaystyle\frac{2}{5}4,-\frac{3}{5})^{P}, \displayst le\frac{1}5 )\cup(\frac{1}5 ,\left(\begin{ar y}{l 3^{ }&2^{ }\ \overline{5}&-\overline{5} \end{ar y}\right)

俺\tilde{H}(n, 2)[40点],となることが分かる.

4\tilde{H}(n, m) が極大であるための必要十分条件
この節では,\tilde{H}(n, m) が \mathbb{R}^{n(m-1)} 上のm距離集合として極大であるための必要十分条件を紹介する.第2節から, \mathrm{x}\in \mathbb{R}^{mn} が距離集合の性質を保ったまま \tilde{H}(n, m) に付け加えられるとすれば,\mathrm{x}\in \mathfrak{X}=\mathfrak{X}(\{k_{i}^{(j)}\}_{0\leq i\leq t_{j},1\leq j\leq m})=(\mathfrak{x}_{1}, . . . , \mathfrak{x}_{m})となる.もし, \mathfrak{X} のある元が,\tilde{H}(n, m) に付け加えられるならば, \mathfrak{X} の全ての元がH‐(n, m) に付け加えられることに注意する. \mathrm{x}\in \mathfrak{X} に対して,

M_{\mathfrak{X} =\displaystyle \max d(\mathrm{x}, \mathrm{y})^{2}\mathrm{y}\in\tilde{H}(n,m)とする.ここで M_{\mathfrak{X} は,元 \mathrm{x}\in \mathfrak{X} の選び方に依らない.このとき,次が成
り立つ.

88

補題4.1. \mathrm{x}\in \mathfrak{X} が m 距離の性質を保ったまま \tilde{H}(n, m) に付け加えられる

必要十分条件は, M_{\mathfrak{X} が偶数で, M_{\mathfrak{X}}\leq 2m を満たすことである.

\mathfrak{X}=\mathfrak{X}(\{k_{i}^{(j)}\}) に対して,もし t_{l}\geq 3 となる l が存在するとき,鰐を\mathfrak{X}'=X\'{i} =\mathfrak{X}(\{k^{\prime(j)}\}) と定義する,ここで k_{i}^{\prime(j)} は次のように与えられる.
\bullet\bulletk_{i}^{\prime(j)}=k_{i}^{(j)},t_{l}\geq 4 のとき, k_{1}^{;(l)}=k^{(l)}-1, k_{2}^{\prime(l)}=k^{(l)}+1, k_{t}^{;(l_{-1}^{)}}=k_{t_{l}-1}^{(l)}+1,(j, i)\neq(l, 1) (l, 2) (l tl -1) (l, t_{l}) のとき,
,

,

,

,

k_{t_{l} ^{\prime(l)}=k_{t_{l} ^{(l)}-1,\bullet t_{l}=3 のとき,

例えば,k^{\prime(l)}=k^{(l)}-1, k_{2}^{\prime(l)}=k^{(l)}+2, k_{3}^{\prime(l)}=k_{3}^{(l)}-!.

\tilde{H}(6,4) に\displaystyle\mathfrak{X}=( \frac{3}{2},\frac{1}{2} -\frac{1}{2}3)^{P},\frac{1}{6} ,\frac{1}{6} ,\frac{1}{6} )の任意の元は付け加えられるが,l=1 に対して,上の操作を行えば,\displaystyle\mathfrak{X}_{1}'=( \frac{1}{2}4-\frac{1}{2} )^{P},\frac{1}{6} ,\frac{1}{6} ,\frac{1}{6} \mathrm{I}-となる.この操作 \mathfrak{X}' について,次が成り立つ.

補題4.2. M_{\mathfrak{X} を偶数であるとする.そのとき, M_{\mathfrak{X}'} も偶数で, M_{\mathfrak{X}}>M_{\mathfrak{X}'}を満たす.

補題4.1, 4.2により,もし,\mathfrak{X} の元が\tilde{H}(n, m) に付け加えられるならば,\mathfrak{X}' の元も \tilde{H}(n, m) に付け加えられる.この操作を繰り返すことで,全ての\tilde{H}(n, m) に付け加えられる元を持つ \mathfrak{X}_{0} を構成することができる.つまり, \tilde{H}(n, m) が極大でないことは,任意の j に対してち \leq 2 をみたす \mathfrak{X} で \tilde{H}(n, m) に元が付け加えらるものがあるかをどうj に対して, tj\leq 2 を満たし,かで判断できる.それが主なアイデアとなり次を得る.
補題4.3. 次の2条件は同値である.

(1) \tilde{H}(n, m) は m 距離集合として,極大でない.

89(2) 整数 l, k^{(1)}k_{0}^{(m)} が存在して, n\geq k_{0}^{(1)}\geq\geq k_{0}^{(l)}>1=
k_{0}^{(l+1)}=\cdots=k_{0}^{(m)} を満たし,ある i に対して k_{0}^{(i)}\neq n かつ
.

,

.

.

.

.

.

,

,

\displaystyle \sum_{j=1}^{m}\frac{k_{0}^{(j)}(n-k_{0}^{(j)} {n}+2l(4.1)

が 2m 以下の偶数である.

補題4.3と初等的な M_{\mathfrak{X} の評価により,次の定理を得る.
定理4.4.

\tilde{H}(n, m) がm

距離集合として極大でない最大の n は m^{2}+m-1である.

\tilde{H}(n, m) を含む最大な

5

本節では,

方法について述べていく.まず,り,全て列挙する.

距離集合\tilde{H}(n, m) を含む最大な

m=3 , 4に対し,ての n に対して,補題4.3 (2)

m

m

m

距離集合の分類のを固定し, n\leq m^{2}+m-1 を満たす全を満た、す (k_{0}^{(1)}, \ldots, k_{0}^{(m)}) をコンピュータによ

m=3 , 4のとき,表6で(k_{0}^{(1)}, \ldots, k_{0}^{(m)}) から得られる

Xo=\mathfrak{X}(\{k_{i}^{(j)}\}) をブロックの置換を除いて示す.
\mathfrak{X}' と逆の操作を,

M_{\mathfrak{X}_{\text{。}}}<2m を満たす \mathfrak{X}_{0} に対して行うことで,\tilde{H}(n, m)に加えることができる元をもつ \mathfrak{X}(\{k_{i}^{(j)}\}) を全て与えることが出来る.表7

は,Xo から得られた \mathfrak{X} のリストである.
次に,いつ2点 \mathrm{x}, \mathrm{y}\in \mathfrak{X}(\{k_{i}^{(j)}\}) が \tilde{H}(n, m) へ同時に付け加えられる($\alpha$^{k_{1}}, ( $\alpha$-1)^{k_{2}})^{P} ( resp. ($\alpha$^{k_{1}}, ( $\alpha$-1)^{k_{2}}, ( $\alpha$-2)^{k_{3}})^{P}) が(1^{k_{1}},0^{k_{2}})^{P} ( resp. (1^{k_{1}},0^{k_{2}}, -1^{k_{3}})^{P}) と等長同型であることに注意する.
かを考える.

表8の\mathfrak{X}(\{k_{i}^{(j)}\}) を除けば,表6の \mathfrak{X}(\{k_{i}^{(j)}\}) の全ての元は, \tilde{H}(n, m) へ同時に付け加えられる.Erdós‐Ko‐Rado の定理の類似 [7, 18, 3, 13, 12, 10, 9, 2]を用いることで,表8のように,る,\tilde{H}(n, m) に全ての元を同時に付け加えられ\mathfrak{X}(\{k_{i}^{(j)}\}) の最大な部分集合を分類することが可能である.ここでは,次の記号を用いた.

禽 (k, t)=\{(x_{1}, \ldots, x_{n})\in(1^{k}, 0^{n-k})^{P}:|\{i\in\{1, . . . , t+2r\}:x_{i}=1\}|\geq t+r\}.

90

表6

\tilde{H}(n, m) へ付け加えられる元をもつ Io

表7Xo から得られる \mathfrak{X}

露 (k, t ko )= { \mathrm{x}\in(ko, (k_{0}-n)^{n-k})^{P}|1/n(\mathrm{x}-(k_{0}-n)1)\in 禽 (k, t) }.
,表9は,表7の \mathfrak{X} に対して,同時に \tilde{H}(n, m) に加えられる最大部分集合を示している.主に,コンピューターに依る分類と,[2] のある種の\mathrm{E}\mathrm{r}\mathrm{d}\acute{\acute{\mathrm{o} \mathrm{s}-\mathrm{K}\mathrm{o}−Rado の定理の類似の結果を用いた.

91

表8

\mathrm{E}\mathrm{r}\mathrm{d}\acute{\acute{\mathrm{o} \mathrm{s}-\mathrm{K}\mathrm{o} ‐Radoの定理等が必要な

表9次に,異なる \{k_{i}^{(j)}\},
が,いつ\tilde{H}(n, m)\mathfrak{X}(\{k_{i}^{(j)}\})

表7の \mathfrak{X} の最大部分集合\{k^{\prime(j)}\} に対して, \mathrm{x}\in \mathfrak{X}(\{k^{(j)}\}) \mathrm{y}\in \mathfrak{X}(\{k_{i_{\ve } ^{\prime(j)}\}),に同時に付け加えられるか考える.ベク トル(x_{11}, \ldots, x_{1n}, \ldots, x_{m1}, \ldots, x_{mn})は,全ての i\in\{1, . . . , m\},\in\mathfrak{X}(\{k_{i}^{(j)}\}) が標準的と呼ばれるの

l\in\{1, . . . , n-1\} に対して, x_{i,l}\geq x_{i,l+1} を満たすときにいう.次の補題が有効である.
補題5.1.

\mathfrak{X}(\{k^{(j)}\}) \mathfrak{X}(\{k_{i}^{\prime(j)}\}) は異なると仮定する.そのとき,次が同値
,

92

である.

(1) ある \mathrm{x}\in \mathfrak{X}(\{k_{i}^{(j)}\}),\mathrm{y}\in \mathfrak{X}(\{k_{i}^{\prime(j)}\}) が存在して, d(\mathrm{x}, \mathrm{y})^{2} \in\{2, 4, . . . , 2m\} を満たす.
(2) 標準的な \mathrm{x}'\in \mathfrak{X}(\{k_{i}^{(j)}\}),\mathrm{y}'\in \mathfrak{X}(\{k_{i}^{\prime(j)}\}) に対して, d(\mathrm{x}', \mathrm{y}')^{2}\in\{2, 4, . . . , 2m\} を満たす.
さらに,もし\displaystyle \mathrm{x}\in \mathfrak{X}(\{k_{i}^{(j)}\}),\mathrm{y}\in \mathfrak{X}(\{k_{i}^{ $\gamma$(j)}\})^{d(\mathrm{x},\mathrm{y})^{2} \max\in\{2, 4, . . 2m\},を満たすならば,全ての組 \mathrm{x}\in \mathfrak{X}(\{k_{i}^{(j)}\}),\mathrm{y}\in \mathfrak{X}(\{k_{i}^{\prime(j)}\}) は, d(\mathrm{x}, \mathrm{y})^{2}\in\{2, 4, . . . , 2m\} を満たす.

V=V(n, m) を \tilde{H}(n, m) に付け加えられる元を持つ \mathfrak{X}(\{k_{i}^{(j)}\}) の族であるとする.標準的な x'\in \mathfrak{X}, y'\in \mathfrak{X}' に対して,辺集合 E=\{(\mathfrak{X}, \mathfrak{X}

d(x', y')\in\{2, 4, . . . , 2m\}\} を定義することで,V にグラフ構造 \mathcal{G}(n, m)=(V, E) を与える.ソフトウェアMagma を用いて, \mathcal{G}(n, m) の極大クリークを分類することが出来る.補題5.1を用いれば,((3,0^{2})^{P}, 1^{3},1^{3}, (4,1, -2)^{P}),(1^{3}, (3,0^{2})^{P}, 1^{3}, (5, -1^{2})^{P}) の組を除けば,隣接する \mathfrak{X} 劣, に対して,全て,の組 \mathrm{x}\in \mathfrak{X}, \mathrm{x}'\in \mathfrak{X}' が,同時に \overline{H}(n, m) へ付け加えられることが分かる.

\tilde{H}(n, m) へ同時に付け加えられる \mathfrak{X}の最大部分集合 X に置き換えることで, \tilde{H}(n, m) の含む最大な距離集合
したがって,極大クリークの頂点劣を,mが分類できる.表10が,その最大 m 距離集合のリストである.

参考文献[1] S. Adachi, R. Hayashi, H. Nozaki, and C. Yamamoto, Maximal m‐
distance setscontaining the representation of the Hamming graph

H(n, m) preprint, \mathrm{a}\mathrm{r}\mathrm{X}\mathrm{i}\mathrm{v}:1602.01215.
,[2] S. Adachi, and H. Nozaki, On the largest subsets avoiding the diam‐eter of(0, \pm 1) ‐vectors, to appear in Ars Math. Contemp.

93

表10

(x_{1}, x_{n})^{C}=\{(x_{1+i}, x_{n+i}) i \in \mathbb{Z}/n\mathbb{Z}\},\displaystyle \bigcup_{i\in \mathbb{Z}/n\mathbb{Z}(X_{1+i},\ldots,X_{n+i})},(X_{2}, X_{1}, X_{4}, X_{3}).

\tilde{H}(n, m) に加えられる最大集合 X(X_{1}, X_{2}, X_{3}, X_{4})^{(12)(34)}=(X_{1}, \ldots, X_{n})^{C}(X_{1}, X_{2}, X_{3)}X_{4})94[3] R. Ahlswede, and L.H. Khachatrian, The complete intersection theo‐remfor systems of finite sets, Europ. J. Combin. 18 (1997), 125‐136.

[4] E. Bannai, E. Bannai, and D. Stanton, An upper bound for the car‐dinality of an s ‐distance subset in real Euclidean space, II, Combina‐
torica 3(1983), 147‐152.

[5] E. Bannai, T. Sato, and J. Shigezumi, Maximal m‐distance sets con‐taining the representation of the Johnson graph J(n, m),

Discrete

Math. 312 (2012), no. 22, 3283‐3292.

[6] P. Erdó s, and P. Fishburn, Maximum planar sets that determine k\acute{}distances, Discrete Math. 160 (1996), 115‐125.
\acute{}[7] P. Erdó \mathrm{s}C. Ko, and R. Rado, Intersection theorems for systems of,

Quart. J. Math. Oxford Ser. (2) 12 (1961), 313‐320.

finite sets,[8] S. J. Einhorn, and I. J. Schoenberg, On euclidean sets having only two
distances between points. I. II. Nederl. Akad. Wetensch. Proc. Ser. A

69=Indag.

Math. 28 (1966), 479‐488, 489‐504.

[9] P. Frankl, and N. Tokushige, Some best possible inequalities concern‐
ing cross‐intersecting families, J. Combin. Theory, Ser. A 61 (1992),
87‐97.

[10] A.J.W. Hilton, and E.C. Milner, Some intersection theorems for sys‐
tems of finite sets,

Quart. J. Math. Oxford 18 (1967), 369‐384.

[11] P. Lisoněk, New maximal two‐distance sets, J. Combin. Theory, Ser.
A 77 (1997), 318‐338.

[12] M. Matsumoto, and N. Tokushige, The exact bound in the Erdós‐
Ko‐Rado theorem for cross‐intersecting families, J. Combin.

TheorySer. A52 (1989), no. 1, 90‐97.

[13] L. Pyber, A new generalization of the Erdós‐Ko‐Rado theorem, J.
Combin.

Theory Ser. A 43 (1986), no, 1, 85‐90.

[14] M. Shinohara, Classification of three‐distance sets in two dimensional
Euclidean space, European J. Combin. 25 (2004), 1039‐1058.

95[15] M. Shinohara, Uniqueness of maximum planar five‐distance sets,
Discrete Math. 308 (2008), 3048‐3055.

[16] M. Shinohara, Uniqueness of maximum three‐distance sets in thethree‐dimensional Euclidean space, \mathrm{a}\mathrm{r}\mathrm{X}\mathrm{i}\mathrm{v}:1309.2047.

[17] X. Wei, A proof of Erdós‐Fishburns conjecture for g(6)=13 Elec‐,tron. J. Comb.

19(4) (2012), #P38.

[18] R.M. Wilson, The exact bound on the Erdós‐Ko‐Rado theorem,
Combinatorica 4 (1984), 247‐257.