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

Elegant six-page proof reveals the emergence of random structure

quantamagazine.org

Post reply on HN
Print view View original

121–130 of 178 posts

Re: Elegant six-page proof reveals the emergence of random structure

#121

Post by joshocar »

scoot wrote: post #112
feral wrote: post #86

Earlier quoted context omitted.

And, to give an example we've probably all become familiar with, this this is equivalent to how a disease becomes an epidemic as the R value crosses 1.

That seems more like a truism: If on average one case leads to more than one other (R > 1), the number of cases will grow. The R number therefore appears to be nothing more than a measure of growth or decline. What am I missing?

As far as I understand it R is not a rate because it does not include time. Diseases that take on average a few days for you to pass on verses a few months will have different growth rates. For example, an STI might have an R factor of 3, but the rate is completely dependent on how often people have unprotected sex.

Re: Elegant six-page proof reveals the emergence of random structure

#122

Post by belmarca »

marai2 wrote: post #69
jchallis wrote: post #35

Jinyoung Park's Path to Math video on IAS is a really wonderful 3 minute story of how she came to study threshold behavior in random discrete structures, just like this work. Highly recommended. https://www.ias.edu/ideas/paths-math-jinyoung-park

Since we regularly get comments on HN about people wanting to study math in some capacity and about the challenges in doing so - I thought this was a really quote from this video: Jinyoung (after having been a secondary school Math teacher for 7 years): "... there was a big obstacle in studying mathematics or pursuing my career in mathematics, which was me, myself. Because I just couldn't stop thinking that oh I'm to…

I am back in graduate school at 31 after a few years working and I also wondered if I was too old to go back. It is definitely possible if you have the drive to do it. I can say it is both easier and harder than my first time around. My drive to succeed is much higher, my focus is sharper, but my overall energy and free time budgets are more limited (kids). I would recommend if one can and wants to do it.

Re: Elegant six-page proof reveals the emergence of random structure

#123

Post by dandare »

It always fascinated me how basically two quarks, one electron and some bosons can create so much chemical complexity.

It feels like trowing just 6 types of lego bricks into a huge bag and after a lot of random mixing obtaining whole universe of diversity.

Re: Elegant six-page proof reveals the emergence of random structure

#124

Post by zeroonetwothree »

dandare wrote: post #123

It always fascinated me how basically two quarks, one electron and some bosons can create so much chemical complexity. It feels like trowing just 6 types of lego bricks into a huge bag and after a lot of random mixing obtaining whole universe of diversity.

All the complexity of computing comes from just two bits.

(Some even argue that’s true of the universe itself)

Re: Elegant six-page proof reveals the emergence of random structure

#125

Post by leephillips »

omnicognate wrote: post #120
leephillips wrote: post #118

How can a Hamiltonian cycle be increasing? If you have one and you add an edge, then you no longer have a chain of edges that passes through every vertex exactly once, because two vertices will have two edges.

The chain of edges forming the cycle doesn't have to include all edges in the graph. There just has to exist a set of edges that form a Hamiltonian cycle. Adding further edges doesn't change that (but adding further vertices would). Edit: Put another way, it's not the Hamiltonian cycle itself that's increasing, it's the property of there existing a Hamiltonian cycle in the graph.

So the definition in the article, “a chain of edges that passes through every vertex exactly once”, is incorrect?

Re: Elegant six-page proof reveals the emergence of random structure

#126

Post by rocqua »

scoot wrote: post #112
feral wrote: post #86

Earlier quoted context omitted.

And, to give an example we've probably all become familiar with, this this is equivalent to how a disease becomes an epidemic as the R value crosses 1.

That seems more like a truism: If on average one case leads to more than one other (R > 1), the number of cases will grow. The R number therefore appears to be nothing more than a measure of growth or decline. What am I missing?

This is essentially what is happening in the percolation case as well.

Re: Elegant six-page proof reveals the emergence of random structure

#127

Post by rrajasek »

_8j50 wrote: post #101

Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past…

