Erdős-Szekeres-tétel

1. Sablon:Label 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.

1. 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).

1. 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.

1. 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)\ge I(x)+1$.
  * Ha $x>y$, akkor $D(y)\ge D(x)+1$.

4. Az $N=nm+1$ elem miatt, ha $I(x)\le n$ és $D(x)\le 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.

• Sablon:En: Sablon:T