[tsunamifury]

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?

[thomasahle]

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 you sometimes get a cycle with few edges or sometimes have many edges but no cycle. 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.

[layer8]

Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?

[nawgz]

It seems to me most graph problems that people care about are monotonic under adding edges. Actually, I can't think of a single problem in graph theory I've done where that wouldn't hold.

[cevi]

Being a https://en.wikipedia.org/wiki/Perfect_graph is not monotonic under adding edges, and it's certainly an interesting property for a graph to have! (But yes, most interesting properties are monotonic under adding edges)

[thaumasiotes]

> It seems to me most graph problems that people care about are monotonic under adding edges. Actually, I can't think of a single problem in graph theory I've done where that wouldn't hold.

https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.

[thomasahle]

You are right! Luckily that's the definition of a graph property .

Something that definitely won't work: The parity of the number of edges.

Still, it's pretty general.

[thaumasiotes]

> 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 at any point. What do you mean by a sudden threshold?

[thomasahle]

You are right. We have to define the notion of sudden. It works like this: As n goes to infinity you have 100% chance of 49% heads or more, but 0% chance of 51% or more.

[Cerium]

In the coin flip scenario, the intrinsic properties of a coin result in a threshold of 50% which above a certain scale, is very "sharp" or sudden in the transition. Compare this to a hash table or queuing theory, where a certain amount of capacity works well up to a certain point, then it falls apart. If you can design a random test which will display that property, then you can determine it before the fact without having a way to directly calculate that property, like we do for coin tosses.

[rocqua]

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

[tromp]

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

[limoce]

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.

[edflsafoiewq]

How do you make the theorem talk about random number sequences? What should the finite set X be?

[photochemsyn]

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 always, arise from a branch of mathematics called graph theory...What have spin glasses to do with all this? As it turns out, quite a lot. Investigations into spin glasses have turned up a number of surprising features, one of which is that the problem of finding low-energy states of spin glasses is just another one of these kinds of problems. This led directly from studies of spin glasses to the creation of new algorithms for solving the TSP [Traveling Salesman] and other combinatorial optimization problems."

The first reference in the original Kahn-Kalai “expectation threshold” conjecture (as linked in the article) is this 2005 Nature paper, "Rigorous location of phase transitions in hard optimization problems"

https://www.cs.cornell.edu/selman/papers/pdf/05.nature.phase...

> "Constraint satisfaction problems are at the heart of statistical physics, information theory and computer science. Typically, they involve a large set of variables, each taking values in a small domain, such as {0, 1}, and a collection of constraints, each binding a few of the variables by forbidding some of their possible joint values. Examples include spin-glasses in statistical physics, error-correcting codes in information theory, and satisfiability and graph colouring in computer science. Given a collection of constraints, a fundamental scientific question is how many of them can be satisfied simultaneously."

So... the article notes "each property has what’s called a threshold: a probability at which the structure emerges, often very abruptly."

Here's a short video of a sudden phase transition in supercooled water, which is sort of comparable to a phase transition in a spin glass, or say, the transition from amorphous to crystalline silicon. These things happen at sharp thresholds but have defied first-principles calculation as far as I know about this (which isn't so much, but seems to agree with your latter question re importance):

https://www.youtube.com/watch?v=PM9nwYF1uR4

Perhaps then as a result of this work, your theoretical condensed matter physicists now have new proven mathematical tools to understand things like this?

[tsunamifury]

Thank you!

[civilized]

Yes, this is all about knowing precisely when the properties are going to emerge. How many edges are needed for the Hamiltonian cycle to be present (with high probability).

[ergonaught]

From article, “The conjecture pertains to far more than random graphs. If true, it holds for random sequences of numbers, for generalizations of graphs called hypergraphs, and for even broader types of systems.”

“Obvious to a layman” is also frequently not at all related to proof, particularly in a mathematical sense.

Your summary of what they’ve proven is off, as well.

[tsunamifury]

Ah yes all clear now :)

[gspr]

> Because this seems absurdly obvious to any layman.

That something seems obvious does not suffice for mathematics. It needs to be proven.

> Why is this a complex proof?

Because no one has come up with a simpler proof. (Although this proof is in fact not very complex, as far as modern mathematical proofs go).

[Keyframe]

It's not about _can produce_ as much as will it and when which is now an open path for further discovery.

[da39a3ee]

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

[thaumasiotes]

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 had also written it down earlier.

[filoleg]

A great and hilarious example of that is this heavily cited paper titled "A mathematical model for the determination of total area under glucose tolerance and other metabolic curves."[0]

The title of this paper is not misleading at all. They basically just reinvented Riemann sum in 1994.

0. https://pubmed.ncbi.nlm.nih.gov/8137688/

[raverbashing]

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

[vitus]

Don't forget the celebrated Bayes theorem that falls directly out of the definition of conditional probability P(A|B) = P(A & B) / P(B).

If you had to squint at it and turn that into P(B|A) = P(A & B) / P(A), you'd realize that you can simply multiply the top and bottom by P(A), then pull out the remaining P(A)/P(B).

       P(A & B) / P(B)
     = P(A & B) * P(A) / (P(A) * P(B))
     = P(A & B) / P(A) * P(A) / P(B)
     = P(B | A) * P(A) / P(B).

[cultureswitch]

Interestingly, both rules are rejected in so-called "intuitionist" math. They introduce a third state any proposition can be in, as long as it hasn't been proven true or false (using other axioms). The math that derives from that is pretty nutty, like most things spawned after Godel numbering was discovered.

[chrispine]

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.

[lupire]

Knowing that true things are obviously true is easy. The difference between naive and professional mathematician is the ability to be precise enough to avoid knowing that false things are "obviously true".

To wit, what you stated is not De Morgan's law.

> De Morgan is given credit for stating the laws in the terms of modern formal logic, and incorporating them into the language of logic

[thehappypm]

Obligatory xkcd: https://xkcd.com/2042/

[thaumasiotes]

The art museum visitor would be unambiguously correct in the case of De Morgan's laws. Rolle's Theorem depends on some fairly tricky setup work.

But for an even more obvious theorem that was actually difficult to prove (Rolle's theorem isn't), see https://en.wikipedia.org/wiki/Jordan_curve_theorem

("Any path which begins in the interior of a closed curve, and ends in the exterior of the same curve, must cross the curve at some point.")

[yesenadam]

From that link:

"The first formal proof of the Jordan curve theorem was created by Hales in the HOL Light system, in January 2005, and contained about 60,000 lines. Another rigorous 6,500-line formal proof was produced in 2005 by an international team of mathematicians using the Mizar system. Both the Mizar and the HOL Light proof rely on libraries of previously proved theorems, so these two sizes are not comparable."