Nagy Zoltán Lóránt és
Csíkvári Péter:
Sûrûségi Turán-problémáról
Elôadásunkban a
következô problémáról
fogunk beszélni. Adott egy H gráf,
ennek egy G[H] felfújtját
úgy értelmezzük, hogy H minden csúcsa
helyére
berakunk csúcsoknak egy kupacot és
két kupac között akkor húzunk be néhány
élt
(nem feltétlenül az összeset !) ha a megfelelô
H-beli csúcsok között
ment él.
Kérdés: a kupacok között milyen
élsûrûséget kell megkövetelnünk,
hogy G[H] biztosan tartalmazza H egy példányát,
mégpedig úgy, hogy h eleme
V(H) a neki megfelelô kupacban legyen benne.
A problámát teljesen megoldottuk ha H egy fa
és tetszôleges gráfokra is jó
becsléseink vannak.
Az elôadáson a probléma számos
különbözô megközelítését
adjuk; elemi, algebrai és
valószínûségszámítási
ötleteket is fel fogunk
használni a feladat megtámadásához.