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}\).
