トーナメント（グラフ理論）

トーナメント
4つの頂点でのトーナメント
頂点	${\displaystyle n}$
エッジ	${\displaystyle {\binom {n}{2}}}$
グラフとパラメータの表

グラフ理論では、トーナメントとは、2 つの頂点の間に2 つの可能な方向のいずれかに 1 つの辺だけを持つ有向グラフです。同様に、トーナメントは無向完全グラフの方向です。(ただし、有向グラフであるため、トーナメントは完全ではありません。完全有向グラフでは、2 つの頂点の間に両方向に 2 つの辺があります。^{[1] )}トーナメントという名前は、グラフを総当たりトーナメントの結果として解釈することに由来しています。総当たりトーナメントでは、各プレーヤーが他のすべてのプレーヤーと 1 回ずつ対戦します。トーナメントでは、頂点はプレーヤーを表し、プレーヤー間の辺は勝者から敗者の方向を指します。

トーナメントの重要な特性の多くは、 1953年にHGランドウによって鶏の群れの優位関係をモデル化するために研究されました。^{[2]トーナメントは}投票理論でも精力的に研究されており、複数の候補者の間での投票者の好みについての部分的な情報を表すことができるため、コンドルセ法の定義の中心となっています。

すべてのプレイヤーが同じ数の他のプレイヤーに勝った場合（入次数 − 出次数= 0）、トーナメントは通常のトーナメントと呼ばれます。

有限個の頂点上のトーナメントにはハミルトン経路、つまりすべての頂点上の有向経路が含まれます ( Rédei 1934)。 ${\displaystyle n}$${\displaystyle n}$

これは に関する帰納法で簡単に示せます。に対してステートメントが成り立つと仮定し、頂点上の任意のトーナメントを考えます。の頂点を 1 つ選び、内の有向パスを考えます。 となるようなパスが存在します。(1 つの可能性として、 を任意のに対して となる最大とする、というものがあります。あるいは、となる最小とする、というものがあります。) は希望どおりに有向パスです。この議論は、ハミルトン パスを見つけるアルゴリズムも提供します。エッジのみを調べる必要がある、より効率的なアルゴリズムが知られています。ハミルトン パスは、トーナメントの最小フィードバック アーク セットと 1 対 1 に対応しています。 ^{[3] Rédei の定理は、} Gallai–Hasse–Roy–Vitaverの定理 の完全グラフに対する特別なケースであり、グラフの方向におけるパスの長さをこれらのグラフの彩色数に関連付けます。^[4]${\displaystyle n}$${\displaystyle n}$${\displaystyle T}$${\displaystyle n+1}$${\displaystyle v_{0}}$${\displaystyle T}$${\displaystyle v_{1},v_{2},\ldots ,v_{n}}$${\displaystyle T\smallsetminus \{v_{0}\}}$${\displaystyle i\in \{0,\ldots ,n\}}$${\displaystyle (i=0\vee v_{i}\rightarrow v_{0})\wedge (v_{0}\rightarrow v_{i+1}\vee i=n)}$${\displaystyle i\in \{0,\ldots ,n\}}$${\displaystyle j\leq i,v_{j}\rightarrow v_{0}}$${\displaystyle i}$${\displaystyle \forall j>i,v_{0}\rightarrow v_{j}}$$${\displaystyle v_{1},\ldots ,v_{i},v_{0},v_{i+1},\ldots ,v_{n}}$$${\displaystyle O(n\log n)}$

トーナメントに関するもう 1 つの基本的な結果は、すべての強く連結したトーナメントにはハミルトン閉路が存在することです。^[5]さらに強いことに、すべての強く連結したトーナメントは頂点汎巡回的です。つまり、各頂点、および 3 からトーナメントの頂点数までの範囲の各頂点 に対して、を含む長さ の閉路が存在します。 ^[6]トーナメントが-強く連結されているとは、のすべての頂点セットに対してが強く連結されている場合です。トーナメントが 4 強く連結されている場合、各頂点ペアはハミルトン パスで連結できます。^[7] -強く連結したトーナメントの最大 個の弧のすべてのセットに対して、 はハミルトン閉路を持ちます。^[8]この結果は Bang-Jensen、Gutin、Yeo (1997) によって拡張されました。^[9]${\displaystyle v}$${\displaystyle k}$${\displaystyle k}$${\displaystyle v}$${\displaystyle T}$${\displaystyle k}$${\displaystyle U}$${\displaystyle k-1}$${\displaystyle T}$${\displaystyle TU}$${\displaystyle B}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle T}$${\displaystyle TB}$

およびとなるトーナメントは推移的 と呼ばれます。言い換えると、推移的トーナメントでは、頂点はエッジ関係によって（厳密に）完全に順序付けられ、エッジ関係は到達可能性と同じです。 ${\displaystyle ((a\rightarrow b)}$${\displaystyle (b\rightarrow c))}$ ${\displaystyle \Rightarrow}$ ${\displaystyle (a\rightarrow c)}$

頂点上のトーナメントでは、次のステートメントは同等です。 ${\displaystyle T}$${\displaystyle n}$

1. ${\displaystyle T}$推移的です。
2. ${\displaystyle T}$厳密な全順序付けです。
3. ${\displaystyle T}$非循環的です。
4. ${\displaystyle T}$長さ 3 のサイクルは含まれません。
5. のスコアシーケンス（出次数の集合）は です。${\displaystyle T}$${\displaystyle \{0,1,2,\ldots ,n-1\}}$
6. ${\displaystyle T}$ハミルトン経路は 1 つだけあります。

推移的トーナメントは、無向グラフのクリークと同様の役割を果たします。特に、頂点上のすべてのトーナメントには、頂点上の推移的サブトーナメントが含まれます。証明は簡単です。このサブトーナメントの一部となる頂点を 1 つ選択し、サブトーナメントの残りを、 の入ってくる隣接点の集合または の出ていく隣接点の集合のいずれか大きい方で再帰的に形成します。たとえば、7 つの頂点上のすべてのトーナメントには、3 つの頂点の推移的サブトーナメントが含まれます。7つの頂点上のPaley トーナメントは、これが保証できる最大のものであることを示しています。^[10]ただし、Reid と Parker (1970) は、 のより大きな値に対してこの境界が厳密ではないことを示しました 。^[11]${\displaystyle n}$${\displaystyle 1+\lfloor \log _{2}n\rfloor }$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle n}$

Erdős & Moser (1964) は、頂点上に、サイズ の推移的サブトーナメントのないトーナメントが存在することを証明しました。彼らの証明では、計数論法が使用されています。つまり、ラベル付き頂点 上で、要素の推移的トーナメントが、より大きなトーナメントのサブトーナメントとして発生する方法の数はであり 、が より大きい場合、この数は、同じラベル付き頂点セット上の異なるトーナメントのそれぞれ内で推移的トーナメントが発生することを許容するには小さすぎます。^[10]${\displaystyle n}$${\displaystyle 2+2\lfloor \log _{2}n\rfloor }$${\displaystyle k}$${\displaystyle n}$$${\displaystyle {\binom {n}{k}}k!2^{{\binom {n}{2}}-{\binom {k}{2}}},}$$${\displaystyle k}$${\displaystyle 2+2\lfloor \log _{2}n\rfloor }$${\displaystyle 2^{\binom {n}{2}}}$${\displaystyle n}$

すべてのゲームに勝ったプレイヤーが、当然トーナメントの勝者となる。しかし、非推移的なトーナメントの存在が示すように、そのようなプレイヤーは存在しないかもしれない。すべてのプレイヤーが少なくとも 1 ゲーム負けるトーナメントは、1-パラドキシカル トーナメントと呼ばれる。より一般的には、のすべての-元部分集合に対して、すべての に対してとなる頂点が に存在する場合、トーナメントは -パラドキシカルであると呼ばれる。確率的方法を用いて、ポール・エルデシュは、 の任意の固定値に対して、 であれば、 上のほぼすべてのトーナメントが-パラドキシカルであることを示した。 [ ^12]一方、簡単な議論から、任意の -パラドキシカル トーナメントには少なくとも プレイヤーがいなければならないことが示され、これは1965 年にエスターとジョージ・シェケレスによってに改良された。^[13]プレイヤーがいる-パラドキシカル トーナメントの明示的な構築は、グラハムとスペンサー (1971)によって、ペイリー トーナメントとして行われている。 ${\displaystyle T=(V,E)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle S}$${\displaystyle V}$${\displaystyle v_{0}}$${\displaystyle V\setminus S}$${\displaystyle v_{0}\rightarrow v}$${\displaystyle v\in S}$${\displaystyle k}$${\displaystyle |V|\geq k^{2}2^{k}\ln(2+o(1))}$${\displaystyle V}$${\displaystyle k}$${\displaystyle k}$${\displaystyle 2^{k+1}-1}$${\displaystyle (k+2)2^{k-1}-1}$${\displaystyle k}$${\displaystyle k^{2}4^{k-1}(1+o(1))}$

