5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Dear @ Lwins.Gafiel: I made several edits to your OP. Stylistic throughout. In particular, I strongly recommend to avoid the term "$n$-ring". Graph theory is still in such a stage that sometimes it is accused of too much "whimsicality" and permissiveness;I care about that; using terms like "$n$-ring", for which a standard technical term does exist, does not help in that respect. If you insist on some of the removed parts of your OP, please re-edit. $\endgroup$ – Peter Heinig Sep 25 '17 at 14:08
  • $\begingroup$ To @PeterHeinig. Thanks for your edit. I used the term "ring" just because there is a question in CS Theory called ring election. Now I know its standard name. $\endgroup$ – Lwins Sep 25 '17 at 14:36
  • $\begingroup$ I think my answer applies just as well to the infinite case. The finite graphs are only different in the fact that on a large scale they look "0-dimensional". $\endgroup$ – Mikhail Tikhomirov Sep 25 '17 at 15:38
  • $\begingroup$ I don't really know what to 'think of' the 'number-of-vertices-in-a-ball-of-constant-radius-proposal', yet I think it is very relevant to consider this proposal in the light of the existence of expander graphs. By e.g. Exercise 1.1.12 in Terence Tao: Expansion in Finite Simple Groups of Lie Type. AMS GSM 164, for any given $k$ and any $\varepsilon >0$, there exists a $\varepsilon$-expander graph and a constanct $c>0$ such that for each vertex $v$ and each radius $d$, for all sufficiently large $n$ we have that [...] $\endgroup$ – Peter Heinig Sep 25 '17 at 16:48
  • $\begingroup$ [...] the (to use the formulation in the proposal) "the number of vertices at most $d$ steps away from" $v$ is at least $c^d$ (I simplified-away the min-formulation in loc.cit.), roughly speaking (to make contact with the proposal), is $\Omega(c^d)$. Now the question is, of course, what this tells us about "dimension". There is no answer to this because the OP did not define "dimension". I would think that expanders should be considered 'intuitively high-dimensional'. $\endgroup$ – Peter Heinig Sep 25 '17 at 16:54
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ It seems advisable to change "The distinguishing feature" into "An essential feature", or even weaker, "A noteworthy property". While I don't know how to disprove the current "The distinguishing [...]", I also cannot make any precise sense of it. What you point out is certainly worth pointing out, yet the current formulation seems untenably strong. It seems clear, almost too clear to make writing it out in detail seem worthwhile, that the 'preimage over the $\Omega(d^2)$-growth-class is populated by many graphs which look nowhere near a discretization of a torus; more precisely [...] $\endgroup$ – Peter Heinig Sep 25 '17 at 14:20
  • $\begingroup$ [...] it seems clear that said 'preimage' of the classification-function you propose is populated by many graphs with do not have genus equal to 1(=genus of the torus surface), so this (interesting) growth-condition you propose does not seem to 'capture' the global topology. $\endgroup$ – Peter Heinig Sep 25 '17 at 14:24
  • $\begingroup$ @PeterHeinig: you are right, I've changed the wording to be weaker. I don't think that genus has a lot to do with dimension since a) it is innately tied with 2-dimensional manifolds, hence doesn't really differentiate dimensions, and b) it is not robust against small changes (e.g. add/delete a few edge), hence does not exactly qualify as a global/coarse measure. $\endgroup$ – Mikhail Tikhomirov Sep 25 '17 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.