Identifying Regular and Irregular Lattices in the Graphity Model

[skippy1729]

Hello, I am an old engineer with a curiosity about some of the background independent QG models, CDT, graphity, &ct. I try to patch up the holes in my mathematical background as I go along. I am looking for some books or other references that might help with the following question about the graphity model:

Suppose I pick a specific Hamiltonian, large N number of vertices, and am able to determine a state (graph) of low or least energy. Suppose the maximum valence of any vertex is small (say in the range of 5 to 10). The adjacency matrix will be a large sparse matrix of 0's and 1's. At this point one would like to determine if the graph is a regular or irregular lattice of some low dimension (possibly with a small number of "defects") or is some high dimensional "rats nest".

My gut feeling is that any algorithm to accomplish this will have a high computational complexity. Anyone know of a book on graph theory which might shed some light on this type of problem? I live hundreds of miles from a "good" library so I would like something available online or on Amazon.

Thanks for any suggestions. Skippy

 

[skippy1729]

I found my answer. In case anyone else is interested: http://arxiv.org/abs/cs/0402028v1 "Lattice dimension of a Graph" by David Eppstein.

Skippy

 

[marcus]

Skippy, compliments on originality and gumption (an old word for initiative).
I wasn't responding because I don't know enough about Graphity to be able to comment usefully. It's possible that other people aren't familiar with it either. If you want to contribute a brief introduction to it saying what it's about it wouldn't hurt and might stimulate some interest.

 

[skippy1729]

GRAPHITY:

A family of models, with classical and quantum versions, whose goal is to select a subgraph of the fully connected graph Kn (with n vertices and n*(n-1)/2 edges) which is a discrete manifold resembling the universe. n will be finite but VERY large although their published simulations have all been "toy" models with small n. This is a "bottom up" theory as opposed to things like LQG or CDT which have the Einstein-Hilbert action built in from the start: "top down theories". The papers, to date, have been by Konopka, Markopoulou and Smolin of Perimeter Institute.

The classical Hamiltonian is built with things like powers of the adjacency matrix; Aij = 1 if there is an edge connecting vertices i and j, 0 otherwise. A two dimensional complex Hilbert space (like a qubit) is associated with each edge of Kn and the direct product of these form the state space for the quantum mechanical Hamiltonian. It is built from standard creation and annihilation operators, which, in the right combinations, can mimic graph theoretic functions like valence of a vertex, number of closed paths of length L which contain a vertex, and some simple graph transition operations. The Hamiltonians are built with a bit of speculation and "hand waving" to attempt to approximate what might be meant by energy of a graph state. The Hamiltonian is then used to build the partition function which is investigated with some simulations for small n and some order of magnitude estimates for various classes of graphs. The Java source code for their simulations
is contained in the arXiv source package of arXiv:0805.2283v2 [hep-th]; the other two significant papers are arXiv:hep-th/0611197v1 and arXiv:0801.0861v2 [hep-th]. I haven't looked at the source code yet (I don't speak Java) but plan on examining it soon.

They are looking at a high temperature phase (which might model the very early universe) which have many edges "on", is high dimensional, any two points approximately log(n) apart. The idea is that this could explain the cosmological "horizon problem" since everything is close enough to be in thermal equilibrium. After cooling a low temperature phase, expanded due to a lower degree of connectivity, would have a low dimensional manifold structure. The metric structure in all cases is based on the counting measure. The discrete structure is fundamental and any continuum limit would be a convenient approximation. Compare to CDT where the discrete simplices are the fiducial mathematical structures approximating some underlying continuum theory.

There are some speculations about how to include matter perhaps with Ising like structures or something called "string net condensation". There is a lot of work to be done before Graphity could be considered a falsifiable scientific
theory.

If I got something wrong, please let me know. I am NOT an expert on this topic. Skippy

 

[atyy]

There are some speculations about how to include matter perhaps with Ising like structures or something called "string net condensation". There is a lot of work to be done before Graphity could be considered a falsifiable scientific
theory.

A lattice bosonic model as a quantum theory of gravity
Zheng-Cheng Gu, Xiao-Gang Wen
http://arxiv.org/abs/gr-qc/0606100

I'd be curious to know what you think about Gu and Wen's paper. Wen worked on string-net condensation which he calls "noodle soup"
http://dao.mit.edu/~wen/talks/alight/index.html.

 

[skippy1729]

A lattice bosonic model as a quantum theory of gravity
Zheng-Cheng Gu, Xiao-Gang Wen
http://arxiv.org/abs/gr-qc/0606100

I'd be curious to know what you think about Gu and Wen's paper. Wen worked on string-net condensation which he calls "noodle soup"
http://dao.mit.edu/~wen/talks/alight/index.html.

Thanks for the link to the slide show. String-net condensation has been on my list of things learn about for a while now. Skippy