Timeline for Spanning trees in 3 regular graphs.
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 18, 2011 at 9:18 | answer | added | Martin Tancer | timeline score: 1 | |
| Sep 17, 2011 at 19:32 | answer | added | Joseph O'Rourke | timeline score: 6 | |
| Sep 17, 2011 at 13:45 | history | edited | Jeff McGowan | CC BY-SA 3.0 |
added 1173 characters in body
|
| Sep 17, 2011 at 13:33 | history | edited | Jeff McGowan | CC BY-SA 3.0 |
added 167 characters in body
|
| Sep 16, 2011 at 10:54 | comment | added | Jeff McGowan | Now imagine a much bigger graph, but the same idea. Start with a random graph, cut edges, and generate a fundamental domain (note that it is unclear what the genus of the related surface will actually be, but ignore that for now). The hope would be that one could get the "usual" domain $aba^{-1}b^{-1}cdc^{-1}d^{-1}\ldots$ with sides identified in alternating pairs, but of course this is not usually possible while respecting the triangulation. So the question is can one somehow get something with all the paired leaves roughly the same distance or with one set far apart and the others close. | |
| Sep 16, 2011 at 10:42 | comment | added | Jeff McGowan | Let's see, first, yes just the leaves, but identified in pairs. The issues isn't construction, but what happens with a random 3-regular graph. Long and short are relative. As an example, consider the usual two holed torus, which can be given by identifying the edges of an octagon in pairs. Triangulate the octagon, put a vertex in every triangle, and connect neighboring vertices with an edge. Include vertices which have a paired external side, so you get a 3 regular graph. Now imagine reversing direction, so you start with a random 3 regular graph, and you cut edges until you have a tree. | |
| Sep 16, 2011 at 4:30 | comment | added | Gerhard Paseman | I considered 3-regular graphs in this question mathoverflow.net/questions/64746/…, which provided a counterexample for Alain Valette. You might use that and similar examples to guide your intuition for this problem. Gerhard "Ask Me About System Design" Paseman, 2011.09.15 | |
| Sep 16, 2011 at 2:56 | comment | added | j.c. | @Jeff McGowan, it may help if you describe an explicit example of a cubic graph and the process of "clipping" it to a spanning tree in your question. You might also be able to explain more what you're looking for in 1) and 2) with an example at hand. | |
| Sep 16, 2011 at 2:37 | comment | added | Daniel Mansfield | Also, I'm sure you can construct an example of 3-regular graphs which has many "long" paths and many "short" ones. It would look something like a big Y. Perhaps more detail about what is considered long and short would be helpful. Or, if you didn't like the big "Y", here's another example t1.gstatic.com/… | |
| Sep 16, 2011 at 2:27 | comment | added | Daniel Mansfield | So are the half edges just the leaves of the tree? | |
| Sep 16, 2011 at 2:13 | comment | added | Jeff McGowan | Sorry, I'm using the language I'm used to using with my colleague Eran Makover. What I mean by "clip" is to cut the edge, of course when you cut enough edges you get a tree. If you then embed the tree in the plane, each edge which was cut shows up in two places, and those we consider identified. The background is that what we are really looking at is Riemann surfaces, and the graph corresponds to a triangulation, and the tree corresponds to a fundamental domain, where the "half edges" are identified sides - think Belyi and Grothendieck. Does that make sense? | |
| Sep 16, 2011 at 1:57 | comment | added | Alon Amit | What do "clip" and "half edges" mean? | |
| Sep 16, 2011 at 1:54 | history | asked | Jeff McGowan | CC BY-SA 3.0 |