Timeline for Can we define an isomorphism invariant to measure "dimension" of an undirected simple graph?
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 14, 2017 at 20:03 | vote | accept | Lwins | ||
| Sep 26, 2017 at 9:16 | comment | added | Mikhail Tikhomirov | A simpler example of "super-dimensional" graphs are trees, since their ball volume grows exponentially with $d$, which is not observed in any finite-dimensional space or manifold. | |
| Sep 25, 2017 at 16:54 | comment | added | Peter Heinig | [...] 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'. | |
| Sep 25, 2017 at 16:48 | comment | added | Peter Heinig | 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 [...] | |
| Sep 25, 2017 at 15:38 | comment | added | Mikhail Tikhomirov | 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". | |
| Sep 25, 2017 at 14:50 | history | edited | Lwins | CC BY-SA 3.0 |
added 331 characters in body
|
| Sep 25, 2017 at 14:36 | comment | added | Lwins | 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. | |
| Sep 25, 2017 at 14:29 | answer | added | Peter Heinig | timeline score: 4 | |
| Sep 25, 2017 at 14:08 | comment | added | Peter Heinig | 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. | |
| Sep 25, 2017 at 14:05 | history | edited | Peter Heinig | CC BY-SA 3.0 |
Corrected title. Light stylistic and grammatical improvements. The 'cycle-or-circuit-decision' made in favor of the convention in Bondy's Handbook-article and Zhang's "Circuit Double Covers of Graphs" (LMS LNS 399) Corrected 'malapropisms' "characteristic" and "ring". Style of question respected.
|
| Sep 25, 2017 at 13:35 | answer | added | Mikhail Tikhomirov | timeline score: 3 | |
| Sep 25, 2017 at 13:26 | history | asked | Lwins | CC BY-SA 3.0 |