Answer to Test Your Intuition (3)

Posted on May 27, 2009 by

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.

About these ads
This entry was posted in Geometry, Test your intuition and tagged . Bookmark the permalink.

2 Responses to 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:

Gravatar
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 )

Cancel

Connecting to %s