New proof shows when structure must emerge in graphs | Hacker News Reader

New proof shows when structure must emerge in graphs

quantamagazine.org

75 pointsOrderOfChaos24 comments

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

The world needs less of proof of work, as it is synonymous with proof of burning energy.

Agreed, but note that the power used on cuckoo cycle is less than 1 windmill can provide...

As long as we get energy from non-renewable sources, that argument doesn't fly.

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.

For a fixed ASIC die cost, an SRAM dominated chip would indeed have a lower power limit, so the mining costs would shift somewhat from opex to capex...

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!

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.

How does this relate to the proof of the Kahn-Kalai conjecture that made news two months ago?

https://www.quantamagazine.org/elegant-six-page-proof-reveal...

I thought this was going to be about https://en.wikipedia.org/wiki/Szemer%C3%A9di_regularity_lemm...

"Limit cycles" come to mind. How you translate "cycle detection" from and to a continuous space?

I can't even understand your question.

Interesting!

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?

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

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.

You can place all n vertices within a unit sphere, with a roughly uniform distribution. Then the distance between two vertices is at most 2 and at least roughly around the cubic root of 4π/3n (sphere volume divided by number of vertices). So the maximum factor between edge lengths in that construction is proportional to the cubic root of n. I would suspect that it’s possible to construct graphs where that factor cannot be significantly improved upon.

Yes, N-dimensional planar graphs (better term that 'untangled'!).

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

Reply on news.ycombinator.com