Sobre o número de cruzamentos do grafo de Kneser K(n,2)
Resumo
O número de cruzamentos $\nu(G)$ de um grafo $G=(V,E)$ é o menor número de cruzamentos em um desenho $D(G)$ no plano de $G$. Dada uma reta $r$, chamada espinha, $p\geq 1$, e $S_1,\ldots,S_p$ serem $p$ semiplanos distintos limitados por $r$, um desenho de $G=(V,E)$ em $p$-páginas tem os vértices de $V$ desenhados em $r$ e cada aresta de $G$ é desenhada em um $S_1,\ldots,S_p$. O número de cruzamentos em $p$-páginas $\nu_p(G)$ de $G$ é o menor número de cruzamentos em um desenho de $G$ em $p$ páginas. Nós provamos que se $n=2q\geq 6$, então $\frac{n^8} {2^{13}} - 9\frac{n^7}{2^{13}} - \frac{n^6}{2^{10}} - \frac{n^4} {2^{7}} - \frac{n^3}{2^{9}} \leq \nu(K(n,2))\leq \nu_2(K(n,2))\ leq \frac{n^8}{2^{10}} - \frac{3n^7}{2^8} + \frac{31n^6}{2^83} + \ frac{7n^5}{2^6} - \frac{563n^4}{2^73} + \frac{517n^3}{2^53} - \ frac{267n^2}{2^5} + \frac{107n}{2^33}$. Como os grafos completos $\nu_2(K(n,2))=\Theta(|V(K(n,2)|^4)=\nu(K(n,2))$ cujo termo líder $\ell(n)$ satisfaz $\frac{1}{2^{13}}\leq \ell(n)\leq \frac{1}{2^{10}}$.
Referências
Berge, C. (1973). Graphs and hypergraphs. North-Holland Pub. Co.
de Klerk, E., Pasechnik, D. V., and Salazar, G. (2013). Improved lower bounds on book crossing numbers of complete graphs. SIAM J. Discret. Math., 27(2):619–633.
Faria, L., de Figueiredo, C. M. H., Richter, R. B., and Vrt’o, I. (2016). The same upper bound for both: The 2-page and the rectilinear crossing numbers of the n-cube. J. Graph Theory, 83(1):19–33.
Hlinený, P. (2006). Crossing number is hard for cubic graphs. J. Comb. Theory, Ser. B, 96(4):455–471. Kneser, M. (1955). Aufgabe 360, Jber. Deutsch. Math. Verein, 58:27.
Székely, L. A. (1997). Crossing numbers and hard Erdos problems in discrete geometry. Combinatorics, Probability and Computing, 6(3):353–358.
