Turnering (grafteori) - Tournament (graph theory)

Turnering
En turnering på 4 hörn
Hörn	${\ displaystyle n}$
Kanter	${\ displaystyle {\ binom {n} {2}}}$
Tabell över grafer och parametrar

En turnering är en riktad graf (digraph) som erhålls genom att tilldela en riktning för varje kant i ett oriktat komplett diagram . Det vill säga, det är en orientering av ett komplett diagram, eller likvärdigt ett riktat diagram där varje par distinkta hörn är förbundna med en riktad kant (ofta kallad en båge ) med någon av de två möjliga orienteringarna.

Många av de viktiga egenskaperna hos turneringar undersöktes först av Landau (1953) för att modellera dominansförhållanden hos kycklingar. Nuvarande tillämpningar av turneringar inkluderar bland annat studier av röstteori och sociala valteori .

Namnet turnering härrör från en sådan kurva tolkning som resultatet av en round-robin turnering där varje spelare möter varannan spelare exakt en gång, och där ingen drar förekomma. I turneringen digraph, hörnen motsvarar spelarna. Kanten mellan varje par spelare orienteras från vinnaren till förloraren. Om spelaren slår spelaren , så sägs det att dominerar . Om varje spelare slår samma antal andra spelare ( indegree = outdegree ) kallas turneringen regelbunden . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a}$ ${\ displaystyle b}$

Vägar och cykler

Ett annat grundresultat på turneringar är att varje starkt ansluten turnering har en Hamiltonian -cykel (Camion 1959). Mer starkt är varje starkt ansluten turnering vertex pancyklisk : för varje toppunkt , och var och en i intervallet från tre till antalet hörn i turneringen, finns det en längdcykel som innehåller . En turnering är -strongly ansluten om för varje uppsättning av hörn av , är starkt kopplad. Om turneringen är 4 -starkt ansluten kan varje hörnpar kopplas till en hamiltonspår (Thomassen 1980). För varje uppsättning av högst bågar av en starkt ansluten turnering har vi som har en hamiltons cykel. Detta resultat förlängdes i ${\ 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}$

Transitivitet

En turnering där och kallas transitiv . Med andra ord, i en transitiv turnering kan hörnen (strikt) vara helt ordnade av kantrelationen, och kantrelationen är densamma som nåbarhet . ${\ displaystyle ((a \ högerpil b)}$${\ displaystyle (b \ högerpil c))}$ ${\ displaystyle \ Rightarrow}$ ${\ displaystyle (a \ högerpil c)}$

Motsvarande villkor

Följande uttalanden motsvarar en turnering på hörn: ${\ displaystyle T}$${\ displaystyle n}$

1. ${\ displaystyle T}$ är transitiv.
2. ${\ displaystyle T}$ är en strikt totalbeställning.
3. ${\ displaystyle T}$är acyklisk .
4. ${\ displaystyle T}$ innehåller inte en cykel med längd 3.
5. Poängsekvensen (uppsättning utegrader) av är .${\ displaystyle T}$${\ displaystyle \ {0,1,2, \ ldots, n-1 \}}$
6. ${\ displaystyle T}$ har exakt en hamiltons väg.

Ramsey -teorin

Transitiva turneringar spelar en roll i Ramsey -teorin analogt med klickningar i oreglerade grafer. I synnerhet innehåller varje turnering på hörn en transitiv subturnament på hörn. Beviset är enkelt: välj vilken hörnpunkt som helst som ska ingå i denna underturnering, och bilda resten av delturneringen rekursivt på antingen uppsättningen inkommande grannar till eller uppsättningen av utgående grannar , beroende på vilket som är störst. Till exempel innehåller varje turnering på sju hörn en transitiv subturnament med tre vertex; den Paley turnering på sju brytpunkter visar att detta är den mest som kan garanteras ( Erdős & Moser 1964 ). Men Reid & Parker (1970) visade att denna gräns inte är tätt för några större värden på  . ${\ displaystyle n}$${\ displaystyle 1+ \ lfloor \ log _ {2} n \ rfloor}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle n}$

