← All problems

Linhart–Eckhoff–Welzl conjecture and generalized crossing-number conjectures

For every integer n≥5n\ge 5, the crossing number of the complete graph satisfies cr⁡(Kn)=14⌊n2⌋⌊n−12⌋⌊n−22⌋⌊n−32⌋\operatorname{cr}(K_n)=\frac{1}{4}\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}{2}\right\rfloor\left\lfloor\frac{n-2}{2}\right\rfloor\left\lfloor\frac{n-3}{2}\right\rfloor. Equivalently, every drawing of KnK_n in the plane has at least this many edge crossings, and this bound is attained by a drawing of KnK_n.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

A 2026 paper proves several special cases and adds evidence for broader crossing-number conjectures, but the main conjectures remain open.

The Linhart–Eckhoff–Welzl conjecture concerns the maximum complexity of low-level regions in arrangements, with a related graph-drawing consequence for crossings. The broader entry also tracks higher-dimensional and generalized crossing-number conjectures; none is reported as completely resolved.

Known results

  • A 2025 paper proves the Linhart–Eckhoff–Welzl conjecture when n=d+4n=d+4 and determines the relevant linear and affine relations among level face numbers.
  • The same work proves the r=3r=3 case of the small gg-matrix nonnegativity conjecture, namely g1,k(V)≥0g_{1,k}(V)\ge 0 in the stated range, and derives a lower bound for crossings in spherical drawings of KnK_n.

October 14, 2026 partial results

A report dated October 14, 2026 describes Alfredo Hubard, Cheikh Saliou Ndiaye, and Oriol Solé-Pi's paper on crossing numbers of simplicial complexes in Euclidean and spherical spaces. It supplies structural and probabilistic evidence for generalized Harary–Hill-type statements and new graph-case results, but explicitly presents these as partial results rather than a complete proof.

Current status (as of October 2026): Special cases and supporting results are established, while the full Linhart–Eckhoff–Welzl conjecture and the broader generalized crossing-number conjectures remain open.

Sources

Solutions 0

No solutions have been posted yet.