Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

6. Zárótételek

6. Zárótételek

Először Solymosi [25] és Nielsen [19] vette észre, később Bárány Imre és Valtr fogalmazta meg általánosabb formában azt a tényt, hogy egy rögzített m érték mellett minden elég nagy n -elemű ponthalmazban az m -elemű részhalmazok pozitív százaléka konvex helyzetben van, ráadásul ezek nagy része egy jól meghatározott, „kanonikus” módon kapható meg.

6.1. Tétel [1]. Bármely m ? 4 egészhez van egy c m //>// 0 szám, amely eleget tesz a következő feltételnek: a sík minden általános helyzetű, n -elemű ponthalmazának van m olyan páronként diszjunkt ? c m n ? -elemű részhalmaza, hogy mindegyikből tetszőlegesen kivéve egy-egy elemet, a kapott m pont mindig konvex helyzetben van.

Felmerül a kérdés, hogy minimum hány konvex m -szöget határoz meg n általános helyzetű pont a síkon. A fentiek értelmében a válasz nagyságrendje világos. A pontos választ már az m = 4 esetben sem tudjuk, pedig ez ekvivalens azzal a nevezetes problémával, hogy miként kell lerajzolni a síkban egy teljes n -pontú gráfot egyenesvonalú élekkel úgy, hogy a keresztező élpárok száma a lehető legkisebb legyen [10]. A ma ismert legjobb konstrukcióban [6] a keresztező élpárok (és a konvex helyzetben lévő pontnégyesek) száma aszimptotikusan

6467 16848 n 4 ~ 0 . 3838 n 4 .

A 6.1. Tételben szereplő c m konstansra a legjobb alsó becslés [21]-ben található. Ugyanebből a dolgozatból az is kiderül, hogy az állítás viszonylag zökkenőmentesen általánosítható konvex testekre.

6.2. Tétel [21]. Bármely m ? 4 egészhez van egy c m * //>// 0 szám, amely eleget tesz a következő feltételnek: minden n páronként diszjunkt konvex testből álló halmazrendszernek, melynek bármely három eleme konvex helyzetben van, létezik m olyan páronként diszjunkt ? c m * n ? -elemű részrendszere, hogy mindegyikből tetszőlegesen kivéve egy-egy elemet, a kapott m test mindig konvex helyzetben van. Ráadásul

c m * = 2 - O ( k 2 ) .

Nyilvánvaló, hogy az itt tárgyalt kérdések mindegyike felvethető magasabb dimenziós terekben is. A d -dimenziós euklideszi tér pontjainak egy P halmaza általános helyzetben van, ha semelyik d + 1 eleme nincs ugyanazon a hipersíkon. P konvex helyzetben van, ha megegyezik egy konvex politóp csúcshalmazával. Bármely m //>// d + 1 egész számra jelöljük f d ( m ) -mel azt a legkisebb f számot, amely eleget tesz a következő feltételnek: a d -dimenziós tér minden legalább f általános helyzetű pontból álló halmazának van m olyan eleme, ami konvex helyzetben van. Ezt a jelölést használva az Erdős–Szekeres-tételben szereplő f ( m ) függvény azonos f 2 ( m ) -mel.

Világos, hogy minden általános helyzetű d -dimenziós pontrendszer levetíthető egy alkalmasan választott 2-dimenziós síkra úgy, hogy a vetület általános helyzetű legyen. Következésképp minden d -re

f d ( m ) ? f ( m ) ? 2 m - 5 m - 3 + 2 .

Meglepő módon még az sem ismeretes, hogy f 3 ( m ) legalább exponenciálisan gyorsan nő. A legjobb becslés Károlyitól és Valtr-tól származik [18], akiknek csak annyit sikerült igazolniuk, hogy egy alkalmasan választott C //>// 1 konstanssal

f 3 ( m ) ? C m .

Köszönetnyilvánítás. Ez az áttekintés azon előadásom szövegét követi, melyet 1998. augusztusában a montreali McGill Egyetemen tartottam Erdős Pál Vendég-előadóként. Ugyanezt az anyagot – kisebb változtatásokkal – 1999. januárjában Sydney-ben is előadtam, a Macquarie Egyetemen, Klein Eszter és Szekeres György jelenlétében. Hálás köszönettel tartozom vendéglátásukért és a témával kapcsolatos érdekes megjegyzéseikért.