<p>In the anti-ferromagnetic region of the <a href="http://en.wikipedia.org/wiki/Ising_model">Ising model</a>, the computation complexity of approximating counting depends on the <a href="http://en.wikipedia.org/wiki/Gibbs_measure">Gibbs measure</a> 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.</p>

<p>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.</p>

<p>The most recent <a href="http://arxiv.org/abs/1203.2602v1">result</a> in this line of work is by Sly an Sun.  See their references for other related works.</p>

CC BY-SA 3.0
2012-09-11T04:53:26.700Z
2012-09-11T04:53:26.700Z
Tyson Williams
<p>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.</p>

<p>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 <a href="http://www.cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf" rel="nofollow noreferrer">lower bound</a> of $\Omega(\log^* n)$ and thus cannot be computed on an infinite network.</p>

<p>Further discussion on this point can be found
<a href="https://cstheory.stackexchange.com/questions/9313/infinitely-large-but-locally-finite-computation-problems/9321#9321">here</a>.</p>

CC BY-SA 3.0
2012-09-11T19:00:21.090Z
2012-09-11T19:00:21.090Z
2017-04-13T12:32:28.077Z
Peter
<p><a href="http://en.wikipedia.org/wiki/Universal_graph" rel="nofollow">universal graphs</a> are infinite &amp; 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.</p>

CC BY-SA 3.0
2012-09-11T18:50:30.543Z
2012-09-11T18:50:30.543Z
vzn
<p>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 <a href="http://en.wikipedia.org/wiki/Implicit_graph">implicitly</a>.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Cayley_graph">Cayley graphs</a>, which are often infinite), to provide models for reasoning about systems of logic (see <a href="http://en.wikipedia.org/wiki/Rado_graph">Rado graph</a> and <a href="http://en.wikipedia.org/wiki/Saturated_model">saturated model</a>), etc.</p>

CC BY-SA 3.0
2012-09-11T05:07:19.500Z
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](http://en.wikipedia.org/wiki/Fifty-move_rule) and [threefold repetition](http://en.wikipedia.org/wiki/Threefold_repetition)). Thanks for your answer, you mentioned many ideas I didn't think of: +1
Martin Thoma
CC BY-SA 3.0
2012-09-11T06:21:32.947Z
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?
David Eppstein
CC BY-SA 3.0
2012-09-11T07:53:16.813Z
@DavidEppstein: ah, sorry, I thought those rules forced termination. They do not as the FIDE rules (and wikipedia) state. See also http://math.stackexchange.com/q/194008/6876 for a related question.
Martin Thoma
CC BY-SA 3.0
2012-09-11T04:56:32.100Z
2012-09-11T04:56:32.100Z
David Eppstein
<p>I have just read on the <a href="http://de.wikipedia.org/wiki/Unendlicher_Graph">German Wikipedia</a> 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. </p>

<p><strong>What are infinite graphs good for?</strong></p>

<p>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.</p>

CC BY-SA 3.0
2012-09-11T18:54:12.080Z
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.
vzn
CC BY-SA 3.0
2012-09-20T05:13:40.107Z
see also [applications of infinite graph theory, mathoverflow](http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory)
vzn
<graph-theory><co.combinatorics>
What are infinite graphs good for?
Martin Thoma
# What are infinite graphs good for?

(Asked by: username_0 on 2012-09-11)

I have just read on the [German Wikipedia](http://de.wikipedia.org/wiki/Unendlicher_Graph) 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.

**Tags:** graph-theory, co.combinatorics

> **Comments:**
> **username_1**: 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.  
> **username_1**: see also [applications of infinite graph theory, mathoverflow](http://mathoverflow.net/questions/39647/applications-of-infinite-graph-theory)  

---

## 4 answers

### Answer by username_4 on 2012-09-11. Score: 20 | Accepted answer

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](http://en.wikipedia.org/wiki/Implicit_graph).

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](http://en.wikipedia.org/wiki/Cayley_graph), which are often infinite), to provide models for reasoning about systems of logic (see [Rado graph](http://en.wikipedia.org/wiki/Rado_graph) and [saturated model](http://en.wikipedia.org/wiki/Saturated_model)), etc.

> **Comments:**
> **username_0**: 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](http://en.wikipedia.org/wiki/Fifty-move_rule) and [threefold repetition](http://en.wikipedia.org/wiki/Threefold_repetition)). Thanks for your answer, you mentioned many ideas I didn't think of: +1  
> **username_4**: 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?  
> **username_0**: @DavidEppstein: ah, sorry, I thought those rules forced termination. They do not as the FIDE rules (and wikipedia) state. See also http://math.stackexchange.com/q/194008/6876 for a related question.  

---

### Answer by username_2 on 2012-09-11. Score: 9

In the anti-ferromagnetic region of the [Ising model](http://en.wikipedia.org/wiki/Ising_model), the computation complexity of approximating counting depends on the [Gibbs measure](http://en.wikipedia.org/wiki/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](http://arxiv.org/abs/1203.2602v1) in this line of work is by Sly an Sun. See their references for other related works.


---

### Answer by username_3 on 2012-09-11. Score: 3

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](http://www.cs.huji.ac.il/~nati/PAPERS/locality_dist_graph_algs.pdf) of $\Omega(\log^\* n)$ and thus cannot be computed on an infinite network.

Further discussion on this point can be found
[here](https://cstheory.stackexchange.com/questions/9313/infinitely-large-but-locally-finite-computation-problems/9321#9321).


---

### Answer by username_1 on 2012-09-11. Score: 1

[universal graphs](http://en.wikipedia.org/wiki/Universal_graph) 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.


---

