info prev up next book cdrom email home

Zarankiewicz's Conjecture

The Crossing Number for a Complete Bigraph is

\left\lfloor{n\over 2}\right\rfloor \left\lfloor{n-1\over 2}...
...m\over 2}\right\rfloor \left\lfloor{m-1\over 2}\right\rfloor ,

where $\left\lfloor{x}\right\rfloor $ is the Floor Function. This has been shown to be true for all $m,n\leq 7$. Zarankiewicz has shown that, in general, the Formula provides an upper bound to the actual number.

See also Complete Bigraph, Crossing Number (Graph)

© 1996-9 Eric W. Weisstein