サムナーの予想

数学における未解決の問題:

すべての- 頂点トーナメントには、すべての - 頂点指向ツリーがサブグラフとして含まれていますか?${\displaystyle (2n-2)}$${\displaystyle n}$

（数学における未解決の問題がさらに増える）

サムナーの予想（サムナーの普遍トーナメント予想とも呼ばれる）は、極値グラフ理論におけるトーナメントの有向木に関する予想である。これは、あらゆる-頂点木のすべての有向が、あらゆる-頂点トーナメントのサブグラフであると述べている。 ^[1]サウスカロライナ大学のグラフ理論家デビッド・サムナーは、1971年にトーナメントが多角形の普遍グラフであると予想した。この予想は、ダニエラ・キューン、リチャード・マイクロフト、デリック・オスタスによってすべての大規模グラフに対して証明された。^[2]${\displaystyle n}$${\displaystyle (2n-2)}$ ${\displaystyle n}$

多角形を星型とし、そのすべての辺が中心の頂点から葉に向かって外側に向いているとする。すると、多角形 の周りをすべての辺が時計回りに回ることで形成されるトーナメントに、 は埋め込むことができない。なぜなら、このトーナメントでは、すべての頂点の入次数と出次数は に等しいが、 の中心頂点の出次数は より大きいからである。^[3]したがって、もしこれが正しいとすれば、サムナーの予想は多角形の普遍グラフの可能な限り最高のサイズを与えることになる。 ${\displaystyle P}$ ${\displaystyle K_{1,n-1}}$${\displaystyle P}$${\displaystyle 2n-3}$${\displaystyle n-2}$${\displaystyle P}$${\displaystyle n-1}$

ただし、頂点のトーナメントでは、平均出次数は であり、最大出次数は平均以上の整数です。したがって、出次数が の頂点が存在し、これを のコピーの中心頂点として使用できます。 ${\displaystyle 2n-2}$${\displaystyle n-{\frac {3}{2}}}$${\displaystyle \left\lceil n-{\frac {3}{2}}\right\rceil =n-1}$${\displaystyle P}$

この予想に関する以下の部分的な結果が証明されました。

• 漸近的成長率を持つ関数が存在し、その関数はあらゆる-頂点多木があらゆる -頂点トーナメントのサブグラフとして埋め込むことができるという性質を持つ。さらに、より明示的には、 である。^[4]${\displaystyle f(n)}$${\displaystyle f(n)=2n+o(n)}$${\displaystyle n}$${\displaystyle f(n)}$${\displaystyle f(n)\leq 3n-3}$
• 頂点上のトーナメントが葉を持つ多木に対して普遍的であるような関数が存在する。^[5]${\displaystyle g(k)}$${\displaystyle n+g(k)}$${\displaystyle k}$
• 最大次数を持つすべての頂点多木が、頂点を持つすべてのトーナメントのサブグラフを形成するような関数が存在する。が固定定数のとき、 の漸近的成長率はである。^[6]${\displaystyle h(n,\Delta )}$${\displaystyle n}$${\displaystyle \Delta }$${\displaystyle h(n,\Delta )}$${\displaystyle \Delta }$${\displaystyle h(n,\Delta )}$${\displaystyle n+o(n)}$
• 頂点上のあらゆる「ほぼ正規の」トーナメントには、あらゆる-頂点ポリツリーが含まれます。^[7]${\displaystyle 2n-2}$${\displaystyle n}$
• 直径が最大4である-頂点キャタピラーツリーのすべての方向は、すべての -頂点トーナメントのサブグラフとして埋め込むことができます。^[7]${\displaystyle n}$${\displaystyle (2n-2)}$
• あらゆる-頂点トーナメントはあらゆる-頂点樹状突起をサブグラフとして含みます。^[8]${\displaystyle (2n-2)}$${\displaystyle n}$

Rosenfeld (1972)は、-頂点パスグラフ（ ）のすべての方向は、すべての-頂点トーナメントにサブグラフとして埋め込むことができると推測しました。 ^[7] Thomason (1986)による部分的な結果の後、これはHavet & Thomassé (2000a)によって証明されました。 ${\displaystyle n}$${\displaystyle n\geq 8}$${\displaystyle n}$

