Skip to main content
added 1173 characters in body
Source Link
Jeff McGowan
  • 465
  • 1
  • 5
  • 12

Suppose I have a 3 regular graph, and I cut enough edges to get a spanning tree. The leaves (which we often call "half edges") are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. 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. The

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, put a triangle at each vertex, and you get an octagon with paired sides, thus a two holed torus (depending on the pairings, you might of course get a torus or a sphere). Now imagine a much bigger graph, but the same idea. Start with a random graph, cut edges, and generate a fundamental domain (note again 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. The question is not exactly well formed, but what we would like to know is how close oneI think you can get to onethink of the followingtwo basic possibilities - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

@jc's suggestion, I moved the clarifications up here, duh :-)

Suppose I have a 3 regular graph, and I cut enough edges to get a spanning tree. The leaves (which we often call "half edges") are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. 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. The question is not exactly well formed, but what we would like to know is how close one can get to one of the following - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

@jc's suggestion, I moved the clarifications up here, duh :-)

Suppose I have a 3 regular graph, and I cut enough edges to get a spanning tree. The leaves (which we often call "half edges") are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. 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.

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, put a triangle at each vertex, and you get an octagon with paired sides, thus a two holed torus (depending on the pairings, you might of course get a torus or a sphere). Now imagine a much bigger graph, but the same idea. Start with a random graph, cut edges, and generate a fundamental domain (note again 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. The question is not exactly well formed, but I think you can think of two basic possibilities - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

@jc's suggestion, I moved the clarifications up here, duh :-)

added 167 characters in body
Source Link
Jeff McGowan
  • 465
  • 1
  • 5
  • 12

Suppose I have a 3 regular graph, and I clipcut enough edges to get a spanning tree. The leaves (which we often call "half edges") are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. TheThe 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. The question is not exactly well formed, but what we would like to know is how close one can get to one of the following - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

I have some ideas about how to approach this, but it seems to be very tricky to get very much@jc's suggestion, I moved the first few are pretty easyclarifications up here, but after that it just gets crazy.

Thanks!duh :-)

Suppose I have a 3 regular graph, and I clip enough edges to get a spanning tree. The "half edges" are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. The question is not exactly well formed, but what we would like to know is how close one can get to one of the following - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

I have some ideas about how to approach this, but it seems to be very tricky to get very much, the first few are pretty easy, but after that it just gets crazy.

Thanks!

Suppose I have a 3 regular graph, and I cut enough edges to get a spanning tree. The leaves (which we often call "half edges") are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. 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. The question is not exactly well formed, but what we would like to know is how close one can get to one of the following - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

@jc's suggestion, I moved the clarifications up here, duh :-)

Source Link
Jeff McGowan
  • 465
  • 1
  • 5
  • 12

Spanning trees in 3 regular graphs.

Suppose I have a 3 regular graph, and I clip enough edges to get a spanning tree. The "half edges" are identified in pairs, and what we are interested in is the length of the paths in the graphs joining these half edges. The question is not exactly well formed, but what we would like to know is how close one can get to one of the following - 1) a spanning tree with one long path and many short ones 2) a spanning tree with most paths roughly the same length.

I have some ideas about how to approach this, but it seems to be very tricky to get very much, the first few are pretty easy, but after that it just gets crazy.

Thanks!