O hranách křížících málo jiných hran v jednoduchých topologických úplných grafech grafech

Abstrakt

Nechť h = h(n) je nejmenší přirozené číslo takové, že každý jednoduchý topologický úplný graf na n vrcholech obsahuje hranu křížící nejvýše h jiných hran. Ukážeme, že platí Omega(n^(3/2)) {= h(n) {= O(n^2 / log^{1/4} n).

Také ukážeme, že analogická funkce na ostatních plochách (torus, Kleinova láhev) roste jako cn^2.

Klíčová slova

• edges
• crossing
• other
• edges
• simple
• topological
• complete
• graphs