Grafy bez čtyřcyklu

Úloha číslo: 3724

Dokažte, že pro nekonečně mnoho různých \(n\) existují grafy na \(n\) vrcholech s \(\Omega(n^{3/2})\) hranami, které neobsahují jako podgraf čtyřcyklus (\(C_4\)). Ke konstrukci můžete elegantně využít konečné projektivní roviny.

  • Řešení

    Všimneme si, že graf incidence projektivní roviny nemůže obsahovat čtyřcyklus \(a,P,b,Q\), protože by to znamenalo, že se přímky \(P\) a \(Q\) protínají ve dvou bodech.

    Je-li \(G\) graf incidence projektivní roviny řádu \(k\), je \(|V_G|=n=2k^2+2k+2\) a \(|E_G|=(k^2+k+1)(k+1)\). Protože \((k+1)^2>k^2+k+1\), dostaneme \(|E_G|\ge \frac{n}2 \sqrt{\frac{n}2}=2^{-3/2}n^{3/2}\).

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha řešená úvahou
En translation
	Zaslat komentář k úloze