いかなるトーナメントの凝縮もそれ自体が推移的なトーナメントである。したがって、推移的でないトーナメントであっても、トーナメントの強く連結された成分は完全に順序付けられる可能性がある。^[14]

トーナメントのスコア シーケンスは、トーナメントの頂点の出次数の非減少シーケンスです。トーナメントのスコア セットは、そのトーナメントの頂点の出次数である整数のセットです。

ランダウの定理（1953）減少しない整数列がスコア列となるのは、次の場合のみである：^[2]${\displaystyle (s_{1},s_{2},\ldots ,s_{n})}$

1. ${\displaystyle 0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}}$
2. ${\displaystyle s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},{\text{ for }}i=1,2,\ldots ,n-1}$
3. ${\displaystyle s_{1}+s_{2}+\cdots +s_{n}={n \choose 2}.}$

をサイズ の異なるスコアシーケンスの数とします。シーケンス( OEISのシーケンスA000571 ) は次のように始まります。 ${\displaystyle s(n)}$${\displaystyle n}$${\displaystyle s(n)}$

1、1、1、2、4、9、22、59、167、490、1486、4639、14805、48107、...

ウィンストンとクライトマンは、十分に大きいnに対して次のことを証明しました。

${\displaystyle s(n)>c_{1}4^{n}n^{-5/2},}$

タカーチは後に、 いくつかの合理的だが証明されていない仮定を用いて、 ${\displaystyle c_{1}=0.049.}$

${\displaystyle s(n)<c_{2}4^{n}n^{-5/2},}$

ここで^[15]${\displaystyle c_{2}<4.858.}$

これらを合わせると、次のことが証明されます。

${\displaystyle s(n)\in \Theta (4^{n}n^{-5/2}).}$

ここで は漸近的に厳しい境界を表します。 ${\displaystyle \Theta }$

ヤオは、非負整数の空でない集合はどれも、あるトーナメントのスコア集合であることを示した。^[16]

社会的選択理論では、トーナメントは選好プロファイルの多数決関係として自然に生じる。^{[17] を}選択肢の有限集合とし、上の線形順序のリストを考える。各順序を投票者の選好ランキングと解釈する。上の の（厳密な）多数決関係は、投票者の過半数がを好む場合に限り、となるように定義される。投票者の数が奇数の場合、多数決関係は頂点集合 上のトーナメントの優位関係を形成する。 ${\displaystyle A}$${\displaystyle P=(\succ _{1},\dots ,\succ _{n})}$${\displaystyle A}$${\displaystyle \succ _{i}}$${\displaystyle i}$${\displaystyle \succ _{\text{maj}}}$${\displaystyle P}$${\displaystyle A}$${\displaystyle a\succ _{\text{maj}}b}$${\displaystyle a}$${\displaystyle b}$${\displaystyle |\{i\in [n]:a\succ _{i}b\}|>|\{i\in [n]:b\succ _{i}a\}|}$${\displaystyle n}$${\displaystyle A}$

McGarveyの補題により、頂点上のすべてのトーナメントは、最大で投票者の多数決関係として得られる。 ^[18] StearnsとErdős & Moserによる結果により、頂点上のすべてのトーナメントを誘導するには投票者が必要であることが後に確立された。 ^[19]${\displaystyle m}$${\displaystyle m(m-1)}$${\displaystyle \Theta (m/\log m)}$${\displaystyle m}$

ラスリエ（1997）は、頂点の集合がどのような意味でトーナメントの「勝者」の集合と呼べるのかを研究している。^[20]これは、政治経済の形式モデルにおいて、民主的なプロセスの結果はどのようなものになり得るかを研究する上で、政治学において有用であることが明らかになった。^[21]

• 有向グラフ
• ペイリートーナメント
• サムナーの予想
• トーナメントソリューション

