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

71–80 of 178 posts

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

#71

Post by urthor »

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…

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

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

#72

Post by raverbashing »

thaumasiotes wrote: post #34
da39a3ee wrote: post #23

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…

Whle these are "consequences" of DeMorgan's laws, they are written in the logical predicate format

And you can bet a lot of node developers will get tripped up by those if they need to simplfy or rewrite an if statement

It's "obvious" but not so much (especially for the time), and shows the importance of publishing (formalizing and adding your name) to things that might be obvious but maybe not

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

#73

Post by limoce »

tromp wrote: post #65
thomasahle wrote: post #7

Earlier quoted context omitted.

The interesting thing a out graph properties (like the emergence of connectivity, giant components, Hamiltonian paths etc.) is that they happen as "phase transitions". A classic example is cuckoo hashing: You want to know how many edges the random graph of hashes can have before it contains a cycle, since that's when you need to rehash into a larger table. You might expect that this number is "pretty random" in that…

This is exactly what the Cuckoo Cycle [1] family of graph-theory Proof-of-Work systems gets its name from. The puzzle instances are pseudo-random graphs in which edges are defined by the siphash24 hash function, and the solutions are cycles of length L, which have a chance of about 1/L of occurring. [1] https://github.com/tromp/cuckoo

Cuckoo hash must be a great example. I was interested in the problem solved by this paper solely because I learnt the analysis of time complexity of cuckoo hash just a few months ago.

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

#74

Post by fjfaase »

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/File...

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

#75

Post by [deleted] »

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.

[deleted]

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

#76

Post by m12k »

The article says the Kahn-Kalai conjecture also holds for hypergraphs - IIRC hypergraphs are the foundation of the Wolfram Physics project, meaning this result is likely to have implications for the emergence of patterns within the models they are working on.

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

#77

Post by rocqua »

thaumasiotes wrote: post #28
thomasahle wrote: post #7

Earlier quoted context omitted.

The interesting thing a out graph properties (like the emergence of connectivity, giant components, Hamiltonian paths etc.) is that they happen as "phase transitions". A classic example is cuckoo hashing: You want to know how many edges the random graph of hashes can have before it contains a cycle, since that's when you need to rehash into a larger table. You might expect that this number is "pretty random" in that…

> However it turns out that it very predictably happens exactly when the graph gets to a certain size. In the same way as 1000 coin flips very predictably have 450-550 heads. > What's so cool about the theorem is thst it proves _any_ property you can think of has _some_ sudden threshold like that. ...like what? The example you give, of the number of heads yielded from 1000 coin flips, doesn't have a sudden threshold…

The cases I know tend to be about infinite systems, where you have a critical probability below which the chance of some property is exactly 0. Very often, you get that above that probability the chance is exactly 1 (because of [1]).

In general what I am familiar with is 'percolation theory'.

[1] https://en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93on...

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

#78

Post by ineptech »

Pakaran wrote: post #59
ineptech wrote: post #40

I'm trying to visualize this. I go to Wolfram Alpha and type "chance of getting 504 heads in 1000 coin flips" and see the answer is about 1/40, and when I change 504 to 505 I see the odds are about 1/41 - only slightly worse. Then I check the differences between 524 and 525 and I see that the odds are decreasing much more sharply (1/400, 1/459). The little graph they helpfully provided shows what's happening: I've mo…

The effect you're seeing on the coin flip is best understood by seeing that each coin flip is independent, and in no way connected to the past. So, the odds are based on a fair 50/50 per flip, which leaves you with a simple 2^n sample space of one of each binary combination for n flips. The math for that works out easily, and can be plotted. The emergence of random structure in graphs, however, is different. The chan…

Eh, the coins weren't important, that's just an easy thing for me to visualize. If one graphs that emergence -if one graphs the number of nodes in a graph against the chance of finding some structure in a graph of that size - I had imagined one would see a smooth curve like one half of a binomial distribution curve. It sounds like you're saying the graph would look discontinuous?

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

#79

Post by WithinReason »

thetwentyone wrote: post #5

I wish Quanta was a print publication I could subscribe to. Definitely the types of articles I'd like to sit down and read not on a computer.

This is what an e-reader and Pocket in Firefox is for! Transferring an article to your e-reader in a single click.

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

#80

Post by dr_dshiv »

Reminds me of the Pythagorean perspective that there are basic harmonies (wholenesses) in math itself-- and due to these harmonies in math (arithmetic, geometric, etc), harmonies manifest in the cosmos.

So, the question might be: does this finding have any implications for physical phenomena?

Post reply on HN