การแข่งขัน
การแข่งขันบนจุดยอด 4 จุด
จุดยอด	${\displaystyle n}$
ขอบ	${\displaystyle {\binom {n}{2}}}$
ตารางกราฟและพารามิเตอร์

ในทฤษฎีกราฟทัวร์ นาเมน ต์คือกราฟแบบมีทิศทางที่มีขอบเพียงหนึ่งเดียวระหว่างจุดยอด สองจุดใดๆ ในทิศทางใดทิศทางหนึ่งจากสองทิศทางที่เป็นไปได้ กล่าวอีกนัยหนึ่ง ทัวร์นาเมนต์คือการวางแนวของกราฟสมบูรณ์แบบไม่มีทิศทาง (อย่างไรก็ตาม ในฐานะกราฟแบบมีทิศทาง ทัวร์นาเมนต์ไม่สมบูรณ์: กราฟแบบมีทิศทางที่สมบูรณ์จะมีขอบสองเส้นในทั้งสองทิศทางระหว่างจุดยอดสองจุดใดๆ^{[ 1 ]} ) กล่าวอีกนัยหนึ่ง ทัวร์นาเมนต์คือความสัมพันธ์แบบอสมมาตรที่สมบูรณ์^{[ 2 ] [ 3 ]}

ชื่อ " ทัวร์นาเมนต์"มาจากการตีความกราฟว่าเป็นผลลัพธ์ของการแข่งขันแบบรอบคัดเลือกซึ่งเป็นเกมที่ผู้เล่นแต่ละคนจะจับคู่กับผู้เล่นคนอื่น ๆ ทุกคนเพียงครั้งเดียว ในการแข่งขันแบบทัวร์นาเมนต์ จุดยอดจะแทนผู้เล่น และเส้นเชื่อมระหว่างผู้เล่นจะชี้จากผู้ชนะไปยังผู้แพ้

คุณสมบัติสำคัญหลายประการของทัวร์นาเมนต์ได้รับการตรวจสอบโดยHG Landauในปี พ.ศ. 2496 เพื่อจำลองความสัมพันธ์ของการครอบงำในฝูงไก่^{[ 4 ]}ทัวร์นาเมนต์ยังได้รับการศึกษาอย่างกว้างขวางในทฤษฎีการลงคะแนนเสียงซึ่งสามารถแสดงข้อมูลบางส่วนเกี่ยวกับความชอบของผู้ลงคะแนนเสียงในหมู่ผู้สมัครหลายคน และเป็นศูนย์กลางของคำจำกัดความของวิธีการคอนดอร์เซต์

ถ้าผู้เล่นทุกคนเอาชนะผู้เล่นคนอื่นได้จำนวนเท่ากัน (จำนวนการเชื่อมต่อขาเข้า − จำนวนการเชื่อมต่อขาออก = 0) ทัวร์นาเมนต์นั้นเรียกว่า ทัวร์นาเมนต์ ปกติจำนวนทัวร์นาเมนต์ปกติที่ไม่มีป้ายกำกับซึ่งมีจุดยอด 2n+1 จุด มีดังนี้:

1, 1, 1, 3, 15, 1223, 1495297, 18400989629, 2406183070160597,... (ลำดับA096368ในOEIS )

การแข่งขันใดๆ บนจุดยอดจำนวนจำกัด จะมี เส้นทางแฮมิลโท เนียนอยู่ด้วย กล่าวคือ เส้นทางที่มีทิศทางบนจุดยอดทั้งหมด ( Rédei 1934) ${\displaystyle n}$${\displaystyle n}$

