Erdős-Szekeres-tétel

Magyar

Kiejtés

IPA: [ ˈɛrdøːʃsɛkɛrɛʃteːtɛl]

Főnév

(matematika, kombinatorika) Bármely nk + 1 darab különböző számból álló sorozatban van vagy egy n-nél hosszabb csökkenő részsorozat, vagy egy k-nál hosszabb növekvő részsorozat.

Erdős–Szekeres-tétel

Az **Erdős–Szekeres-tétel** a kombinatorika területéhez tartozik, és a rendezett részhalmazok létezéséről szól. A tétel a számok rendezésére és az úgynevezett Ramsey-elméletre épül.

Tétel:

Legyen $n$ és $m$ pozitív egész szám. Tetszőleges $nm+1$ darab különböző valós szám között mindig található:

egy legfeljebb $n+1$ elemű szigorúan növekvő sorozat, vagy
egy legfeljebb $m+1$ elemű szigorúan csökkenő sorozat.

Ekvivalens állítás:

Ha $N(n,m)$ a legkisebb szám, amely garantálja, hogy bármely $N(n,m)$ -elemű valós számhalmazban található legalább egy $n+1$ hosszú szigorúan növekvő részsorozat vagy $m+1$ hosszú szigorúan csökkenő részsorozat, akkor: $N(n,m)=nm+1$

---

Bizonyítás

1. Kisebb példák megértése

Vizsgáljuk meg $N(2,2)=5$ -öt:

Tetszőleges 5 különböző számot veszünk. Például: $\{1,3,2,5,4\}$ .
Mindig lesz legalább egy 3 elemű növekvő ( $n+1=3$ ) vagy csökkenő ( $m+1=3$ ) részsorozat.
Példa növekvő részsorozatra: $\{1,3,5\}$ .
Példa csökkenő részsorozatra: $\{3,2,1\}$ .

---

2. Ramsey-elmélet alkalmazása

Az Erdős–Szekeres-tétel valójában egy speciális eset a Ramsey-elméletből: a cél egy $n+1$ hosszú növekvő sorozat vagy $m+1$ hosszú csökkenő sorozat megtalálása.

Csúcsok és élek definiálása:

Vegyünk egy $N=nm+1$ -elemű sorozatot. Minden elemhez tartozik egy "csúcs".

- Élek definiálása:**

 * Rajzolunk egy élt két csúcs között, ha a két csúcsot összekötő él növekvő vagy csökkenő kapcsolatot jelez (a két szám rendezésétől függően).

Gráf színezése:

A gráf két színű:

 * Az egyik szín az összes növekvő kapcsolatot (él) jelzi.
 * A másik szín az összes csökkenő kapcsolatot jelzi.

Ramsey-elméleti következtetés:

A Ramsey-elmélet alapján, ha elég sok csúcs van (jelen esetben $N=nm+1$ ), akkor mindig található olyan részgráf, amely teljesen egy színű (vagy csak növekvő, vagy csak csökkenő élekből áll).

---

3. Formális bizonyítás

1. Tegyük fel, hogy van $N=nm+1$ elemünk, és mindegyiket egy sorozatba rendezzük. 2. Minden elemhez rendeljük hozzá a legnagyobb növekvő sorozat hosszát ( $I(x)$ ) és a legnagyobb csökkenő sorozat hosszát ( $D(x)$ ), amely véget ér nála. 3. Az $I(x)$ -re és $D(x)$ -re a következő szabály igaz:

  * Ha  $x<y$ , akkor  $I(y)\geq I(x)+1$ .
  * Ha  $x>y$ , akkor  $D(y)\geq D(x)+1$ .

4. Az $N=nm+1$ elem miatt, ha $I(x)\leq n$ és $D(x)\leq m$ minden $x$ -re, akkor: $I(x)+D(x)>nm$ Ez ellentmondás.

Ezért szükségszerűen létezik legalább egy $n+1$ hosszú növekvő vagy $m+1$ hosszú csökkenő sorozat.

---

Összegzés

Az Erdős–Szekeres-tétel bizonyítása kombinatorikus érveléssel és a Ramsey-elmélet speciális alkalmazásával igazolja, hogy bármely $nm+1$ elemű sorozatban mindig található egy szigorúan növekvő ( $n+1$ hosszú) vagy szigorúan csökkenő ( $m+1$ hosszú) részsorozat.

angol: Erdős-Szekeres theorem (en)

További információk

Erdős-Szekeres-tétel - Értelmező szótár (MEK)
Erdős-Szekeres-tétel - Etimológiai szótár (UMIL)
Erdős-Szekeres-tétel - Szótár.net (hu-hu)
Erdős-Szekeres-tétel - DeepL (hu-de)
Erdős-Szekeres-tétel - Яндекс (hu-ru)
Erdős-Szekeres-tétel - Google (hu-en)
Erdős-Szekeres-tétel - Helyesírási szótár (MTA)
Erdős-Szekeres-tétel - Wikidata
Erdős-Szekeres-tétel - Wikipédia (magyar)