HavetとThomassé ^[9]は、頂点上のすべてのトーナメントには最大で葉を持つすべてのポリツリーがサブグラフとして含まれるというSumnerの予想を強化した。これはMycroftとNaia（2018）によってほぼすべてのツリーで確認されている。 ${\displaystyle n+k-1}$${\displaystyle k}$

Burr (1980) は、グラフが の色付けで 色以上を必要とするときはいつでも、 のすべての向きに-頂点木のすべての向きが含まれると予想しました。完全グラフでは各頂点に異なる色が必要なので、Sumner の予想は Burr の予想から直ちに導かれます。^[10] Burr が示したように、彩色が の関数として二乗で増加するグラフの向きは、多木に対して普遍的です。 ${\displaystyle G}$${\displaystyle 2n-2}$${\displaystyle G}$${\displaystyle G}$${\displaystyle n}$${\displaystyle n}$

• Burr, Stefan A. (1980)、「有向グラフとハイパーグラフのサブツリー」、第 11 回南東部組合せ論、グラフ理論、コンピューティングに関する会議の議事録 (フロリダ アトランティック大学、フロリダ州ボカラトン、1980 年)、第 1 巻、Congressus Numerantium、第 28 巻、pp. 227–239、MR  0608430。
• Chung, FRK (1981)、「トーナメントにおけるサブツリーに関する注記」、ベル研究所内部メモワーマルド（1983）より引用。
• El Sahili, A. (2004)、「トーナメントのツリー」、Journal of Combinatorial Theory、シリーズ B、92 (1): 183–187、doi : 10.1016/j.jctb.2004.04.002、MR  2078502。
• Häggkvist, Roland; Thomason, Andrew (1991)、「トーナメントにおけるツリー」、Combinatorica、11 (2): 123–130、doi :10.1007/BF01206356、MR  1136161。
• Havet, Frédéric (2002)、「トーナメントにおける木」、離散数学、243 (1–3): 121–134、doi :10.1016/S0012-365X(00)00463-5、MR  1874730。
• Havet, Frédéric; Thomassé, Stéphan (2000a)、「トーナメントにおける有向ハミルトン経路: Rosenfeld の予想の証明」、Journal of Combinatorial Theory、シリーズ B、78 (2): 243–273、doi : 10.1006/jctb.1999.1945、MR  1750898。
• Havet, Frédéric; Thomassé, Stéphan (2000b)、「トーナメントの中央順序: 第 2 近傍問題とサムナーの予想のためのツール」、Journal of Graph Theory、35 (4): 244–256、doi :10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H、MR  1791347。
• キューン、ダニエラ; マイクロフト、リチャード; オストゥス、デリック (2011a)、「サムナーの普遍トーナメント予想の近似バージョン」、Journal of Combinatorial Theory、シリーズ B、101 (6): 415–447、arXiv : 1010.4429、doi :10.1016/j.jctb.2010.12.006、MR  2832810、Zbl  1234.05115。
• キューン、ダニエラ; マイクロフト、リチャード; オストゥス、デリック (2011b)、「大規模トーナメントに対するサムナーの普遍トーナメント予想の証明」、ロンドン数学会紀要、第 3 シリーズ、102 (4): 731–766、arXiv : 1010.4430、doi :10.1112/plms/pdq035、MR  2793448、Zbl  1218.05034。
• Naia, Tássio (2018)、高密度有向グラフの大規模構造 (博士論文)、バーミンガム大学。
• リード、KB; ワーマルド、NC (1983)、「トーナメントでの有向n木の埋め込み」、ハンガリー数学会誌、18 (2–4): 377–387、MR  0787942。
• ローゼンフェルド、M. (1972)、「トーナメントにおける反向ハミルトン経路」、組合せ理論ジャーナル、シリーズ B、12 : 93–99、doi :10.1016/0095-8956(72)90035-4、MR  0285452。
• トーマスン、アンドリュー（1986）、「トーナメントにおけるパスとサイクル」、アメリカ数学会誌、296（1）：167–180、doi：10.2307/2000567、JSTOR  2000567、MR  0837805。
• ワーマルド、ニコラス C. (1983)、「大規模トーナメントのサブツリー」、組み合わせ数学、X (アデレード、1982)、数学講義ノート、第 1036 巻、ベルリン: シュプリンガー、pp. 417–419、doi :10.1007/BFb0071535、ISBN 978-3-540-12708-6、MR  0731598。

• サムナーのユニバーサルトーナメント予想 (1971)、DB West、2008 年 7 月更新。