Turnering (grafteori)

En turnering är en riktad graf som erhålls från en oriktad komplett graf genom att tilldela en riktning till varje kant. Således är en turnering en digraf där varje par av hörn är sammankopplade med en enda riktad båge.

Många viktiga egenskaper hos turneringar övervägs av Landau [ 1] för att undersöka mönstret av kycklingdominans i en flock. Aktuella tillämpningar av turneringar inkluderar forskning om röstning och kollektiva val annat. Namnet på turneringen kommer från en grafisk tolkning av resultatet av en round robin-turnering , där varje spelare möter varannan spelare exakt en gång, och där det inte kan bli oavgjort . I turneringsdigrafen motsvarar hörnen spelarna. Bågen mellan varje par av spelare är orienterad från vinnare till förlorare. Om spelaren slår spelaren sägs den dominera över . $a$ $b$ $a$ $b$

Vägar och cykler

Varje turnering med ett ändligt antal hörn innehåller en Hamiltonsk bana , det vill säga en riktad bana som innehåller alla hörn [2] . Detta kan enkelt visas genom matematisk induktion på : låt påståendet vara sant för , och låt det bli någon turnering med hörn. Låt oss välja en vertex vid och låt oss vara en riktad väg till . Låta vara det maximala antalet så att det för alla finns en båge från till . Sedan $n$ $n$ $n$ $n$ $T$ $n+1$ $v_{0}$ $T$ $v_{1},v_{2},\ldots ,v_{n}$ $T\setminus \{v_{0}\}$ $i\in \{0,\ldots ,n\}$ $j\leq i$ $v_{j}$ $v_{0}$

v_{1},\ldots ,v_{i},v_{0},v_{{i+1}},\ldots ,v_{n}

är den önskade orienterade banan. Detta bevis ger också en algoritm för att hitta en Hamiltonsk väg. En mer effektiv algoritm är känd som kräver uppräkning av alla bågar [3] . $\O(n\log n)$

Detta betyder att en strikt sammankopplad turnering har en Hamiltonsk cykel [4] . Mer strikt är varje starkt sammankopplad turnering vertex-pancyklisk — för alla hörn v och för alla k från tre till antalet hörn i turneringen finns det en cykel med längden k som innehåller v [5] . Dessutom, om turneringen är 4-kopplad, kan vilket par av hörn som helst kopplas ihop med en Hamiltonsk väg [6] .

Transitivitet

En turnering där och kallas transitiv . I en transitiv turnering kan hörnen ordnas helt i nåbarhetsordning . $((a\högerpil b)$ $(b\högerpil c))$ $\Höger pil$ $(a\högerpil c)$

Motsvarande villkor

Följande uttalanden för en turnering med n hörn är likvärdiga:

T är transitivt.
T är acyklisk .
T innehåller inte cykler med längd 3.
Sekvensen av antalet vinster (uppsättningen av halva utfall) T är {0,1,2,..., n − 1}.
T innehåller exakt en Hamiltonsk väg.

Ramsey teori

Transitiva turneringar spelar en viktig roll i Ramsey-teorin , liknande rollen som klicker spelar i oriktade grafer. I synnerhet innehåller varje turnering med n hörn en transitiv underturnering med hörn [7] . Beviset är enkelt: välj vilken vertex v som helst som en del av denna subturnering och konstruera subturneringen rekursivt på uppsättningen av antingen inkommande grannar till v eller på uppsättningen utgående grannar, beroende på vilken som är störst. Till exempel, varje turnering med sju hörn innehåller en transitiv turnering med tre hörn. Paleys sjutoppsturnering visar att detta är det maximala som kan garanteras [7] . Reid och Parker [8] visade dock att denna gräns inte är strikt för vissa stora värden på n . $1+\lgolv \log _{2}n\rgolv$

Erdős och Moser [7] bevisade att det finns n -vertexturneringar utan transitiva subturneringar av storlek . Deras bevis använder räkning : antalet sätt på vilka en transitiv turnering med k hörn kan innehållas i en större turnering med n märkta hörn är $2+2\lgolv \log _{2}n\rgolv$

{\binom {n}{k}}k!2^{{{\binom {n}{2}}-{\binom {k}{2}}}},

och för k större än detta nummer är det för litet för att en transitiv turnering ska vara i var och en av de olika turneringarna i samma uppsättning av n märkta hörn. $2+2\lgolv \log _{2}n\rgolv$ $2^{{{\binom {n}{2))))$

Paradoxturneringar

Spelaren som vinner alla spelen blir naturligtvis vinnaren av turneringen. Men som förekomsten av icke-transitiva turneringar visar, kanske det inte finns en sådan spelare. En turnering där varje spelare förlorar minst ett spel kallas en 1-paradoxal turnering. Mer generellt sägs en turnering T =( V , E ) vara k -paradoxal om det för någon k -elementdelmängd S i mängden V finns en vertex v 0 i sådan att för alla . Med hjälp av den probabilistiska metoden visade Erdős att för alla fasta k under villkoret | v | ≥ k 2 2 k ln(2 + o(1)) nästan alla turneringar på V är k -paradoxala [9] . Å andra sidan visar ett enkelt argument att varje k -paradoxal turnering måste ha minst 2 k +1 − 1 spelare, vilket har förbättrats till ( k + 2)2 k −1 − 1 av Esther och György Sekeresami (1965 ) ) [10] . Det finns en explicit metod för att konstruera k -paradoxala turneringar med k 2 4 k −1 (1 + o(1)) spelare utvecklad av Graham och Spencer, nämligen Paley-turneringen [11] . $V\setminus S$ $v_{0}\rightarrow v$ $v\in S$

