Live data from Hacker News

Elegant six-page proof reveals the emergence of random structure

quantamagazine.org

171–178 of 178 posts

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

#171
post #143
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.

When you say R, are you referring to R_0? Because R_0 is not a mathematical predictor of percolation.

I think there's lots of ways to formulate this to see how it's percolation. I'm not a percolation expert though so please call me out if you are, and I'm wrong:

To sketch here:

Consider R the reproductive number of a disease (or R_e, the effective reproductive number, to be specific). This depends on both the inherent contagiousness of the disease, but also on the behavior of the population. If people choose to have fewer contacts (or bars are closed) then R decreases.

Let's say covid is spreading. We ask people to limit their contacts, and see if this stops spread.

We can think of this as trying to remove edges from the contact graph that the disease spreads on.

The contact graph becoming connected or unconnected as we remove edges is clearly percolation.

(Subject to some modeling assumptions about edges being removed at random, but these assumptions are common to both Erdos renyi graph models and SIR style compartmental models).

Make sense?

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

#172
post #129

Earlier quoted context omitted.

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.

Nah, it just suggests that some of the article is superfluous, which I stand by.

Like I said a comment or two up, its a good article, but doesn't contain enough of the meat.

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

#173
post #165

> To make a random graph, take a biased coin — one that lands on heads with a probability of 1%, or 30%, or any other percentage between zero and 100 — and flip it Nooooo!!!! This is impossible. You can bias dice but not coin to flip.

Actually, you can if you bend the coin!

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

#174
post #71

Earlier quoted context omitted.

From the link: "Jinyoung is a first-generation college graduate, and after seven years as a secondary school teacher in South Korea, she went on to earn a mathematics Ph.D. from Rutgers University. Jinyoung’s story demonstrates the importance of role models at all levels of one’s education and the fact that it is never too late to begin anew."

And yet people will shit on DEI efforts. Incorporating more folks into the scientific endeavor helps combat things like stagnation in science precisely because it reduces academic incest.

That was not the topic of OP's post or this really.

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

#175

Earlier quoted context omitted.

If you think something is absurdly obvious you usually need to re-read what you've read.

No. It's not that rare for absurdly obvious things to get published to great fanfare. I'm still bitter about "De Morgan's Laws". There are two of them: 1. If two things are not both true, then one or more of them is false. 2. If neither of two things is true, then both of them are false. Of course this is obvious to everyone. Writing it down did not merit having it named after yourself. I guarantee many other people…

True, and there are lots of these (Bayes's theorem, Bresenham's line drawing algorithm, Dijkstra's shortest path algorithm all spring to mind). But I kind of assume that it's because it's useful to have a name for De Morgan's Laws and these others (so it stuck as a good meme in the original meaning of "meme"), rather than because we're all so impressed with this amazing result.

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

#176
post #128

Earlier quoted context omitted.

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 aft…

> 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. A Hamiltonian cycle is a simple cycle (no repeated vertices or edges) that contains every vertex of the graph. If a graph G has a Hamiltonian cycle, then adding more edges to G will not make that cycle go away; it will still be there. So the propert…

> Consider the complete graph on n vertices; there are roughly n-factorial-many Hamiltonian cycles. Any permutation of the vertices corresponds to one such cycle. Different permutations can correspond to the same cycle, so the number is not exactly n-factorial.

Isn't it just (n-1)!/2 as each cycle can be cyclically permuted (n possibilities) and (for n>=3) also be reversed? (Cases n=2 and n=1 have only one cycle.)

(That wasn't the point you were trying to get to, I know. I'm just thinking about the precise number.)

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

#177
post #74

A nice 'visual' illustration of the threshold is found in Percolation theory https://en.wikipedia.org/wiki/Percolation_theory where if you have an infinite grid of square rooms with either a wall or a door between each pair of rooms, that there is shift about what is connected when the percentage of door gets just over 50% as is visualized in this animation: https://en.wikipedia.org/wiki/Percolation_theory#/media/Fil…

I recommend everyone interested in percolation theory to also check https://meltingasphalt.com/interactive/going-critical/ and play with critical thresholds interactively!

Thank you!

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

#178

Can someone explain to my why proving random graphing can produce known shapes is important? Because this seems absurdly obvious to any layman. Why is this a complex proof? I’m guessing it’s more that they proved the thresholds for these shapes being formed more than why?

This is quite the rabbit hole but according to some background it links to a number of interesting problems, for example phase transitions in spin-glasses in physics. The wiki page on spin glasses is a good place to start, perhaps. Here's more on background: http://assets.press.princeton.edu/chapters/i9917.pdf "These are all examples of what are called combinatorial optimization problems, which typically, though not…

Thank you!
Post reply on HN