コンウェイの99グラフ問題
| パラメータ (99,14,1,2) を持つ強正則グラフは存在しますか? | 
|
コンウェイの99グラフ問題（コンウェイの99グラフもんだい、英: Conway's 99-graph problem）はグラフ理論の未解決問題の一つであり、次の性質を持つ99個の頂点からなる無向グラフが存在するかどうかを問う。
- 任意の隣接する2頂点がちょうど1個の共通の隣接頂点を持ち、任意の隣接しない2頂点がちょうど2個の共通の隣接頂点を持つ。同じことだが、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの4-閉路の向かい合う2頂点となる。
ジョン・ホートン・コンウェイはこの問題の解決に対して1000ドルの賞金を提示している[1]。
性質
[編集]もしそのようなグラフが存在すれば、必ず局所線形グラフ（locally linear graph）で、パラメータ (99,14,1,2) の強正則グラフである。1、3、4番目のパラメータはこの問題の条件をコード化したもので、グラフの頂点数が99個であること、どの隣接する2頂点もちょうど1個の共通する隣接頂点を持つこと、どの隣接しない2頂点もちょうど2個の共通する隣接頂点を持つこと、を表している。2番目のパラメータはグラフが14-正則グラフであることを表している[2]。
もしこのようなグラフが存在すれば、それには位数11の対称性（グラフの自己同型）は存在せず、したがって任意の頂点が任意の頂点へ写るような対称性は持たないことがわかっている[3]。対称性に関してはこれ以外にも制約が課されねばならないことが知られている[4]。
歴史
[編集]このようなパラメータを持つグラフが存在する可能性は、既に1969年にノーマン・L・ビッグスによって示唆されており[5]、またその存在が未解決問題であることがコンウェイ以前に他の著者によって記されている[3][6][7][8]。コンウェイ自身はこの問題に 1975年から取り組み始めたが[6]、賞金を提示したのは2014年、DIMACS Conference on Challenges of Identifying Integer Sequences において提示された問題群の一部としてであった。この問題群には thrackle予想、ダンツァー集合での間隙の最小値に関するもの、sylver coinageゲームで16手後にどちらのプレイヤーが勝つかを問う問題が含まれている[1]。
関連するグラフ
[編集]より一般に、任意の辺がただ一つの三角形の1辺となり、任意の隣接しない2頂点がただ一つの四角形の向かい合う頂点となるような強正則グラフには、5通りのパラメータの組しか許されない。そのうち存在がわかっているのは2通りの組だけであり、頂点数が9のペイリーグラフ（3-3 duoprism のグラフ）はパラメータが (9,4,1,2) 、バーレカンプ–ヴァン・リント–ザイデルグラフはパラメータが (243,22,1,2) である。99グラフ問題は、5通りのパラメータの組の中で存在がわかっていないもののうち最小のものである[4]。
脚注
[編集]- ^ a b Conway, John H., Five $1,000 Problems (Update 2017), On-Line Encyclopedia of Integer Sequences 2019年2月12日閲覧。. See also オンライン整数列大辞典の数列 A248380.
- ^ Zehavi, Sa'ar; David de Olivera, Ivo Fagundes (2017), Not Conway's 99-graph problem, arXiv:1707.08047
- ^ a b Wilbrink, H. A. (August 1984), “On the (99,14,1,2) strongly regular graph”, in de Doelder, P. J.; de Graaf, de, J.; van Lint, J. H., Papers dedicated to J. J. Seidel, EUT Report, 84-WSK-03, Eindhoven University of Technology, pp. 342–355
- ^ a b Makhnev, A. A.; Minakova, I. M. (January 2004), “On automorphisms of strongly regular graphs with parameters , ”, Discrete Mathematics and Applications 14 (2), doi:10.1515/156939204872374, MR2069991
- ^ Biggs, Norman (1971), Finite Groups of Automorphisms: Course Given at the University of Southampton, October–December 1969, London Mathematical Society Lecture Note Series, 6, London and New York: Cambridge University Press, p. 111, MR0327563
- ^ a b Guy, Richard K. (1975), “Problems”, in Kelly, L. M., Proceedings of a Conference held at Michigan State University, East Lansing, Mich., June 17–19, 1974, Lecture Notes in Mathematics, 490, Berlin and New York: Springer-Verlag, pp. 233–244, doi:10.1007/BFb0081147, MR0388240. See problem 7 (J. J. Seidel), pp. 237–238.
- ^ Brouwer, A. E.; Neumaier, A. (1988), “A remark on partial linear spaces of girth 5 with an application to strongly regular graphs”, Combinatorica 8 (1): 57–61, doi:10.1007/BF02122552, MR951993
- ^ Cameron, Peter J. (1994), Combinatorics: topics, techniques, algorithms, Cambridge: Cambridge University Press, p. 331, ISBN 0-521-45133-7, MR1311922