สิ่งนี้แสดงให้เห็นโดยการอุปมานบน: สมมติว่าข้อความนี้เป็นจริงสำหรับและพิจารณาทัวร์นาเมนต์ใดๆบนจุดยอด เลือกจุดยอดของและพิจารณาเส้นทางทิศทางในมีบางค่าที่ทำให้(ความเป็นไปได้หนึ่งคือให้เป็นค่าสูงสุดที่ทำให้ สำหรับทุกหรืออีกทางหนึ่ง ให้เป็นค่าต่ำสุดที่ทำให้) เป็นเส้นทางทิศทางตามที่ต้องการ ข้อโต้แย้งนี้ยังให้ขั้นตอนวิธีในการค้นหาเส้นทางแฮมิลโทเนียน มีขั้นตอนวิธีที่มีประสิทธิภาพมากกว่าซึ่งต้องตรวจสอบเฉพาะขอบเท่านั้น เส้นทางแฮมิลโทเนียนมีความสอดคล้องกันแบบหนึ่งต่อหนึ่งกับเซตส่วนโค้งป้อนกลับ ขั้นต่ำ ของทัวร์นาเมนต์^{[ 5 ]}ทฤษฎีบทของ Rédei เป็นกรณีพิเศษสำหรับกราฟสมบูรณ์ของทฤษฎีบท Gallai–Hasse–Roy–Vitaverซึ่งเชื่อมโยงความยาวของเส้นทางในการวางแนวของกราฟกับจำนวนสีของกราฟเหล่านี้^{[ 6 ]}${\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)}$

ผลลัพธ์พื้นฐานอีกประการหนึ่งเกี่ยวกับทัวร์นาเมนต์คือ ทัวร์นาเมนต์ ที่เชื่อมต่ออย่างแน่นหนา ทุกรายการ จะมีวัฏจักรแฮมิลโท เนียน ^{[ 7 ]}ยิ่งไปกว่านั้น ทัวร์นาเมนต์ที่เชื่อมต่ออย่างแน่นหนาทุกรายการจะ มี จุดยอดแบบแพนไซคลิก : สำหรับแต่ละจุดยอดและแต่ละค่าในช่วงตั้งแต่สามถึงจำนวนจุดยอดในทัวร์นาเมนต์ จะมีวัฏจักรที่มีความยาวซึ่งประกอบด้วย^{[ 8 ]}ทัวร์นาเมนต์จะเชื่อมต่ออย่างแน่นหนา -strongly ถ้าสำหรับทุกเซตของจุดยอดของ จะเชื่อมต่ออย่างแน่นหนา ถ้าทัวร์นาเมน ต์เชื่อมต่ออย่างแน่นหนา 4-strongly แล้วแต่ละคู่ของจุดยอดสามารถเชื่อมต่อกันด้วยเส้นทางแฮมิลโทเนียน^{[ 9 ]}สำหรับทุกเซต ของ ส่วนโค้งไม่เกิน ของ ทัวร์นาเมนต์ที่เชื่อมต่ออย่างแน่นหนา -strongly เรามี ที่มีวัฏจักรแฮมิลโทเนียน^{[ 10 ]}ผลลัพธ์นี้ได้รับการขยายโดยBang-Jensen, Gutin & Yeo (1997 ) ^{[ 11 ]}${\displaystyle v}$${\displaystyle k}$${\displaystyle k}$${\displaystyle v}$${\displaystyle T}$${\displaystyle k}$${\displaystyle U}$${\displaystyle k-1}$${\displaystyle T}$${\displaystyle T-U}$${\displaystyle B}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle T}$${\displaystyle T-B}$

ทัวร์นาเมนต์ที่และเรียกว่า ทัวร์ นาเมนต์แบบถ่ายทอด (transitive tournament) กล่าวอีกนัยหนึ่ง ในทัวร์นาเมนต์แบบถ่ายทอด จุดยอดอาจถูกเรียงลำดับอย่างสมบูรณ์ (อย่างเคร่งครัด) โดยความสัมพันธ์ของขอบ และความสัมพันธ์ของขอบนั้นเหมือนกับความสามารถในการเข้าถึง (reachability ) ${\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}$มีเส้นทางแฮมิลโทเนียนเพียงเส้นเดียวเท่านั้น

