Timeline for Deciding when an infinite graph is connected
Current License: CC BY-SA 2.5
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 4, 2010 at 17:30 | answer | added | François G. Dorais | timeline score: 5 | |
| Apr 4, 2010 at 17:20 | comment | added | Sergei Ivanov | Actually the size of the quotient is not enough too. You cannot tell a line from a bunch of very long loops although both are homogeneous. | |
| Apr 4, 2010 at 17:11 | comment | added | François G. Dorais | Igor, you can build tons of undecidable examples using the simple fact that there is no finite algorithm to decide whether two real numbers are equal. However, I'm pretty sure this will not be satisfactory to you since I'm pretty sure none of these simplistic examples fit the actual graphs you have in mind. We would be happy to help if you make your description more specific. | |
| Apr 4, 2010 at 16:37 | comment | added | Igor Belegradek | Thanks for the comments. Sergei, could you elaborate on the algorithm? Suppose for simplicity the quotient graph consists of ONE edge, what do you do? | |
| Apr 4, 2010 at 16:31 | comment | added | HJRW | Igor, when you "fix n" you are basically saying that you know the size of the quotient. That's why the quotient graph is relevant! | |
| Apr 4, 2010 at 16:30 | comment | added | Sergei Ivanov | If you have only one graph, then there is a program. It is either "begin; print YES; end" or "begin; print NO; end", depending on your graph. | |
| Apr 4, 2010 at 16:19 | comment | added | Sergei Ivanov | You need a way to bound the size of the quotient as Henry Wilton's comment shows. Another explanation: Consider all computable functions that can produce a graph whose nodes are indexed by $\mathbb Z$, and which is either real line or a segment $[-n,n]$ plus a bunch of isolated nodes ($n$ is arbitrary). You can not tell algorithmically functions of the first type from the second type, so you need a bound for $n$ as an input to your program. | |
| Apr 4, 2010 at 16:06 | comment | added | Igor Belegradek | Henry, I have one graph, not a family of graphs. If you fix $n$ and wait long enough, you shall see that your $\Gamma_n$ is not connected. | |
| Apr 4, 2010 at 16:03 | comment | added | Igor Belegradek | There seems to be no way to write a presentation for the automorphism group (the group is actually a complex hyperbolic lattice, it is hard to find presentations for those), but with some work it should be possible to get explicit information on the quotient graph. Why is the structure of the quotient graph relevant? | |
| Apr 4, 2010 at 15:45 | comment | added | HJRW | Igor, how about the following family of examples? \Gamma_n is the real line, with the usual graph structure, with every nth edge removed. It seems to me that these graphs are just as hard to distinguish from the real line as your example with just one edge removed, but the automorphism group now acts with finite quotient. | |
| Apr 4, 2010 at 15:18 | comment | added | Sergei Ivanov | How the information about the automorphism group is presented? Do you only know that there is some group with finite quotient, or you know the size of the quotient, a set representing all orbits, or something like this? | |
| Apr 4, 2010 at 15:18 | comment | added | Andy Putman | Do you know generators for the automorphism group? | |
| Apr 4, 2010 at 15:02 | history | asked | Igor Belegradek | CC BY-SA 2.5 |