A kombinatorika szeminárium következő (III. 24. (péntek), 10:00, a szobámban) előadása:

Adott egy általanos helyzetű ponthalmaz, telítsük ezt köztük haladó szakaszokkal úgy, hogy elkerüljük szakaszaink metszését (szakaszaink közös végpontban összefuthatnak, de belső közös pontjuk nem lehet). Amihez jutunk az egy trianguláció. Már a konvex helyzetű ponthalmaz esete is érdekes.

Felvetődnek összeszámlálási kérdések, gráfelméleti kérdések (ha egy triangulációban egy szakasz elvételével - két háromszöget egybeolvasztva - egy konvex négyszöghöz jutunk, akkor ennek másik átlójával egy `szomszédos' triangulációt kapunk; mi az így kaptt gráf átmerője), algoritmuselméleti kérdések (ponthalmazok Delaunay-triangulációjának meghatározása).

Gyönyörű kérdések, gyönyörű válaszok, mégsem ez az előadás célja. Mostanában kezdték el a k-triangulációk vizsgalatát. Egy konvex helyzetű ponthalmazból indulunk ki és összekötő szakaszokkal telítjük úgy, hogy k+1 páronként metsző szakaszt elkerüljük. Amit így kapunk az a k-trianguláció (1-triangulácio=trianguláció). Bárhogy is haladjunk a telítéssel mindig ugyanannyi szakasznál állunk le. Ez triangulációkra szinte triviális. k-triangulációkra meglepően nehéz. Mégis természetes kérdés lehet, mert 3 független bizonyítás is született. Ezek a bizonyítások adják az előadás fő részét. A többi alapkérdés még messze megoldatlan.

Minden érdeklődőt szeretettel várunk,

Péter