Hyperbolic graph

In mathematics , hyperbolic graphs are important in graph theory , geometry, and group theory .

definition

Let it be a connected graph . We identify each edge with the unit interval and thus make the graph a metric space . (The distance between two nodes is therefore the number of edges of a minimal connection path.) ${\displaystyle X=(V,E)}$

The graph is called hyperbolic if there is one , so that for all triples of nodes and all shortest connecting paths from to for applies: ${\displaystyle \delta \geq 0}$ ${\displaystyle v_{1},v_{2},v_{3}}$ ${\displaystyle w_{ij}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$ ${\displaystyle i,j\in \left\{1,2,3\right\}}$

${\displaystyle w_{12}}$is in the neighborhood of ${\displaystyle \delta }$ ${\displaystyle w_{13}\cup w_{23}}$

${\displaystyle w_{13}}$is in the neighborhood of ${\displaystyle \delta }$ ${\displaystyle w_{12}\cup w_{23}}$

${\displaystyle w_{23}}$is in the neighborhood of ${\displaystyle \delta }$ ${\displaystyle w_{12}\cup w_{13}}$

Examples

• Finite graphs are hyperbolic, you can choose the diameter of the graph. ${\displaystyle \delta }$
• Trees are hyperbolic, you can choose. ${\displaystyle \delta =0}$
• The Farey graph is hyperbolic, you can choose. ${\displaystyle \delta =1}$
• Cayley graphs of hyperbolic groups are (by definition) hyperbolic.

Web links

• Hyperbolic graphs, fractal boundaries and graph limits (PDF; 5.4 MB)