Can we define an isomorphism invariant to measure "dimension" of an undirected simple graph?

Question

Can we define a characteristic to measure the "dimension" of a graph?

Let's start by some simple example. Intuitively, a circuit graph with $n$ nodes and $n$ edges should have dimension $1$. Likewise, an $(n \times n)$-torus should have dimension $2$, etc. So, can we define a general concept of "dimension" for every graphs? Maybe we could draw inspiration from Hausdorff dimension?

This question is inspired by When do 3D random walks return to their origin?.

---

As Mikhail Tikhomirov pointed out, we may meet difficulty in defining a certain "dimension". From my point of view, I think that it is beacuse a finite graph does not have enough details or microstructure/macrostructure. Therefore, could we consider this problem on infinite graph such as the infinite $2$-dimensional grid graph?

Answer 1

Five answers, 'by vague association' and 'lateral thinking' (which is unavoidable for this vague question, I think).

All in all, I think that any definition you will give will have an 'air' of arbitrariness: the most straightforward 'take' on this is to point out that (realizations of) graphs are after all just one-dimensional simplicial complexes, so in that sense every graph has dimension one, and one answer to your answer, taken unimaginatively literally, should be

Yes we can: we assign each graph the number 1. There is nothing else to say.${}$(short.answer)

Four more 'divergent' remarks now follow.

1. The graph invariant called 'genus'. A traditional, important graph invariant spiritually similar to what you are asking about is the genus of a graph.

I am aware that one may argue that this does not capture the intuition of 'dimension'. But then again, you yourself tagged this a 'soft-question', so this answer should be sort-of-acceptable to you.

Also worth pointing out: as you will probably known, for any fixed dimension $d\geq 3$, any countable graph can be embedded into $\mathbb{R}^d$, a fact which by the way can be proved working only over the 'signature' of graph-theory, plus a little intuitive geometry, by an inductive argument; you do not need the usual argument via a Vandermonde matrix (not that this would be 'bad', yet the proof via the 'moment curve' wields a 'signature' which besides $\sim$ (adjacency) and $\#$ ('intersects') also uses $\mathbb{Z}$, and '$+$' and '$\cdot$').

2. The methods around the ideas of 'thickening point clouds' and 'persistent homology'. Your question also reminded me of the very active field of 'persistent homology' (and related ideas). Again, it does not fit your specifications precisely. For this to be relevant to your question, of course, the data that you wish to associated your isomorphism invariant to must be given inside a metric space. A purely combinatorial graph will not be enough to make these methods 'bite'.

If so inclined, you can start reading about this in the following two references

National Science Foundation Mathematical Sciences Institutes: Topology of Shapes, Persistent Homology and Point Clouds: Where Does it Take Us?

H. Edelsbrunner and J. Harer. Persistent homology --- a survey. Surveys on Discrete and Computational Geometry. Twenty Years Later, 257-282, eds. J. E. Goodman, J. Pach and R. Pollack, Contemporary Mathematics 453: Persistent Homology — a Survey

3. 'Neighbourhood complexes' of graphs. You can assign to your graph the **vector of the Betti numbers of the abstract simplicial complex whose faces are precisely the subsets of neighborhoods of vertices. Since Bettin numbers are often perceived to be sort-of-a-dimension, this is another approach relevant to your question. One starting point to read up on this could be

Matthew Kahle: The neighborhood complex of a random graph. Journal of Combinatorial Theory, Series A 114 (2007) 380–387

4. Graphs as knots. This is something of a non-example, the relation to the idea of 'dimension' being almost non-existant. One can ask knot-theoretic questions about graphs. However, please note the nice summary of Dror Bar-Natan's in this MO thread, which gives a sense in which there is no 'knot-theory of graph' at all.

5. Zariski dimension of associated commutative rings. You could construct some functor¹ $F\colon\mathsf{SomeReasonableCategoryOfGraphs}\to\mathsf{CommutativeRings}$, and then take the Krull dimension of $F(G)$ as your "dimension" of $G$. I do not know of anyone who would think this a motivated thing to do.

Let me reiterate: all this except (short.answer) seems arbitrary and context-dependent and would say more about the person doing this than about a hard mathematical reality. There are, of course, many wonderful and useful things to learn along any of these roads, but you should be aware that the choice of what road to take is arbitrary. Please forgive this expression: the question in this OP is more of a mathematical Rorschach test than a mathematical question.

1 _{There are many possibilities to associate rings to graphs. Note, however, that using the word 'functor' immediately implies that your construction will have to be graph-isomorphism-invariant, since any functor takes isos to isos.}

Answer 2

One way to distinguish a cycle from a torus is that for not too large $d$ the number of vertices at most $d$ steps away from a chosen vertex is $\Omega(d)$ for the cycle and $\Omega(d^2)$ for the torus. Hence the "dimension" $d(G)$ of a graph $G$ may be defined as $\beta$ in the best approximation of the number $\omega_d(G)$ of pairs of vertices at distance at most $d$ with $C n d^\beta$ for $d$ much smaller than the diameter of $G$.

A problem of this definition is that $\omega_d(G)$ may exhibit several regimes of growth for certain graphs. For example, take a $w \times h$ grid graph with $w << h$. Then for $d < w$ we will have $\beta = 2$, but $\beta = 1$ for $w < d < h$. It is not hard to construct a graph that exhibit any given kind of piecewise constant regime of $\beta$. Hence it is hard to name a single number that describes the "dimension" of the graph, but rather the information about "dimension spectrum" is encoded in the sequence $\omega_d(G)$.