Sbírka matematických úloh

Graf projektivních rovin

Úloha číslo: 3725

• Varianta

  Určete obvod \(g\) grafu \(G\). (Obvodem grafu, který obsahuje alespoň jednu kružnici, rozumíme velikost nejmenší kružnice v grafu obsažené.)

• Řešení

  Jelikož graf je bipartitní, obsahuje pouze kružnice (cykly) sudé délky. Nemůže obsahovat \(4\)-cyklus, protože takový \(4\)-cyklus by byl tvaru \(x_1\), \(p_1\), \(x_2\), \(p_2\), kde \(x_1\) a \(x_2\) jsou dva různé body a \(p_1\) a \(p_2\) jsou dvě různé přímky. To je ale spor s definicí konečné projektivní roviny, protože máme dvojici přímek, která se protíná ve dvou bodech. Tedy dostáváme, že obvod je alespoň \(6\).

  Naopak \(6\)-cyklus snadno v grafu nalezneme: Zvolíme tři body \(x_1\), \(x_2\) a \(x_3\), které neleží na jedné přímce. Označíme \(p_{ij}\) přímku určenou \(x_i\) a \(x_j\). Potom \(x_1\), \(p_{12}\), \(x_2\), \(p_{23}\), \(x_3\), \(p_{13}\) je hledaný \(6\)-cyklus.

• Odpověď

  \(g = 6\)

• Varianta

  Určete počet kružnic v \(G\) velikosti \(g\).

• Nápověda

  Rozmyslete si, že \(6\)-cykly odpovídají trojicím bodů, které neleží na jedné přímce.

• Řešení

  Při pohledu na řešení předchozí varianty si uvědomíme, že \(6\)-cykly v \(G\) jednoznačně odpovídají trojicím bodů z \(X\), které neleží na jedné přímce (rozmyslete si!).

  Jelikož \(|X| = q^2 + q + 1\), dostáváme, že počet všech trojic bodů z \(X\) je \(\binom{q^2 + q + 1}3\). Musíme však ještě odpočítat trojice, které leží na jedné přímce. Každá trojice bodů jednoznačně určuje přímku, na které leží. Počet přímek je \(q^2 + q + 1\) a každá přímka určuje \(\binom{q+1}3\) trojic bodů, které na ní leží. Dohromady tedy počet \(6\)-cyklů vychází

  \[ \binom{q^2+q+1}3 - (q^2 + q + 1)\binom{q+1}3 = \frac16(q^2 + q + 1)(q+1)q^3. \]

• Varianta

  Nechť \(H\) je bipartitní \((q+1)\)-regulární graf (tj. každý vrchol má stupeň \(q+1\)) pro \(q \geq 2\), bez kružnic velikosti \(4\) a takový, že mezi každými dvěma vrcholy existuje cesta délky nejvýše \(3\) spojující tyto dva vrcholy. Dokažte, že \(H\) je izomorfní \(G(X',\mathcal P')\) pro nějakou konečnou projektivní rovinu \((X',\mathcal P')\) řádu \(q\).

• Řešení

  Náznak řešení: Nechť \(A \cup B\) je disjunktní rozklad množiny vrcholů \(H\) odpovídající tomu, že \(H\) je bipartitní. Body z \(A\) budeme považovat za body projektivní roviny a body \(B\) za přímky.

  Potřebujeme vědět, že každé dva body leží na jedné přímce: nemohou ležet na dvou přímkách, jinak bychom našli \(4\)-cyklus. Naopak, pro dva různé body z \(A\) existuje v \(H\) cesta délky nejvýše \(3\), která je spojuje. Tato cesta však musí mít délku přesně \(2\), jelikož jsou body ve stejné části a prostřední vrchol této cesty je přímka z \(B\) obsahující tyto dva vrcholy.

  Že každé dvě přímky se protínají v právě jednom bodě získáme v úvahách výše záměnou \(A\) a \(B\).

  Nakonec snadno ověříme, že se jedná o projektivní rovinu tak, že ověříme axiom o existenci dvou přímek s alespoň třemi body namísto axiomu o existenci čtyř bodů v obecné poloze.