ทัวร์นาเมนต์แบบทรานซิทีฟมีบทบาทในทฤษฎีแรมซีย์ในลักษณะเดียวกับคลิกในกราฟแบบไม่มีทิศทาง โดยเฉพาะอย่างยิ่ง ทัวร์นาเมนต์ทุกรายการบนจุดยอดจะมีทัวร์นาเมนต์ย่อยแบบทราน ซิทีฟบนจุดยอด การพิสูจน์นั้นง่าย: เลือกจุดยอดใดจุดหนึ่งให้เป็นส่วนหนึ่งของทัวร์นาเมนต์ย่อยนี้ และสร้างทัวร์นาเมนต์ย่อยที่เหลือแบบเรียกซ้ำบนเซตของเพื่อนบ้านขาเข้าของหรือเซตของเพื่อนบ้านขาออกของแล้วแต่ว่าเซตใดมีขนาดใหญ่กว่า ตัวอย่างเช่น ทัวร์นาเมนต์ทุกรายการบนจุดยอดเจ็ดจุดจะมีทัวร์นาเมนต์ย่อยแบบทรานซิทีฟสามจุดยอดทัวร์นาเมนต์พาเลย์บนจุดยอดเจ็ดจุดแสดงให้เห็นว่านี่คือจำนวนสูงสุดที่สามารถรับประกันได้^{[ 12 ]}อย่างไรก็ตามรีดและพาร์คเกอร์ (1970)แสดงให้เห็นว่าขอบเขตนี้ไม่แน่นสำหรับค่าที่มากกว่าบางค่า  ของ^{[ 13 ]}${\displaystyle n}$${\displaystyle 1+\lfloor \log _{2}n\rfloor }$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle n}$

Erdős & Moser (1964)พิสูจน์ว่ามีทัวร์นาเมนต์บนจุดยอดที่ไม่มีทัวร์นาเมนต์ย่อยแบบทรานซิทีฟที่มีขนาดการพิสูจน์ของพวกเขาใช้การโต้แย้งเชิงนับ : จำนวนวิธีที่ทัวร์นาเมนต์ทรานซิทีฟที่มีองค์ประกอบ - สามารถเกิดขึ้นเป็นทัวร์นาเมนต์ย่อยของทัวร์นาเมนต์ที่ใหญ่กว่าบนจุดยอดที่มีป้ายกำกับคือ และเมื่อมีขนาดใหญ่กว่าจำนวนนี้เล็กเกินไปที่จะอนุญาตให้เกิดทัวร์นาเมนต์ทรานซิทีฟภายในทัวร์นาเมนต์ที่แตกต่างกันแต่ละรายการบนเซตของจุดยอดที่มีป้ายกำกับ เดียวกัน ^{[ 12 ]}${\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-paradoxical โดยทั่วไปแล้ว การแข่งขันจะเรียกว่า-paradoxical ถ้าสำหรับเซตย่อยที่ มีสมาชิก - ตัว ของ ทุกเซต จะมีจุดยอดในเซตนั้นที่สำหรับทุกค่าโดยใช้วิธีความน่าจะเป็น Paul Erdősแสดงให้เห็นว่าสำหรับค่าคงที่ใดๆ ของถ้าแล้วการแข่งขันเกือบทุกรายการบนจะเป็น-paradoxical ^{[ 14 ]}ในทางกลับกัน ข้อโต้แย้งง่ายๆ แสดงให้เห็นว่าการแข่งขันแบบ -paradoxical ใดๆ จะต้องมีผู้เล่นอย่างน้อยซึ่งได้รับการปรับปรุงเป็นโดยEstherและGeorge Szekeresในปี 1965 ^{[ 15 ]}มีการสร้างการแข่งขันแบบ -paradoxical ที่มีผู้เล่นอย่างชัดเจนโดยGrahamและ Spencer (1971) ซึ่งก็คือการแข่งขัน Paley ${\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))}$

การควบแน่นของทัวร์นาเมนต์ใดๆ ก็ตามถือเป็นทัวร์นาเมนต์แบบถ่ายทอดได้ ดังนั้น แม้แต่สำหรับทัวร์นาเมนต์ที่ไม่ถ่ายทอดได้ ส่วนประกอบที่เชื่อมต่อกันอย่างแน่นแฟ้นของทัวร์นาเมนต์ก็อาจเรียงลำดับได้อย่างสมบูรณ์^{[ 16 ]}