• オースティン・スミス、D.; バンクス、J. (1999)、ポジティブ政治理論、ミシガン大学出版局
• Bang-Jensen, J.; Gutin, G .; Yeo, A. (1997)、「トーナメントで規定された弧を回避するハミルトンサイクル」、組合せ論、確率および計算、6 : 255–261
• Bar-Noy, A.; Naor, J. (1990)、「トーナメントにおけるソート、最小フィードバックセット、ハミルトンパス」、SIAM Journal on Discrete Mathematics、3 (1): 7–20、doi :10.1137/0403002
• ブラント、フェリックス。ブリル、マーカス。 Harrenstein、Paul (2016)、「第 3 章: トーナメント ソリューション」、Brandt、Felix 著。コニッツァー、ヴィンセント。エンドリス、ウレ。ラング、ジェローム。 Procaccia、Ariel D. (編)、Handbook of Computational Social Choice、ケンブリッジ大学出版局、ISBN 9781107060432
• Camion, Paul (1959)、「Chemins et circuis hamiltoniens desgraphes complets」、Comptes Rendus de l'Académie des Sciences de Paris (フランス語)、249 : 2151–2152
• Erdős, P. (1963)、「グラフ理論における問題について」(PDF)、The Mathematical Gazette、47 : 220–223、JSTOR  3613396、MR  0159319
• エルデシュ、P. ; Moser, L. (1964)、「順序付けの和集合としての有向グラフの表現について」(PDF)、Magyar Tud。アカド。マット。クタト国際空港ケズル。、9 : 125–132、MR  0168494
• Fraisse, P.; Thomassen, C. (1987)、「トーナメント問題に対する建設的解法」、Graphs and Combinatorics、3 : 239–250。
• グラハム、RL ;スペンサー、JH (1971)、「トーナメント問題に対する建設的解法」、カナダ数学速報、14 :45–48、doi :10.4153/cmb-1971-007-1、MR  0292715。
• ハラリー、フランク;モーザー、レオ(1966)、「ラウンドロビントーナメントの理論」、アメリカ数学月刊誌、73 (3): 231–246、doi :10.2307/2315334、JSTOR  2315334。
• Havet, Frédéric (2013)、「セクション 3.1: Gallai–Roy の定理と関連する結果」(PDF)、グラフの方向と色付け、フランス、オレロンで開催された SGT 2013 サマースクールの講義ノート、pp. 15–19
• ランダウ、HG（1953）「動物社会の支配関係と構造について。III.スコア構造の条件」、数理生物物理学紀要、15（2）：143-148、doi：10.1007/BF02476378。
• Laslier, J.-F. (1997)、トーナメントソリューションと多数決、Springer
• McGarvey, David C. (1953)、「投票パラドックスの構築に関する定理」、Econometrica、21 (4): 608–610、doi :10.2307/1907926、JSTOR  1907926
• ムーン、JW (1966)、「トーナメントのサブトーナメントについて」、カナダ数学速報、9 (3): 297–301、doi : 10.4153/CMB-1966-038-7。
• ラスロー・レデイ(1934)、「Ein kombinatorischer Satz」、Acta Litteraria Szeged、7 : 39–43。
• リード、KB; パーカー、ET (1970)、「エルデシュとモーザーの予想の反証」、組合せ理論ジャーナル、9 (3): 225–238、doi : 10.1016/S0021-9800(70)80061-8
• スターンズ、リチャード (1959)、「投票問題」、アメリカ数学月刊誌、66 (9): 761–763、doi :10.2307/2310461、JSTOR  2310461
• セーケレス、Ｅ．Szekeres, G. (1965)、「Schütte と Erdős の問題について」、The Mathematical Gazette、49 : 290–293、doi :10.2307/3612854、MR  0186566。
• タカチ・ラヨシュ(1991)、「ベルヌーイ遠回りとそのさまざまな応用」、応用確率論の進歩、23 (3)、応用確率論トラスト: 557–585、doi :10.2307/1427622、JSTOR  1427622。
• Thomassen, Carsten (1980)、「ハミルトン連結トーナメント」、Journal of Combinatorial Theory、シリーズ B、28 (2): 142–163、doi : 10.1016/0095-8956(80)90061-1。
• Yao, TX (1989)、「トーナメントのスコアセットのリード予想について」、中国科学会報、34 : 804–808。

この記事には、 Creative Commons Attribution-Share-Alike Licenseに基づいてライセンスされているPlanetMathのトーナメントの資料が組み込まれています。