Publikace na Matematicko-fyzikální fakulta |
2006
Abstrakt
Definujme $h=h(n)$ jako nejmenší přirozené číslo takové, že každý jednoduchý topologický graf na $n$ vrcholech obsahuje hranu protínající nejvýše $h$ jiných hran. Ukazujeme, že $\Omega(n^{3/2})\le h(n) \le O(n^2/\log^{1/4}n)$.