Erdős & Moser (1964) visade att det finns turneringar på hörn utan en transitiv subturnament av storlek Deras bevis använder ett räknargument : antalet sätt som en -elementtransitiv turnering kan ske som en subturnament för en större turnering på märkta hörn är ${\ 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}}},}$

och när är större än , är detta antal för litet för att möjliggöra en transitiv turnering inom var och en av de olika turneringarna på samma uppsättning märkta hörn. ${\ displaystyle k}$${\ displaystyle 2+2 \ lfloor \ log _ {2} n \ rfloor}$${\ displaystyle 2^{\ binom {n} {2}}}$${\ displaystyle n}$

Paradoxala turneringar

En spelare som vinner alla matcher skulle naturligtvis vara turneringens vinnare. Men som förekomsten av icke-transitiva turneringar visar, kanske det inte finns någon sådan spelare. En turnering för vilken varje spelare förlorar minst ett spel kallas en 1-paradoxal turnering. Mer allmänt en turnering kallas -paradoxical om för varje -element delmängd av det finns ett hörn i ett sådant sätt att för alla . Med hjälp av sannolikhetsmetoden , Paul Erdős visade att för varje fast värde , om , då nästan varje turnering på är -paradoxical. Å andra sidan visar ett enkelt argument att varje paradoxal turnering måste ha minst spelare, vilket förbättrades till av Esther och George Szekeres (1965). Det finns en uttrycklig konstruktion av -paradoxiska turneringar med spelare av Graham och Spencer (1971) nämligen Paley -turneringen . ${\ 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 \ i 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))}$

Kondensation

Den kondense av en turnering är i sig en transitiv turnering. Således, även för turneringar som inte är transitiva, kan de starkt anslutna komponenterna i turneringen vara helt beställda.

Poängsekvenser och poängsatser

Poängsekvensen för en turnering är den icke -minskande sekvensen av utegrader i en turnerings hörn. Poänguppsättningen för en turnering är uppsättningen heltal som är utegraderna för hörn i den turneringen.

Landaus teorem (1953) En sekvens av heltal som inte minskar är en poängsekvens om och endast om: ${\ 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 \ välj 2}, {\ text {för}} i = 1,2, \ ldots, n-1}$
3. ${\ displaystyle s_ {1}+s_ {2}+\ cdots+s_ {n} = {n \ välj 2}.}$

Låt vara antalet olika poängsekvenser av storlek . Sekvensen (sekvens A000571 i OEIS ) startar som: ${\ displaystyle s (n)}$${\ displaystyle n}$${\ displaystyle s (n)}$

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

Winston och Kleitman bevisade att för tillräckligt stora n :

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

där Takács senare visade, med några rimliga men obevisade antaganden, att ${\ displaystyle c_ {1} = 0,049.}$

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

var ${\ displaystyle c_ {2} <4.858.}$

Tillsammans ger dessa bevis på att:

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

Här betyder en asymptotiskt stram gräns . ${\ displaystyle \ Theta}$

Yao visade att varje uppsättning icke -negativa heltal är poängsättningen för någon turnering.

Majoritetsförhållanden

I sociala valteori uppstår turneringar naturligtvis som majoritetsrelationer mellan preferensprofiler. Låt oss vara en begränsad uppsättning alternativ, och överväga en lista över linjära order över . Vi tolkar varje order som föredrar ranking av en väljare . Den (strikt) majoritet relation med över definieras sedan så att om och endast om en majoritet av väljarna föredrar att , det är . Om antalet väljare är udda, så utgör majoritetsrelationen dominansrelationen för en turnering på toppunktsuppsättning . ${\ 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 \ i [n]: a \ succ _ {i} b \} |> | \ {i \ i [n]: b \ succ _ {i} a \} |}$${\ displaystyle n}$${\ displaystyle A}$

