Answer to Test Your Intuition (3)

Question: Let X=[0,1]^d be the d-dimensional cube. Turn X into a torus T^d by identifying opposite facets. What is the minumum (d-1)-dimensional volume f(d) of a subset Y of X which intersects every non-trivial cycle in T^d.

Answer: Taking Y to be all points in the solid cube with one coordinate having value 1/2, gives you a set Y that seperates all cycles and has (d-1)-dimensional volume equals d. It is not difficult to prove that f(d) \ge C\sqrt d. Guy Kindler, Ryan O’donnell, Anup Rao and Avi Wigderson proved the existence of Y which seperates all cycles with vol(Y) =O(\sqrt d). 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.

2 thoughts on “Answer to Test Your Intuition (3)

  1. Pingback: Test Your Intuition (4) « Combinatorics and more

  2. Pingback: Answer To Test Your Intuition (4) « Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s