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.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze