A következő Katona O. H. Gyulától származó problémát vizsgáltuk: Legyenek k és N fix pozitív egészek. Adott két diszjunkt n elemű halmaz, A és B. Egy S halmazcsaládot az A∪B alaphalmazon félmetszőnek nevezünk, ha bármely S∈S pontosan k helyen metszi az A és a B halmazt is, és bármely két különböző S,T∈S esetén S és T pontosan az egyik oldalon metszenek, azaz S∩T nem üres és vagy A vagy B-nek részhalmaza. f(k,N)-nel jelöljük a legnagyobb félmetsző halmazcsalád méretét. Erre akarunk mindél jobb alsó és felső becsléseket adni.
Vegyük észre, hogy a feladat azzal ekvivalens, hogy mekkora két KG(N,k) Kneser-gráf XOR szorzatának a klikkszáma. Megvizsgáltuk más gráfszorzatokra is ezt a kérdést, de nem adott érdekes eredményt, így inkább az eredeti problémára fókuszálunk az előadás során.
Pontosan kiszámoljuk az f(2,N) értékét nagy N értékek esetén, illetve bebizonyítjuk, hogy ha k fix akkor f(k,N)Downloads
