On the crossing number of the Kneser graph K(n,2) - Sousa, A. D. R. de; Carneiro, J. C.; Faria, L.; Pabon, M. V. (Proceedings of the Theory of Computation Meeting (ETC), 2022)
The crossing number $ν(G)$ of a graph $G=(V,E)$ is the minimum number of crossings in a drawing $D(G)$ in the plane of $G$. Let $r$ be a straight line, called spine, $p\ geq 1$, and $S_1,…,S_p$ be $p$ distinct half-planes bounded by $r$. A drawing of $G=(V,E)$ in $p$-pages has the vertices of $V$ drawn in $r$ and each edge of $G$ is drawn in one of $S_1,…,S_p$. The crossing number in $p$-pages $ν_p(G)$ of $G$ is the minimum number of crossings in a drawing in $p$-pages of $G$. We prove that if $n=2q≥ 6$, then $ \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)) ≤ \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}$. Like complete graphs, $ν_2(K(n,2))=Θ(|V(K(n,2)|^4)=ν(K(n,2))$ and the leading term is $\ell(n)$, such that $\frac{1}{2^{13}}\ leq \ell(n)≤ \frac{1}{2^{10}}$.