ゲームグラフ

グラフ理論において、ゲームズグラフは既知の最大の局所線形強正則グラフです。強正則グラフとしてのパラメータは (729,112,1,20) です。これは、頂点数が 729、辺数が 40824 (頂点あたり 112) であることを意味します。各辺は一意の三角形に属し (局所線形グラフです)、隣接しない頂点のペアはそれぞれ 20 個の共有隣接点を持ちます。このグラフは、未発表の通信^{[ 1 ]}でその構成を提案し、関連する構成について記述したRichard A. Games にちなんで名付けられました^{[ 2 ] 。}

工事

このグラフの構築には、56 ポイントのキャップセットが含まれます。 $PG(5,3)$ これは、3要素体上の5次元射影幾何学において、一直線上に3つが並ばない点のサブセットであり、対称性を除いて一意である。^{[ 3 ]} 6次元射影幾何学では、 $PG(6,3)$ は、6次元のアフィン空間に分割できる。 $AG(6,3)$ そしてコピー $PG(5,3)$ これは、アフィン空間に関して無限遠にある点の集合を形成します。ゲームグラフの頂点は、アフィン空間の729個の点です。 $AG(6,3)$ アフィン空間内の各直線は、これらの点のうち3つと、無限遠にある4つ目の点を通ります。グラフには、キャップセットの点を通る3つのアフィン点の直線ごとに三角形が含まれます。^{[ 1 ]}

物件

この構成から、グラフのいくつかの特性がすぐに導き出されます。 $729=3^{6}$ 頂点の数です。アフィン空間の点の数は、基底体のサイズを次元のべき乗で割った値だからです。各アフィン点に対して、キャップセット点を通る直線が 56 本、対応する頂点を含む三角形が 56 個、そして $112=56\times 2$ 頂点の隣接点。また、構成から生じる三角形以外に三角形は存在し得ない。なぜなら、他の三角形は、共通平面で交わる 3 つの異なる線から生じる必要があるからである。 $PG(6,3)$ 3本の線の3つのキャップ設定点はすべて、この平面と $PG(5,3)$ これは直線です。しかし、これはキャップセットの定義特性である「直線上に3つの点を持たない」という性質に反するため、そのような余分な三角形は存在できません。強く正則なグラフの残りの特性である、隣接していないすべての点のペアが同じ数の共有近傍を持つという性質は、5次元キャップセットの特定の特性に依存します。

参考文献

1 2 van Lint, JH ; Brouwer, AE (1984)、「強正則グラフと部分幾何構造」(PDF)、Jackson, David M. ; Vanstone, Scott A. (編)、Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982、London: Academic Press、pp. 85–122、MR 0782310 特に114～115ページを参照。
↑ Games, Richard A. (1983), "次元が5より大きいGF(3)上の射影幾何学のパッキング問題", Journal of Combinatorial Theory , Series A, 35 (2): 126–144 , doi : 10.1016/0097-3165(83)90002-X , MR 0712100 特に、表VII、139ページの項目を参照してください。 $r=5$ そして $d=3$ 。
↑ Hill, Raymond (1978)、「Caps and codes」、Discrete Mathematics、22 (2): 111– 137、doi : 10.1016/0012-365X(78)90120-6、MR 0523299
↑ボンダレンコ、アンドリー V. Radchenko、Danylo V. (2013)、「強く規則的なグラフのファミリーについて」 $\lambda =1$ 「、Journal of Combinatorial Theory、シリーズB、103（4）：521–531、arXiv：1201.0383、doi：10.1016/j.jctb.2013.05.005、MR 3071380
↑キャメロン、ピーター J. (1975)、「部分四角形」、The Quarterly Journal of Mathematics、第 2 シリーズ、26 : 61–73、doi : 10.1093/qmath/26.1.61、MR 0366702
↑ Berlekamp, ER ; van Lint, JH ; Seidel, JJ (1973), "完全三元ゴレイ符号から導出された強正則グラフ" (PDF) , JN Srivastava (編), A Survey of Combinatorial Theory , Amsterdam: North-Holland, pp. 25– 30, doi : 10.1016/B978-0-7204-2262-7.50008-9 , ISBN 9780720422627MR 0364015

[vlb-1] 1 2 van Lint, JH ; Brouwer, AE (1984)、「強正則グラフと部分幾何構造」(PDF)、Jackson, David M. ; Vanstone, Scott A. (編)、Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14–July 2, 1982、London: Academic Press、pp. 85–122、MR 0782310 特に114～115ページを参照。

[g-2] Games, Richard A. (1983), "次元が5より大きいGF(3)上の射影幾何学のパッキング問題", Journal of Combinatorial Theory , Series A, 35 (2): 126–144 , doi : 10.1016/0097-3165(83)90002-X , MR 0712100 特に、表VII、139ページの項目を参照してください。 $r=5$ そして $d=3$ 。

[h-3] Hill, Raymond (1978)、「Caps and codes」、Discrete Mathematics、22 (2): 111– 137、doi : 10.1016/0012-365X(78)90120-6、MR 0523299

[br-4] ボンダレンコ、アンドリー V. Radchenko、Danylo V. (2013)、「強く規則的なグラフのファミリーについて」 $\lambda =1$ 「、Journal of Combinatorial Theory、シリーズB、103（4）：521–531、arXiv：1201.0383、doi：10.1016/j.jctb.2013.05.005、MR 3071380

[c-5] キャメロン、ピーター J. (1975)、「部分四角形」、The Quarterly Journal of Mathematics、第 2 シリーズ、26 : 61–73、doi : 10.1093/qmath/26.1.61、MR 0366702

[bvls-6] Berlekamp, ER ; van Lint, JH ; Seidel, JJ (1973), "完全三元ゴレイ符号から導出された強正則グラフ" (PDF) , JN Srivastava (編), A Survey of Combinatorial Theory , Amsterdam: North-Holland, pp. 25– 30, doi : 10.1016/B978-0-7204-2262-7.50008-9 , ISBN 9780720422627MR 0364015

[ 1 ]

[ 2 ] 。

[ 3 ]

4

[ 5 ]

[ 6 ]

工事

物件

関連グラフ

参考文献