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.
https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.
Something that definitely won't work: The parity of the number of edges.
Still, it's pretty general.
> 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?
In general what I am familiar with is 'percolation theory'.
[1] https://en.wikipedia.org/wiki/Kolmogorov%27s_zero%E2%80%93on...
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.
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?
“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.
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).
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.
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.")
"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."
The title of this paper is not misleading at all. They basically just reinvented Riemann sum in 1994.
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
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).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