Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New proof shows when structure must emerge in graphs

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 26 posts

Re: New proof shows when structure must emerge in graphs

#11

Post by pointedset »

somewhereoutth wrote: post #9
pointedset wrote: post #8

Earlier quoted context omitted.

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.

Note that for this property, you want edges to be reasonably close, but you also need to say that vertices are reasonably far apart: otherwise you could always get a "less tangled" graph by just shrinking it until it's too small to see.

Re: New proof shows when structure must emerge in graphs

#13

Post by dellamonica »

It is quite nice see that our [D-V.Rödl] bound on Thomassen's conjecture stood for over a decade, but I always felt that it would be improved to at least what Janzer and Sudakov now show.

In fact, in our paper we show the log(log(Delta)) bound assuming that G is C4-free, now you can get this (and much more) without assuming structure on G. Fantastic!

Re: New proof shows when structure must emerge in graphs

#16

Post by jacksnipe »

wiz21c wrote: post #15

As an engineer, I know a bit about graph stuff that allows me to solve real life problem. But with this new result, what kind of practical problem can be solved, or helped to solve ?

Nothing in the short term, but the techniques developed may help advance graph theory in the medium to long term. Pure math has a really long track record of delivering useful developments this way.

Re: New proof shows when structure must emerge in graphs

#18

Post by dellamonica »

layer8 wrote: post #17

> it has a large number of immediate consequences It would have been nice to mention a couple.

Basically, everything that a regular graph is known to contain will also be present in this broad class of graphs (by simple inclusion).

This is enough to establish some results like Thomassen's, that is, containing a sub-graph of minimum degree >= \delta and "girth" >= g (where you need the degree of the regular graph to be large enough in terms of \delta and g).

*girth of a graph is the length of the smallest cycle (a triangle is a cycle of length 3).

Re: New proof shows when structure must emerge in graphs

#19

Post by politician »

klysm wrote: post #10
tromp wrote: post #2

Appearance 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?

All proof-of-work systems use the concept of solving a hard problem to pace the rate of growth of commits to a chain.

Asking whether an approach has less power consumption than another approach misses the point: all PoW systems maximize energy expenditure to maintain the security guarantees of the chain.

Neither does this one have ASIC resistance which means that capital-intensive fabs can be set up to produce chips that perform these operations faster than general purpose CPUs. If you can run more attempts per second than the other guy, then you’ll mint more blocks over time as well.

This is a cool algorithm, and my hat’s off to the authors. However, it doesn’t make PoW green or accessible.

Re: New proof shows when structure must emerge in graphs

#20

Post by [deleted] »

somewhereoutth wrote: post #9
pointedset wrote: post #8

Earlier quoted context omitted.

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.

[deleted]
Post reply on HN