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

1992 / 1. szám

1.1.2 lemma. ([GYll]) Legyen t ¡ 2 és € Sk. Ha v({Ax, A?.......At}) ‚­t minden Aj € Hj választásra, akkor valamely i £ {1,2,...,t)-re v(Hi) s tk. 1.1.3 kérdés. Milyen kisebb függvény írható tk helyett az 1.1.2 lemmában? А λ­­ 1 esetben a lemma és Gallai tétele ezt adja: 1.1.4 következmény. Ha H\, H3,..., Ht € 1 (t · 2) és i/({Ai,A3,...,At)) á­t minden Aj ( Hj választásra, akkor valamely i G {1,2,... ,t}-re t(Ht) á­t. Ez a következmény a Gallai tétel és a Helly tétel Lovász-féle általánosításának ([L01]) közös megfogalmazása (Ai = #2 — Ht esetén az előbbi, i — 2 esetén az utóbbi). .­­ 1.1.1 tétel bizonyítása. Legyen H = {Aj, A2,..., Am} szeparált ib-intervallu­­mok rendszere, v(H) = t. írjuk A,-t­ι,- = ν U Bi alakban, ahol I, C Bi, Bi pedig (ρ — l)-intervallum. Definiáljunk R\-en egy pontsorozatot. Legyen P0 = 1 00 és legyen Pj a lehető legjobbra a következő tulajdonság mellett: *'({£» , U C (Pj-i, ij)}) = (* + l)*-1 - 1 Legyen Hj = {pi : /,• C (Pj_i,Pj]}. Ekkor Pj definíciója miatt v{Hj) — (t + l)*-1 és 1.1.2 lemma miatt Pj+1 = 00. Ezért a P\,... Pj pontokkal le nem fogott t-beli k­­intervallumok az R?, R3,.. .,Rk egyeneseken olyan H' (k — l)-intervallumrendszert alkotnak, melyre v(H') · t((t + l)t_1 — l). Ebből a tétel következik. ■ А к = 2, t = 1 esetben az 1.1.1 tételből g(S7,1) · 2 adódik. Mivel j(52,1) · 2 triviális példából következik, kapjuk: 1.1.5 következmény. ([GYL1]) g(S2,1) = 2. Az 1.1.1 tétel bizonyítási módszere már ifc = 3, 1 = 1 esetén is durva, g(S3,1) · · 43-at ad. Ezzel szemben az igazság: 1.1.6 tétel. ([GYll]) g(S3,1) = 4. Mivel a bizonyítás elég komplikált, mellőzzük. Mindenesetre jó tudni, hogy általában g(Sk, 1) ф 1. 1.1.7 probléma. Kívánatos lenne g(Sk, 1) jó becslése, esetleg olyan, mely közvet­lenül g(Sk~1,t) függvényében korlátozza 0(5*,l)-et. Érdekes lenne még g(S2,t) helyes nagyságrendje (az 1.1.1 tételből g(Sz,t) , S 2 + t adódik). 1.1.8. Intervallumgráfok uniójának klikkfedése A g(Sk ,t) Gallai szám interpretálható a következőképpen is. Tekintsük azon G gráfokat, melyekre a(G) - t és melyek felírhatók . intervallumgráf, G­,...,Gk 2

Next