Kondensation

Kondenseringen av alla turneringar är en transitiv turnering. Således, även om turneringen inte är transitiv, kan de starkt sammankopplade komponenterna i turneringen beställas helt [12] .

Sekvenser av resultat och uppsättningar av resultat

Sekvensen av turneringsresultat är en icke-minskande sekvens av halvgradiga utfall för turneringens hörn. Uppsättningen av turneringsresultat är uppsättningen av heltal som är halvgrader av resultatet av turneringens hörn.

Landaus teorem (1953) - En icke-minskande sekvens av heltal är en sekvens av resultat om och endast om: $(s_{1},s_{2},\cdots ,s_{n})$

$0\leq s_{1}\leq s_{2}\leq \cdots \leq s_{n}$
$s_{1}+s_{2}+\cdots +s_{i}\geq {i \choose 2},$ för $i=1,2,\cdots ,n-1$
$s_{1}+s_{2}+\cdots +s_{n}={n \välj 2}.$

Låt vara antalet distinkta sekvenser av resultat av storlek . Sekvensen börjar med: $s(n)$ $n$ $s(n)$

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

(sekvens A000571 i OEIS )

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

s(n)>c_{1}4^{n}n^{{-{5 \över 2}}},

där Takacs senare visade [13] med några rimliga men obevisade gissningar som $c_{1}=0,049.$

s(n)<c_{2}4^{n}n^{{-{5 \över 2}}},

var $c_{2}<4,858.$

Tillsammans tyder detta på det

s(n)\in \Theta (4^{n}n^{{-{5 \över 2}}}).

Här återspeglar den asymptotiskt strikta bunden . $\Theta$

Yao visade [14] att varje icke-tom uppsättning av icke-negativa heltal är resultatet för en turnering.

Se även

Anteckningar

↑ HG Landau. Om dominansrelationer och djursamhällens struktur. III. Villkoret för en poängstruktur // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , nr. 2 . - S. 143-148 . - doi : 10.1007/BF02476378 .
↑ Lazlo Redei. Ein kombinatorischer Satz // Acta Litteraria Szeged. - 1934. - T. 7 . - S. 39-43 .
↑ A. Bar-Noy, J. Naor. Sortering, Minimal Feedback Sets och Hamilton Paths in Tournaments // SIAM Journal on Discrete Mathematics . - 1990. - T. 3 , nummer. 1 . - S. 7-20 . - doi : 10.1137/0403002 .
↑ Chemins et circuits hamiltoniens des graphes complets // Comptes Rendus de l'Académie des Sciences de Paris. - 1959. - T. 249 . - S. 2151-2152 .
↑ JW Moon. Om underturneringar till en turnering // Canadian Mathematical Bulletin. - 1966. - T. 9 , nr. 3 . - S. 297-301 . - doi : 10.4153/CMB-1966-038-7 . Arkiverad från originalet den 3 mars 2016.
↑ Carsten Thomassen. Hamiltonian-Connected Tournaments // Journal of Combinatorial Theory, Series B. - 1980. - V. 28 , nr. 2 . - S. 142-163 . - doi : 10.1016/0095-8956(80)90061-1 .
↑ 1 2 3 Paul Erdős, Leo Moser. Om representationen av riktade grafer som sammanslutningar av beställningar // Magyar Tud. Akad. Matta. Kutato Int. Kozl. - 1964. - T. 9 . - S. 125-132 . Arkiverad från originalet den 13 december 2013.
↑ K.B. Reid, E.T. Parker. Motbevis för en gissning om Erdös och Moser // Journal of Combinatorial Theory. - 1970. - T. 9 , nr. 3 . - S. 225-238 . - doi : 10.1016/S0021-9800(70)80061-8 .
↑ Paul Erdős. Om ett problem i grafteori // The Mathematical Gazette. - 1963. - T. 47 . - S. 220-223 . — . Arkiverad från originalet den 22 december 2014.
↑ Esther Szekeres, George Szekeres. Om ett problem med Schütte och Erdős // The Mathematical Gazette. - 1965. - T. 49 . - S. 290-293 .
↑ Ronald Graham, Joel Spencer. En konstruktiv lösning på ett turneringsproblem // Canadian Mathematical Bulletin. Bulletin Canadien de Mathematiques. - 1971. - T. 14 . - S. 45-48 .
↑ Frank Harary, Leo Moser. Theory of round robin-turneringar // American Mathematical Monthly. - 1966. - T. 73 , nr. 3 . - S. 231-246 . - doi : 10.2307/2315334 . — .
↑ Lajos Takacs. En Bernoulli-utflykt och dess olika tillämpningar // Framsteg i tillämpad sannolikhet. - 1991. - T. 23 , nr. 3 . - S. 557-585 . - doi : 10.2307/1427622 . — .
↑ T.X. Yao. Om Reid gissningar om poänguppsättningar för turneringar // kinesisk vetenskap. Tjur. - 1989. - T. 34 . - S. 804-808 .