Genom ett lemma av McGarvey kan varje turnering på hörn fås som majoritetsförhållande för de flesta väljare. Resultat från Stearns och Erdős & Moser fastställde senare att väljare behövs för att framkalla varje turnering på hörn. ${\ displaystyle m}$${\ displaystyle m (m-1)}$${\ displaystyle \ Theta (m/\ log m)}$${\ displaystyle m}$

Laslier (1997) studerar i vilken mening en uppsättning hörn kan kallas uppsättningen "vinnare" i en turnering. Detta visade sig vara användbart inom statsvetenskap för att i formella modeller för politisk ekonomi studera vad som kan bli resultatet av en demokratisk process.

Se även

• Orienterad graf
• Paley -turnering
• Sumners gissning
• Turneringslösning

Anteckningar

Referenser

• Bang-Jensen, J .; Gutin, G .; Yeo, A. (1997), "Hamiltonian Cycles Undvik förskrivna bågar i turneringar", Combinatorics, Probability and Computing , 6 : 255–261.
• Bar-Noy, A .; Naor, J. (1990), "Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments", SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi : 10.1137/0403002.
• Camion, Paul (1959), "Chemins et circuits hamiltoniens des graphes complets" , Comptes Rendus de l'Académie des Sciences de Paris (på franska), 249 : 2151–2152.
• Erdős, P. (1963), "On a problem in graph theory" (PDF) , The Mathematical Gazette , 47 : 220–223, JSTOR  3613396 , MR  0159319.
• Erdős, P .; Moser, L. (1964), "Om representationen av riktade grafer som fackföreningar i beställningar" (PDF) , Magyar Tud. Akad. Matta. Kutató Int. Közl. , 9 : 125–132, MR  0168494.
• Fraisse, P .; Thomassen, C. (1987), "En konstruktiv lösning på ett turneringsproblem", Graphs and Combinatorics , 3 : 239–250.
• Graham, RL ; Spencer, JH (1971), "En konstruktiv lösning på ett turneringsproblem", Canadian Mathematical Bulletin , 14 : 45–48, doi : 10.4153/cmb-1971-007-1 , MR  0292715.
• Harary, Frank ; Moser, Leo (1966), "The theory of round robin tournaments", American Mathematical Monthly , 73 (3): 231–246, doi : 10.2307/2315334 , JSTOR  2315334.
• Landau, HG (1953), "Om dominansrelationer och djursamhällenas struktur. III. Villkoret för en poängstruktur", Bulletin of Mathematical Biophysics , 15 (2): 143–148, doi : 10.1007/BF02476378.
• Laslier, J.-F. (1997), Turneringslösningar och majoritetsröstning , Springer.
• Moon, JW (1966), "On subtournaments of a turnering" , Canadian Mathematical Bulletin , 9 (3): 297–301, doi : 10.4153/CMB-1966-038-7.
• Rédei, László (1934), "Ein kombinatorischer Satz", Acta Litteraria Szeged , 7 : 39–43.
• Reid, KB; Parker, ET (1970), "Disproof of a conjecture of Erdös and Moser", Journal of Combinatorial Theory , 9 (3): 225–238, doi : 10.1016/S0021-9800 (70) 80061-8.
• Szekeres, E .; Szekeres, G. (1965), "On a problem of Schütte and Erdős", The Mathematical Gazette , 49 : 290–293, doi : 10.2307/3612854 , MR  0186566.
• Takács, Lajos (1991), "A Bernoulli Excursion and Its Various Applications", Advances in Applied Probability , Applied Probability Trust, 23 (3): 557–585, doi : 10.2307/1427622 , JSTOR  1427622.
• Thomassen, Carsten (1980), "Hamiltonian-Connected Tournaments", Journal of Combinatorial Theory , Series B, 28 (2): 142–163, doi : 10.1016/0095-8956 (80) 90061-1.
• Yao, TX (1989), "On Reid gissningar om poänguppsättningar för turneringar", kinesiska Sci. Tjur. , 34 : 804–808.

Denna artikel innehåller material från turneringar på PlanetMath , som är licensierade enligt Creative Commons Erkännande/Dela-Lika-licens .