Geometry » Polytopes

Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The fatness of a 4-polytope $ P $ is defined to be $ (f_1 + f_2)/(f_0 + f_3) $ where $ f_i $ is the number of faces of $ P $ of dimension $ i $.

Question   Does there exist a fixed constant $ c $ so that every convex 4-polytope has fatness at most $ c $?

Keywords: f-vector; polytope

Posted by mdevos
updated May 12th, 2007
add new comment
Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

The $ d $-dimensional (hyper)cube $ Q_d $ is the graph whose vertices are all binary sequences of length $ d $, and two of the sequences are adjacent in $ Q_d $ if they differ in precisely one coordinate.

Conjecture   $ \displaystyle \lim \frac{cr(Q_d)}{4^d} = \frac{5}{32} $

Keywords: crossing number; hypercube

Posted by Robert Samal
updated July 18th, 2008
1 comment
Graph Theory » Topological G.T. » Crossing numbers

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2} \floor{\frac n2} \floor{\frac {n-1}2} $

Keywords: complete bipartite graph; crossing number

Posted by Robert Samal
updated May 11th, 2007
add new comment