Množiny s malými průniky
Úloha číslo: 3812
Dokažte, že existuje konstanta \(c\) splňující následující tvrzení. V každém souboru \(S_1, …, S_n\) podmnožin množiny \(\{1,\cdots, n\}\), kde \(n\) je přirozené číslo, splňujícím \(|S_i \cap S_j| \le 1\) pro všechna \(i, j\) taková, že \(1 \leq i < j \leq n\), lze nalézt \(S_i\) s nejvýše \(c \sqrt n\) prvky.
Nápověda
Prozkoumejte bipartitní graf s částmi \(\{1,…,n\}\) a \({S_1,…, S_n}\).
Řešení
Graf incidence nemůže obsahovat čtyřcyklus, tedy má nejvýše \(O(n^{3/2})\) hran. Průměrný stupeň je \(O(\sqrt{n})\) a nutně existuje vrchol, jehož stupeň průměr nepřevyšuje.