22
$\begingroup$

I have just read on the German Wikipedia that an infinite graph is a graph with an infinite number of nodes or an infinite number of edges. I only know applications and algorithms for finite graphs.

What are infinite graphs good for?

What are applications of those? I can't imagine algorithms that would work on infinite graphs, as you can't store an infinite graph. So you can't operate on it.

Improve this question
$\endgroup$
2
  • $\begingroup$ a greedy algorithm that works by moving between vertices with finite edges can traverse the graph and find a new "preferred" or "best" vertex based on a cost or fitness function evaluated at each vertex. much work on optimization heuristics eg genetic algorithms can be regarded as traversing infinite graphs. $\endgroup$
    – vzn
    Commented Sep 11, 2012 at 18:54
  • 1
    $\begingroup$ see also applications of infinite graph theory, mathoverflow $\endgroup$
    – vzn
    Commented Sep 20, 2012 at 5:13

4 Answers 4

Reset to default
20
$\begingroup$

Many search problems in artificial intelligence (such as searching the game tree of a chess game, or searching for solutions to puzzles like the Rubik's cube, or more generally searching for sequences of actions to perform in order to accomplish some desired goal) are, in effect, algorithms on infinite graphs, even though the desired answer is a finite path. It is certainly possible to perform algorithms on such graphs, if they are represented implicitly.

But it is also true that mathematics may be useful even if it is not the mathematics of problems that can be solved by algorithms. Infinite graphs can be used to model birth and death processes (e.g. how do our rules for inheritance of names, and the rates at which people are born and die, lead to nonuniform distributions of family names among different human cultures?), to give a framework for approaching questions about mathematical symmetries (via Cayley graphs, which are often infinite), to provide models for reasoning about systems of logic (see Rado graph and saturated model), etc.

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ The tree of a chess game is finite - although it is unimaginable big - as a maximum number of moves exists (due to the fifty-move rule and threefold repetition). Thanks for your answer, you mentioned many ideas I didn't think of: +1 $\endgroup$
    – Martin Thoma
    Commented Sep 11, 2012 at 5:07
  • 2
    $\begingroup$ Do those rules force termination of the game? Or do they merely give players an additonal option, of calling a draw rather than continuing to move? $\endgroup$
    – David Eppstein
    Commented Sep 11, 2012 at 6:21
  • 1
    $\begingroup$ @DavidEppstein: They do impose a maximum move limit. If 50 moves are made without any player moving a pawn or capturing a piece, the game automatically ends in a draw, even if the players would like to continue. (But of course, this doesn't affect your answer.) $\endgroup$
    – user4772
    Commented Sep 11, 2012 at 7:21
  • 1
    $\begingroup$ @DavidEppstein: ah, sorry, I thought those rules forced termination. They do not as the FIDE rules (and wikipedia) state. See also math.stackexchange.com/q/194008/6876 for a related question. $\endgroup$
    – Martin Thoma
    Commented Sep 11, 2012 at 7:53
9
$\begingroup$

In the anti-ferromagnetic region of the Ising model, the computation complexity of approximating counting depends on the Gibbs measure over infinite $d$-regular trees. The Gibbs measure on these infinite $d$-regular trees undergoes a phase transition on a line called the uniqueness threshold.

On one side of the threshold, the Ising model is hard to approximate. On the other side of the threshold, the Ising model is easy to approximate. The complexity of the Ising model along the uniqueness threshold is currently an open problem, but the conjecture is that it is tractable.

The most recent result in this line of work is by Sly an Sun. See their references for other related works.

Improve this answer
$\endgroup$
3
$\begingroup$

To give you a particular application where it is useful to think about infinite graphs, consider a network of distributed nodes, each of which runs a distributed algorithm that proceeds in rounds. In every round a node can update its state by performing local computation and communicate by sending/receiving messages to/from its neighbors. The output of such an algorithm is the combined output of all nodes. For example, every node could locally decide whether it is part of an independent set.

Certain distributed computing problems can be solved in constant time (i.e. constant number of rounds until all nodes terminate), no matter how many nodes are in the network. In particular, any such algorithm will work on an infinite (but locally finite) graph. That said, many classic problems (like MIS) are subject to a lower bound of $\Omega(\log^* n)$ and thus cannot be computed on an infinite network.

Further discussion on this point can be found here.

Improve this answer
$\endgroup$
1
$\begingroup$

universal graphs are infinite & a generalization of the Rado random graph mentioned by DE. recent research in the area is in the direction of identifying universal graphs for a graph family F: ie, an infinite graph belonging to F that contains all finite graphs in F as induced subgraphs.

Improve this answer
$\endgroup$

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.