
> 
> 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?](https://mathoverflow.net/questions/45098/).




---


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?



Can we define an isomorphism invariant to measure "dimension" of an undirected simple graph?
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](http://mathworld.wolfram.com/GraphGenus.html).


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?*](https://mathinstitutes.org/highlights/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*](http://pub.ist.ac.at/%7Eedels/Papers/2008-B-02-PersistentHomology.pdf)
> 
> 
> 


**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](http://www.sciencedirect.com/science/article/pii/S0097316506000781)
> 
> 
> 


**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](https://mathoverflow.net/questions/79488/is-there-a-knot-theory-for-graphs), 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 functor1 $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](https://en.wikipedia.org/wiki/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.


