New proof shows when structure must emerge in graphs
quantamagazine.org
New proof shows when structure must emerge in graphs
1–10 of 26 posts
Re: New proof shows when structure must emerge in graphs
#2Appearance of fixed length cycles in random graphs makes a nice Proof-of-Work puzzle, that takes lots of SRAM to solve efficiently [1], while remaining instantly verifiable.
Re: New proof shows when structure must emerge in graphs
#3I thought this was going to be about https://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemm...
Re: New proof shows when structure must emerge in graphs
#4Interesting!
I have been wondering how to understand what graphs appear 'tangled' in 2D, that then appear 'untangled' in 3D (e.g. using force layout) - specifically, how large a class of graphs that is, and what kind of constraints might determine that property. Presumably sub-structure is key.
Any insights gratefully received!
Re: New proof shows when structure must emerge in graphs
#5Interesting! I have been wondering how to understand what graphs appear 'tangled' in 2D, that then appear 'untangled' in 3D (e.g. using force layout) - specifically, how large a class of graphs that is, and what kind of constraints might determine that property. Presumably sub-structure is key. Any insights gratefully received!
You mean like the set of 'N dimensional planar graphs'? I'm sure there's a word for it but I don't know it
Re: New proof shows when structure must emerge in graphs
#6Interesting! I have been wondering how to understand what graphs appear 'tangled' in 2D, that then appear 'untangled' in 3D (e.g. using force layout) - specifically, how large a class of graphs that is, and what kind of constraints might determine that property. Presumably sub-structure is key. Any insights gratefully received!
You mean like the set of 'N dimensional planar graphs'? I'm sure there's a word for it but I don't know it
Yes, N-dimensional planar graphs (better term that 'untangled'!).
Re: New proof shows when structure must emerge in graphs
#7Interesting! I have been wondering how to understand what graphs appear 'tangled' in 2D, that then appear 'untangled' in 3D (e.g. using force layout) - specifically, how large a class of graphs that is, and what kind of constraints might determine that property. Presumably sub-structure is key. Any insights gratefully received!
You mean like the set of 'N dimensional planar graphs'? I'm sure there's a word for it but I don't know it
If a planar graph is what is meant by an untangled graph in R2, then isn't any finite graph untangled embedded in R3?
Re: New proof shows when structure must emerge in graphs
#8Earlier quoted context omitted.
You mean like the set of 'N dimensional planar graphs'? I'm sure there's a word for it but I don't know it
If a planar graph is what is meant by an untangled graph in R2, then isn't any finite graph untangled embedded in R3?
Yes, if "untangled" means "no edge crossings", then 3 dimensions is enough for any graph to be untangled. As a proof, you can put the vertices at coordinates (0, 0, 0), (1, 1, 1), (2, 4, 8), (3, 9, 27), ..., (n, n^2, n^3), and then no two edges will cross.
A different definition of "untangled" might be that all edges have roughly the same length (which could be formally defined in lots of different ways), in which case more dimensions might be helpful for bigger graphs. (With this definition, every graph with n vertices can be untangled in n-1 dimensions, and the complete graph shows that this is a tight bound).
Another generalization is to look at 2-dimensional surfaces of higher genus rather than spaces of higher dimension: something like a donut or a multi-handled donut. There's a whole bunch of research already done on that topic, search for "graph embeddings".
Re: New proof shows when structure must emerge in graphs
#9Earlier quoted context omitted.
If a planar graph is what is meant by an untangled graph in R2, then isn't any finite graph untangled embedded in R3?
Yes, if "untangled" means "no edge crossings", then 3 dimensions is enough for any graph to be untangled. As a proof, you can put the vertices at coordinates (0, 0, 0), (1, 1, 1), (2, 4, 8), (3, 9, 27), ..., (n, n^2, n^3), and then no two edges will cross. A different definition of "untangled" might be that all edges have roughly the same length (which could be formally defined in lots of different ways), in which ca…
Ah indeed. I was meaning 'untangled' in the looser sense of 'can be spread out over 3D space with most/all connected points reasonably close to each other'.
Seems like this is a topological property, that the 'neighbourhoods' defined by the connections 'tessellate' in some sense.
Re: New proof shows when structure must emerge in graphs
#10Appearance of fixed length cycles in random graphs makes a nice Proof-of-Work puzzle, that takes lots of SRAM to solve efficiently [1], while remaining instantly verifiable. [1] https://github.com/tromp/cuckoo
Does it being memory bound make it have less power consumption than CPU bound tasks?