Timeline for The density hex
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 16, 2009 at 22:10 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 96 characters in body
|
| Dec 16, 2009 at 21:09 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 243 characters in body
|
| Dec 16, 2009 at 19:01 | comment | added | Gil Kalai | Anyway, it is a very nice problem and the connection to Gales theorem that Harrison found is also great. | |
| Dec 15, 2009 at 17:24 | comment | added | Gil Kalai | Yes, your graph seems intermediate one between G_\infty considered by BKLO and G_1 considered by AK; and your question for G_1 is also interesting and does not seem to be known (and also for the specific graph you study). | |
| Dec 15, 2009 at 11:47 | vote | accept | Harrison Brown | ||
| Dec 15, 2009 at 11:46 | comment | added | Harrison Brown | Huh -- Looking at the paper, I realize I heard Alon give a talk on the isoperimetric proof, and I even remember thinking "This might apply to this problem..." Apparently I then proceeded to forget about it entirely! But I don't think it's proved directly in either Bollobas et al or Alon-Klartag; their $G_\infty$ is slightly different from my graph and somewhat larger. But I'd be very surprised if the basic method didn't extend; I'll try it later. (Taking a break from mathematics today. Or so I'm telling myself...) | |
| Dec 15, 2009 at 11:06 | history | edited | Gil Kalai | CC BY-SA 2.5 |
added 699 characters in body
|
| Dec 14, 2009 at 21:02 | comment | added | Gil Kalai | I think we can expect for n fixed (say n=3) and d large a simpler combinatorial proof with much better bounds. anyway I think the results on separating all cycles in [0,1]^n and their discrete analogues are relevant. Look here (and the links there) :gilkalai.wordpress.com/2009/05/27/… | |
| Dec 14, 2009 at 20:49 | comment | added | Harrison Brown | The combination of a measure (in the wrong continuous density version) and fixed points (in the coloring version) makes me think of ergodic theory, but I don't know enough about ergodic theory to know if this is meaningful. As to your (#) statement, certainly any two consecutive vertices in the path lie in a combinatorial line, but three consecutive vertices can determine a comb. subspace of large dimension. I guess we can think of combinatorial lines as paths that remain locally comb. lines no matter what adjacency structure we put on them. Can we use this to derive DHJ from density hex? | |
| Dec 14, 2009 at 20:14 | comment | added | Harrison Brown | "Note that the topological proof of the coloring theorem does not rely on assuming n being fixed and d is large. when d is fixed (two) and n is large the coloring result is correct but the density result is far from being correct." This is essentially what motivates the question -- it seems to suddenly change from a topological problem to a combinatorial one, and I'd be very interested to see a way of bridging the gap. Incidentally, the failure of the density version fixing d and varying n is because there are sets with positive measure but lots of connected components. | |
| Dec 14, 2009 at 19:36 | history | edited | Gil Kalai | CC BY-SA 2.5 |
deleted 5 characters in body
|
| Dec 14, 2009 at 19:22 | history | answered | Gil Kalai | CC BY-SA 2.5 |