4
$\begingroup$

I am interested in algorithms that help decide whether a countably infinite locally finite graph is connected.

I think there is no algorithm that works for all graphs, e.g. no algorithm should work for an infinite chain with one edge removed.

I care about a specific graph $\Gamma$ whose automorphism group acts with finite quotient, i.e. there are only finitely many orbits of vertices. Also $\Gamma$ can be realized as an explicit collection of points in $\mathbb R^n$, and there is an easily computable function $d:\mathbb R^n\times \mathbb R^n\to \mathbb R$ such that two vertices $v,w$ are adjacent if and only if $d(v,w)=0$. I hope to find an algorithm that can be implemented so that after some computer experiments I would have evidence that the graph is actually connected.

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ 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. $\endgroup$
    – HJRW
    Apr 4, 2010 at 15:45
  • 3
    $\begingroup$ 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. $\endgroup$
    – Sergei Ivanov
    Apr 4, 2010 at 16:19
  • 6
    $\begingroup$ 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. $\endgroup$
    – Sergei Ivanov
    Apr 4, 2010 at 16:30
  • 1
    $\begingroup$ 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! $\endgroup$
    – HJRW
    Apr 4, 2010 at 16:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sergei Ivanov
    Apr 4, 2010 at 17:20

1 Answer 1

Reset to default
5
$\begingroup$

My original example was not locally finite, this is a different example which is locally finite.

Given a Turing machine T, let GT be the graph whose vertex set is {-1,+1}×ℤ, and (a,n) is connected to (b,m) if and only if either a = b and |m-n| = 1, or a ≠ b and T halts (with blank input) in exactly |m - n| steps. This is computable since it is decidable whether T halts in a given number of steps. The automorphism group of GT acts transitively since the maps (a,n) → (±a,n+k) are always automorphisms. The graph GT is connected if and only if T eventually halts. Since the halting problem is undecidable, there is no algorithm that will uniformly decide whether GT is connected.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I guess a much simpler example has vertex -17 and also vertex s when T halts in exactly s steps; no edges. However, this feels even more like cheating than the above example. Regardless, I think the question would have a much better answer if the the relevant graphs were more thoroughly explained. $\endgroup$
    – François G. Dorais
    Apr 4, 2010 at 19:07
  • $\begingroup$ Thanks! I really do not know much about the graph beyond what I stated. There is a closely related problem that is easier to explain. There the graph arises from a locally finite arrangement of hyperplanes in $\mathbb C^n$, where vertices correspond to hyperplanes, and two vertices are adjacent if and only if the hyperplanes intersect. This graph need not not locally finite though. $\endgroup$
    – Igor Belegradek
    Apr 5, 2010 at 0:37
  • $\begingroup$ @damiano: complex hyperplanes have codimension $2$, so I do not see why connectedness comes for free. In truth I have thought more of the case when $\mathbb C^n$ is replaced with the unit ball in $\mathbb C^n$ with the complex hyperbolic metric, and in this case I have tons of examples of arrangements whose correspondning graphs aren't connected. $\endgroup$
    – Igor Belegradek
    Apr 5, 2010 at 1:00
  • $\begingroup$ @IB: sorry, i had erased my comment, since it did not seem relevant! It simply seemed to me that two hyperplanes either intersect or they are parallel and as soon as two intersect, then any other hyperplane must intersect one of the two, since it cannot be parallel to both. $\endgroup$
    – damiano
    Apr 5, 2010 at 1:05
  • $\begingroup$ @damiano: actually you are right, this is what happens in $\mathbb C^n$, but things become different once we only pay attentions to intersections inside the unit ball, so in my comments above substitute $\mathbb C^n$ by the unit ball in $\mathbb C^n$ with the complex hyperbolic metric. $\endgroup$
    – Igor Belegradek
    Apr 5, 2010 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.