Matematikai Lapok, 1992 (Új sorozat 2. évfolyam, 1-4. szám)

1992 / 1. szám

In memóriám Gallai Tibor VARIÁCIÓK A RAMSEY TÉMÁRA GYÁRFÁS ANDRÁS1 1. KLIKKFEDÉS TÉTEL ÉS GALLAI SZÁMOK 1.1. Intervallumuniók Gallai számai Az első fejezetben szereplő vizsgálatok előzménye és bizonyos fokig ihletője Gal­lai egy kérdése volt 1968-ban. Tekintsük a sík két párhuzamos egyenesét, R\-et és Rj-t. Szeparált intervallumpárok rendszerén értsünk olyan véges halmazrend­szert (hipergráfot), melynek elemei (élei) R\ és Rj egy-egy zárt intervallumának egyesítéseként írhatók. Gallai kérdése az volt, igaz-e, hogy páronként metsző sze­parált intervallumpárok rendszerét két pont lefogja? Vezessük be [DGK] nyomán hipergráfok Ti családjának g(Ti,t) Gallai számait: g(Zi,t) = sup {t(H) , t/(Я) = ̧} неп ahol r(tf) jelöli H minimális lefogó ponthalmazának számosságát, t/(tf) pedig H páronként diszjunkt éleinek maximális számát.2 Szeparált intervallumpárok mintájára vezessük be a szeparált ifc-intervallumok­ok családját: ezek olyan véges halmazrendszerek, melynek elemei Rt, Rj,... ,Rt párhuzamos egyenesekről vett zárt intervallumok egyesítéseként írhatók. A Jb­­ 1 esetben Q 51 nem más, mint az intervallumrendszerek I családja, és Gallai egy közismert (publikálatlan) tétele szerint g(l,t) = t minden t természetes számra (ez alapvető tétel a gráfok elméletében). Gallai már említett kérdése az volt, hogy fennáll-e tji(52,t) = 2. Ez, valamint g(Sk,t) t po (tfc és t fix) a következő tétel folyománya. 1.1.1 tétel. ([GYLlj) g(Sk,t) ] g(Sk-\T) + t, ahol T=((t+ t)*'1 - l)t. A tétel bizonyítása a következő lemmán alapszik, mely­­ szerinti indukcióval könnyen bizonyítható.­ ­ Az ELTE matematikus szakán 1968-ban szerzett diplomát. Az MTA SZTAKI tudomá­nyos főmunkatársa. 2 A cikk végén, a függelékben ismertetjük a gyakrabban használt jelöléseket és definíciókat. 1

Next