Timeline for What is the Cheeger constant of a cubical subset of the cubic lattice?
Current License: CC BY-SA 2.5
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 23, 2010 at 12:30 | vote | accept | Henry Segerman | ||
| Jul 23, 2010 at 10:00 | answer | added | Henry Segerman | timeline score: 2 | |
| Jul 21, 2010 at 17:22 | comment | added | Henry Segerman | Hi all, I had looked into the spectral results before, but I hadn't seen much with actual calculated values rather than bounds. There are some papers cited in the link Will Jagy posted that look like they might do what I want though (in particular, "Edge-isoperimetric inequalities in the grid" by Bollob\'{a}s and Leader). I don't particularly need the result other than as a comparison with other kinds of graphs, and it seemed like an example someone would have looked at before. | |
| Jul 21, 2010 at 17:12 | comment | added | Kevin P. Costello | One reference that may be relevant is Bollobás and Leader's "Edge-isoperimetric inequalities in the grid". I haven't seen the full paper, but among the results claimed in the abstract is that the semi-cube has the smallest edge-boundary over all sets containing between 1/4 and 3/4 of the vertices. | |
| Jul 21, 2010 at 15:35 | comment | added | Mark Meckes |
I will add quickly, though, that exact solutions of such isoperimetric problems are often very hard to come by, and it's often much easier to get an estimate of the order of $h(G)$. Would it be good enough for you just to know that $h(G) \ge c/n$ for some constant $c > 0$?
|
|
| Jul 21, 2010 at 15:17 | comment | added | Mark Meckes | Hi Henry. I don't have time to think about this at the moment, but I added a couple (nonobvious?) tags that may attract the attention of people who know the right kind of stuff. (Follow Will's link to see something of the connections.) | |
| Jul 21, 2010 at 15:15 | history | edited | Mark Meckes |
Added tags
|
|
| Jul 21, 2010 at 5:11 | comment | added | Will Jagy | See math.ucsd.edu/~fan/research/revised.html | |
| Jul 21, 2010 at 2:03 | comment | added | Will Jagy | Does it work in $\mathbb Z^2 ?$ | |
| Jul 20, 2010 at 23:56 | history | asked | Henry Segerman | CC BY-SA 2.5 |