Question: Let be the
-dimensional cube. Turn
into a torus
by identifying opposite facets. What is the minumum
-dimensional volume
of a subset
of
which intersects every non-trivial cycle in
.
Answer: Taking to be all points in the solid cube with one coordinate having value 1/2, gives you a set
that seperates all cycles and has
-dimensional volume equals
. It is not difficult to prove that
. Guy Kindler, Ryan O’donnell, Anup Rao and Avi Wigderson proved the existence of
which seperates all cycles with
. A simpler argument was found by Noga Alon and Boaz Klartag. For an even simpler treatement of this result along with several discrete analogs see this paper by Noga.
Advertisements
Pingback: Test Your Intuition (4) « Combinatorics and more
Pingback: Answer To Test Your Intuition (4) « Combinatorics and more