ลำดับคะแนนของทัวร์นาเมนต์คือลำดับที่ไม่ลดลงของดีกรีขาออกของจุดยอดในทัวร์นาเมนต์นั้น เซตคะแนนของทัวร์นาเมนต์คือเซตของจำนวนเต็มที่เป็นดีกรีขาออกของจุดยอดในทัวร์นาเมนต์นั้น

ทฤษฎีบทของแลนเดา (1953)ลำดับจำนวนเต็มที่ไม่ลดลงเป็นลำดับคะแนนก็ต่อเมื่อ: ^{[ 4 ]}${\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}.}$

ให้เป็นจำนวนลำดับคะแนนที่แตกต่างกันที่มีขนาด ลำดับ(ลำดับA000571 ใน OEIS )เริ่มต้นดังนี้: ${\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},}$

ซึ่ง ต่อมา Takács ได้แสดงให้เห็นโดยใช้สมมติฐานที่สมเหตุสมผลแต่ยังไม่ได้รับการพิสูจน์ว่า ${\displaystyle c_{1}=0.049.}$

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

โดยที่^{[ 17 ]}${\displaystyle c_{2}<4.858.}$

สิ่งเหล่านี้รวมกันแล้วเป็นหลักฐานที่แสดงให้เห็นว่า:

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

ในที่นี้หมายถึงขอบเขตที่แน่นในเชิงอะซิมโทติก ${\displaystyle \Theta }$

เหยาแสดงให้เห็นว่าเซตที่ไม่ว่างทุกเซตของจำนวนเต็มที่ไม่เป็นลบคือเซตคะแนนสำหรับทัวร์นาเมนต์บางรายการ^{[ 18 ]}

ในทฤษฎีการเลือกทางสังคมทัวร์นาเมนต์เกิดขึ้นตามธรรมชาติเป็นความสัมพันธ์ส่วนใหญ่ของโปรไฟล์ความชอบ^{[ 19 ]}ให้เป็นเซตจำกัดของทางเลือก และพิจารณารายการลำดับเชิงเส้นเหนือเราตีความแต่ละลำดับเป็นการจัดอันดับความชอบของผู้ลงคะแนนความสัมพันธ์ส่วนใหญ่ (ที่เข้มงวด) ของเหนือจะถูกกำหนดเพื่อให้ก็ต่อเมื่อผู้ลงคะแนนส่วนใหญ่ชอบนั่นคือถ้าจำนวนผู้ลงคะแนนเป็นเลขคี่ ความสัมพันธ์ส่วนใหญ่จะก่อให้เกิดความสัมพันธ์การครอบงำของทัวร์นาเมนต์บนเซตจุดยอด ${\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 การแข่งขันทุกรายการบนจุดยอดสามารถได้รับเป็นความสัมพันธ์เสียงข้างมากของผู้ลงคะแนน ไม่เกิน ^{[ 20 ]}ผลลัพธ์โดยStearnsและ Erdős & Moser ในภายหลังได้พิสูจน์ว่าจำเป็นต้องมีผู้ลงคะแนนเพื่อชักนำให้เกิดการแข่งขันทุกรายการบนจุดยอด^{[ 21 ]}${\displaystyle m}$${\displaystyle m(m-1)}$${\displaystyle \Theta (m/\log m)}$${\displaystyle m}$

Laslier (1997) ศึกษาว่าในแง่ใดที่เซตของจุดยอดสามารถเรียกว่าเซตของ "ผู้ชนะ" ในการแข่งขันได้^{[ 22 ]}สิ่งนี้ได้รับการพิสูจน์แล้วว่ามีประโยชน์ในวิทยาศาสตร์การเมืองเพื่อศึกษาในแบบจำลองที่เป็นทางการของเศรษฐศาสตร์การเมืองว่าผลลัพธ์ของกระบวนการประชาธิปไตยจะเป็นอย่างไร^{[ 23 ]}

• กราฟเชิงทิศทาง
• ข้อสันนิษฐานของซัมเนอร์
• วิธีแก้ปัญหาการแข่งขัน