Sobre o número de cruzamentos do grafo de Kneser K(n,2) - Sousa, A. D. R. de; Carneiro, J. C.; Faria, L.; Pabon, M. V. (Anais do Encontro de Teoria da Computação (ETC); 2022: Anais do VII Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2022.222905, 2022)
O número de cruzamentos $ν(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≥ 1$, e $S_1,…,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,…,S_p$. O número de cruzamentos em $p$-páginas $ν_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≥ 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}} ≤ ν(K(n,2))≤ ν_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 $ν_2(K(n,2))=Θ(|V(K(n,2)|^4)=ν(K(n,2))$ cujo termo líder $\ell(n)$ satisfaz $\frac{1}{2^{13}}≤ \ell(n)≤ \frac{1}{2^{10}}$.