6 ms·

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

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?

civilized 5y ago
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 5y ago
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 5y ago
  Ah yes all clear now :)
thomasahle 5y ago
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 5y ago
  Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
  - nawgz 5y ago
    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 5y ago
      Being a https://en.wikipedia.org/wiki/Perfect_graph 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)
      - deleted 5y ago
        [deleted]
    - thaumasiotes 5y ago
      > 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 https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.
  - darig 5y ago
  - thomasahle 5y ago
    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.
- 5y ago
da39a3ee 5y ago
If you think something is absurdly obvious you usually need to re-read what you've read.
- thaumasiotes 5y ago
  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.
  - thehappypm 5y ago
    Obligatory xkcd: https://xkcd.com/2042/ https://xkcd.com/2042/
    - thaumasiotes 5y ago
      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 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 5y ago
        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."
photochemsyn 5y ago
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 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-transitions-achlioptas-naor-peres.pdf 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 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?
- 5y ago
gspr 5y ago
> 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 5y ago
It's not about _can produce_ as much as will it and when which is now an open path for further discovery.

civilized 5y ago

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 5y ago

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 5y ago
Ah yes all clear now :)

thomasahle 5y ago

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 5y ago
Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
- nawgz 5y ago
  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 5y ago
    Being a https://en.wikipedia.org/wiki/Perfect_graph 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)
    - deleted 5y ago
      [deleted]
  - thaumasiotes 5y ago
    > 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 https://en.wikipedia.org/wiki/Braess%27s_paradox is very famous.
- darig 5y ago
- thomasahle 5y ago
  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.
5y ago

da39a3ee 5y ago

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

thaumasiotes 5y ago
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.
- thehappypm 5y ago
  Obligatory xkcd: https://xkcd.com/2042/ https://xkcd.com/2042/
  - thaumasiotes 5y ago
    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 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 5y ago
      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."

photochemsyn 5y ago

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 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-transitions-achlioptas-naor-peres.pdf 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 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?

5y ago

gspr 5y ago

> 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 5y ago

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