What they're using is the mathematical definition of randomness - an event whose outcomes cannot be determined prior to its occurence. The assumption is that it's physically impossible to predict with certainty what the true outcome is.

In many cases, what you're describing applies - there are many real world phenomena for which we have very limited information or are too complicated to model exactly. Probability theory is really useful in these situations. Why probability theory is useful is because even unpredictable events have some high level patterns that we can discover.

In the case of the article, they're interested in understanding properties of random graphs. Random graphs are useful because they're useful models of real life graphs (such as for social media websites). This is because the real life graph is constructed in a way that appears "random" (such as to whoever maintains the social media site). A lot of graph properties are proxies for real life social behavior - triangles indicate close knit groups, cycles indicate broad friend circles. If you can estimate some of these properties in a random graph, you can do the same for real life graphs. For e.g. Facebook might be interested in identifying close-knit friend circles to identify potential users who may be friends or recommend groups that users can join based on who their friends are. It will also give them sensible estimates on how many people know each other personally, how many friend circles exist and so on.

However, there are certain real life processes which are considered to be 'truly random' - quantum tunnelling, radioactive decay. It's physically impossible (regardless of what technology we can develop) to predict if an electron will tunnel through a barrier, or how long it takes for an uranium atom to decay. However, there are patterns to this randomness such as the probability that the particle tunnels and the half life for radioactive decay. These are macroscopic descriptions of random phenomena.

EDIT: added more relevant information about random graphs

Re: Elegant six-page proof reveals the emergence of random structure

#128

Post by scoot »

yshklarov wrote: post #41
plaguepilled wrote: post #27

Here's a direct link to the preprint if you want to skip the fluff: https://arxiv.org/abs/2203.17207

Actually, the "fluff" in this case is outstanding. The paper itself doesn't provide much context, but the Quanta piece does a great job at explaining why the result is important.

It does an okay job, but there are still a lot of unanswered questions, or assumed knowledge for a lay person:

> Mathematicians want to know when such a graph is likely to have some sort of interesting structure.

Why?

> a Hamiltonian cycle, a chain of edges that passes through every vertex exactly once > adding more edges to a graph that already contains the property will not destroy the property.

Adding one edge after the exact number of edges required to create a Hamiltonian cycle (number of edges equal to number of vertices) would appear to break the property.

> mathematicians often rely on an easier computation, one that provides a minimum possible value, or lower bound, for the threshold [of probability]

How can there be a lower bound other than zero? However small the possibility, surely given an infinite number of cases, there are infinite possibilities of a particular structure being created.

> The sunflower conjecture considers whether collections of sets can be constructed in ways that resemble the petals of a sunflower.

What does this mean?

> If Hamiltonian cycles are “spread out” nicely, that means that not too many cycles contain the same edge or subset of edges.

This seems to suggest multiple Hamiltonian cycles in a graph, contradicting the earlier definition that every vertex must be connected. I guess they meant every vertex in any particular Hamiltonian cycle.

And so on...

Re: Elegant six-page proof reveals the emergence of random structure

#129

Post by scoot »

plaguepilled wrote: post #44
yshklarov wrote: post #41

Earlier quoted context omitted.

Actually, the "fluff" in this case is outstanding. The paper itself doesn't provide much context, but the Quanta piece does a great job at explaining why the result is important.

I agree its a pleasant read, but like other Quanta articles, it spends too long on the journey and not enough time on the precise details for my liking. There are few symbolic expressions to be found. Others agree, which is why I shared the link. Plus, calling it 'fluff' is surely the mildest of sassy descriptions, no?

> calling it 'fluff' is surely the mildest of sassy descriptions, no?

On the contrary, "fluff" suggests that the piece has nothing to offer outside of the source material.

Re: Elegant six-page proof reveals the emergence of random structure

#130

Post by nsane »

rurban wrote: post #102

As I already commented in the first submission of this article: Now that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh. This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements wi…

Isn't the proof for Hamiltonian cycles? From what I could understand from your link to CHM92, it only requires a cyclic graph to stop, which isn't necessarily supposed to touch all vertices. Is that right?
Post reply on HN