Description
Kivonat: 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 $\mathcal{S}$ halmazcsaládot az $A \cup B$ alaphalmazon félmetszőnek nevezünk, ha bármely $S \in \mathcal{S}$ pontosan $k$ helyen metszi az $A$ és a $B$ halmazt is, és bármely két különböző $S, T \in \mathcal{S}$ esetén $S$ és $T$ pontosan az egyik oldalon metszenek, azaz $S \cap 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)$ mindig legfeljebb egy (csak $k$-tól függő) $c$ konstanssal térhet el a triviális alsó becsléstől, $\frac{N}{k}$-tól. Emellett algebrai módszerekkel éles alsó becsléseket adunk a $(k,N)$ párok egy nagy családjára, aminek a segítségével $f(k,k^2)$ értékét is meghatározzuk aszimptotikusan.
The zoom link:
https://zoom.us/j/91399666052?pwd=VCtmb0U0RVI5ckE4eXNHQkV0c1l0QT09
If needed, the passcode is 222823.