Erdős – Szekeresova věta - Erdős–Szekeres theorem

Cesta čtyř nahoru se svažujících hran v sadě 17 bodů. Podle Erdős – Szekeresovy věty má každá sada 17 bodů cestu této délky, která se svažuje nahoru nebo dolů. 16bodová podmnožina s odstraněným středem nemá žádnou takovou cestu.

v matematika, Erdős – Szekeresova věta je konečný výsledek, díky kterému je přesně jeden z důsledků Ramseyova věta. Zatímco Ramseyova věta umožňuje snadno dokázat, že každá nekonečná posloupnost odlišných reálných čísel obsahuje monotónně rostoucí nekonečno subsekvence nebo monotónně klesající nekonečná subsekvence, výsledek prokázal Paul Erdős a George Szekeres jde dále. Za dané r, s ukázali, že jakákoli posloupnost odlišných reálných čísel s délkou alespoň (r − 1)(s - 1) + 1 obsahuje monotónně rostoucí posloupnost délkyr nebo monotónně klesající subsekvence délkys. Důkaz se objevil ve stejném článku z roku 1935, který zmiňuje Šťastný konec problému.^[1]

Příklad

Pro r = 3 a s = 2, vzorec nám říká, že jakákoli permutace tří čísel má rostoucí subsekvenci délky tři nebo klesající subsekvenci délky dvě. Mezi šesti permutacemi čísel 1,2,3:

• 1,2,3 má rostoucí posloupnost skládající se ze všech tří čísel
• 1,3,2 má klesající subsekvenci 3,2
• 2,1,3 má klesající subsekvenci 2,1
• 2,3,1 má dvě klesající subsekvence, 2,1 a 3,1
• 3,1,2 má dvě klesající subsekvence, 3,1 a 3,2
• 3,2,1 má tři klesající délka-2 subsekvence, 3,2, 3,1 a 2,1.

Alternativní interpretace

Geometrická interpretace

Pozice čísel v sekvenci lze interpretovat jako X- souřadnice bodů v Euklidovské letadlo a samotná čísla jako y-souřadnice; naopak pro jakýkoli bod v rovině je y- souřadnice bodů, seřazené podle jejich X-coordinates, tvoří posloupnost čísel (pokud dva z bodů nemají stejné X-souřadnice). S tímto překladem mezi sekvencemi a množinami bodů lze Erdős – Szekeresovu větu interpretovat tak, že uvádí, že v jakékoli sadě alespoň rs − r − s + 2 body můžeme najít a polygonální cesta buď r - 1 kladný sklon hran nebo s - 1 hrana negativního sklonu. Zejména (přičemž r = s), alespoň v jakékoli sadě n body můžeme najít polygonální cestu o minimu ⌊√n-1⌋ hrany se stejnými značkami. Například brát r = s = 5, jakákoli sada alespoň 17 bodů má čtyřbranovou cestu, ve které mají všechny svahy stejné znaménko.

Příklad rs − r − s + 1 bodů bez takové cesty, které ukazují, že tato vazba je pevná, lze vytvořit použitím malé rotace na (r - 1) od (s - 1) mřížka.

Interpretace permutačního vzoru

Erdős – Szekeresova věta může být interpretována také v jazyce permutační vzory jako konstatování, že alespoň každá permutace délky rs + 1 musí obsahovat buď vzor 1, 2, 3, ..., r + 1 nebo vzor s + 1, s, ..., 2, 1.

Důkazy

Erdős – Szekeresova věta může být prokázána několika různými způsoby; Steele (1995) zkoumá šest různých důkazů Erdős – Szekeresovy věty, včetně následujících dvou.^[2]Mezi další důkazy, které zkoumal Steele, patří původní důkazy Erdőse a Szekerese, jakož i důkazy Blackwell (1971),^[3] Hammersley (1972),^[4] a Lovász (1979).^[5]

Princip holubí díry

Vzhledem k posloupnosti délky (r − 1)(s - 1) + 1, označte každé číslo štítkem n_i v pořadí s dvojicí (A_i,b_i), kde A_i je délka nejdelší monotónně rostoucí subsekvence končící na n_i a b_i je délka nejdelší monotónně klesající subsekvence končící na n_i. Každé dvě čísla v pořadí jsou označena jinou dvojicí: pokud i < j a n_i ≤ n_j pak A_i < A_j, a na druhé straně, pokud n_i ≥ n_j pak b_i < b_j. Ale existují pouze (r − 1)(s - 1) možné štítky, pokud A_i je nanejvýš r - 1 a b_i je nanejvýš s - 1, takže u princip pigeonhole musí existovat hodnota i pro který A_i nebo b_i je mimo tento rozsah. Li A_i je tedy mimo rozsah n_i je součástí alespoň rostoucí délky sekvence r, a pokud b_i je tedy mimo rozsah n_i je součástí alespoň klesající sekvence délky s.

Steele (1995) připíše tento důkaz na jednostránkový papír Seidenberg (1959) a nazývá to „nejsklizňovanější a nejsystémovější“ z důkazů, které zkoumá.^[2][6]

Dilworthova věta

Další z použití důkazů Dilworthova věta na řetězových rozkladech v dílčích objednávkách nebo na jejich jednodušším duálním (Mirskyho věta ).

Chcete-li dokázat větu, definujte částečné uspořádání na členech sekvence, ve které X je menší nebo rovno y v částečném pořadí, pokud X ≤ y jako čísla a X není později než y v pořadí. Řetěz v tomto dílčím pořadí je monotónně rostoucí subsekvence a antichain je monotónně klesající subsekvence. Podle Mirského věty existuje buď řetěz délky rnebo lze sekvenci rozdělit maximálně na r - 1 antichains; ale v takovém případě musí největší z antichainů tvořit klesající subsekvenci s délkou alespoň

${ displaystyle left lceil { frac {rs-r-s + 2} {r-1}} right rceil = s.}$

Alternativně, podle Dilworthovy věty samotné, existuje buď antichain délky snebo lze sekvenci rozdělit maximálně na s - 1 řetězy, z nichž nejdelší musí mít alespoň délkur.

Aplikace korespondence Robinson – Schensted

Výsledek lze také získat jako důsledek Korespondence Robinson – Schensted.

Připomeňme, že Robinson – Schenstedova korespondence se přidružuje ke každé sekvenci a Mladé tablo P jejichž položky jsou hodnotami posloupnosti. Tablo P má následující vlastnosti:

• Délka nejdelší rostoucí posloupnosti se rovná délce první řady P.
• Délka nejdelší klesající subsekvence se rovná délce prvního sloupce P.

Nyní není možné umístit (r − 1)(s - 1) + 1 vstupů do čtvercového pole o velikosti (r − 1)(s - 1), takže buď první řada má délku alespoň r nebo je poslední řádek alespoň dlouhý s.

Viz také

• Nejdelší problém s rostoucí posloupností

Reference

externí odkazy

• Weisstein, Eric W. „Erdős-Szekeresova věta“. MathWorld.