Matematikai Lapok 1971/1-4. [antikvár]

ERDŐS ÉS HAJNAL EGY PROBLÉMÁJÁRÓL ERDŐS PÁL és JOEL SPENCER Legyen ff tetszőleges halmaz /(A) egy halmazfüggvény, mely ff minden véges A részhalmazához ?f—A egy x elemét rendeli. Ha Lfx c ff, ff egy tetszőleges részhalmaza, akkor n*í)= u aa), Acy1 ahol A végigfut ffx minden véges részhalmazán. Az 9{ halmazt akkor nevezzük függetlennek, ha ^ fi üres. Legyen (azaz ff véges halmaz), h(n) legyen az a legnagyobb szám, hogy minden / függvényre á^-nek van egy Lfx független részhalmaza, melyre H(n) legyen az a legkisebb szám, melyre van oly / függvény, hogy minden ff^c ff részhalmazra, melyre |ff^H(n), F(ff2)=ff. Erdős és Hajnal bebizonyították, [1] hogy ha«>«0(e), akkor (i) i°gl'-//(„)+f°g'°g". log 2 w log 2 log 2 (log H(n) — j~2) 'la n "" de e kérdés még nincs tisztázva, (l)-ből azonnal adódik, hogy ~>\ , , s log n + 3 log log n . (2) /;(«)<--!^——-t-o (log log«) [l]-ben /;(«)-re csak nagyon gyenge alsó becslés áll. Fennáll a következő Tétel. Legyen ;i>«0(e). Akkor log n — log log n ,, , , , , . log « + 3 log log n ~ logT~+ 0 (log log ^ ^ —log 2 + o (log log «). A felső becslés, mint már mondtuk, [l]-ben áll és ezt nem sikerült javítanunk, s így csak az alsó becsléssel foglalkozunk. Legyen Ac.íf, \A\ = r. Az A halmazt akkor nevezzük rossznak, ha van oly A1cA részhalmaza, melyre \A1\ = r-\ és A = A2 U/(A). Az r elemű rossz részhalmazok száma nyilván legfeljebb ^ " J. Továbbá nyil- 1 Matematikai Lapok 1