Matematikai Lapok 2015/2. [antikvár]

Részlet: UJ KORLATOK 3 RESZES SPERNER-CSALÁDOKRA* MÉSZÁROS ÁNDRÁS Ebben a dolgozatban új alsó és felső korlátokat Eudunk a 3 részes Sperner-családok méretére. Megmutatjuk, hogy 1,05 < ds < 1,0722. Továbbá megcáfoljuk Aydinian, Cza-barka, Erdős, Székely sejtését a maximális fc-részes Sperner-családokkal kapcsolatban, amikor minden rész mérete 2^-1. 1. Bevezetés Sperner [10] a következő számelméleti kérdést vetette fel 1928-ban. Legyen N = PiP2---Pn egy négyzetmentes egész (azaz Pi,P2,---,Pn különböző prímek). Legfeljebb hány különböző osztója választható ki N-nek úgy, hogy ezek az osztók egymásnak nem osztói. Mivel egy osztó a. pi,p2, ¦ ¦ ¦ ,Pn számok egy részhalmazának szorzata, az osztók helyett tekinthetjük a {pi,p2, ¦ ¦ ¦ ,Pn} halmaz részhalmazait. Ezekből kell kiválasztanunk a legtöbb különbözőt úgy, hogy azok ne legyenek egymás részhalmazai. Ha kiválasztjuk az összes fc-elemü részhalmazt, azok között nyilvánvalóan nem lesz tartalmazás. Tehát részhalmaz kiválasztható a feltételnek megfelelően minden fc-ra. Ezen binomiális együtthatók közül a legnagyobb az, ahol fc = | . Tehát az összes | -es halmaz jó választásnak tűnik. Sperner bebizonyította, hogy ennél több halmaz nem is választható ki tartalmazások nélkül. 1.1. tétel ([10]). Egy n-elemű X halmaz részhalmazaiból legfeljebb (1) .2. különböző választható kí úgy, hogy azok egyike se tartalmazzon egy másikat. Katona és Kleitman egymástól függetlenül észrevették, hogy ugyanez a korlát akkor is érvényes, ha az X alaphalmazt kettéosztjuk, és csak olyan tartalmazásokat tiltunk meg, amelyek az egyik részben egybeesnek. 'A Moscow Journal of Combinatorics and Number Theoryban megjelent cikk magyar változata.