19 ms·

Elegant six-page proof reveals the emergence of random structure

589 points by davidvarela_us 4y ago

tsunamifury 4y ago
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 4y 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 4y 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 4y ago
    Ah yes all clear now :)
- thomasahle 4y 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 4y ago
    Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
    - nawgz 4y 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 4y 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 4y ago
        [deleted]
      - thaumasiotes 4y 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 4y ago
    - thomasahle 4y 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.
  - 4y ago
- da39a3ee 4y ago
  If you think something is absurdly obvious you usually need to re-read what you've read.
  - thaumasiotes 4y 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 4y ago
      Obligatory xkcd: https://xkcd.com/2042/ https://xkcd.com/2042/
      - thaumasiotes 4y 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 4y 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 4y 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?
  - 4y ago
- gspr 4y 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 4y ago
  It's not about _can produce_ as much as will it and when which is now an open path for further discovery.
thetwentyone 4y ago
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.
- greggsy 4y ago
  I feel like there’s a market for a publishing service that could partner with popular blogs and websites. They could either allow articles to be selected by the user or the partner site, which could then be auto-paginated and printed being being posted to the subscriber. Hell, sell a service where you will curate articles based on used interests. Add some relevant Twitter threads for letters to the editor. Partner sites could also benefit from some increased subscriber revenue, and ads could actually be relevant again (remember when Scientific American advertisements were kind of cool and industry related?). Call the prototype deadtreepress.io or something. (I recognise the environmental implications, but I think paper and postage can be sustainable in some regions. Maybe you could integrate offsets into the price?)
  - comboy 4y ago
    I feel I would want that too even though I got used to reading on screens. Maybe it could be pdf, I think it may be about some finite amount of content to consume. I guess for me some every 3-12 months ebook with articles that are still relevant and will likely stay relevant for at least a few years would be awesome.
  - dmix 4y ago
    This is a great idea. You could draw in a casual nerdy audience willing to pay a reasonable price for access to high quality OpenAI style explainer pages with access to the raw data and papers.
  - swatcoder 4y ago
    It’s a fine idea, but ignores the importance of typesetting and design for print. I’m sure plenty of people would want something like this regardless, but the product would usually look much less polished than people expect to see in printed and bound materials and that would reflect on the authors/editors. Authors and editors who take pride in the presentation of their work might be a hard sell.
plaguepilled 4y ago
Here's a direct link to the preprint if you want to skip the fluff: https://arxiv.org/abs/2203.17207 https://arxiv.org/abs/2203.17207
- Sniffnoy 4y ago
  Hm, they prove the existence of a K, but don't put any explicit bounds on it. Someone's going to have to proof-mine this one...
- yshklarov 4y ago
  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.
  - plaguepilled 4y ago
    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?
    - scoot 4y ago
      > 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.
      - plaguepilled 4y ago
        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.
    - jessriedel 4y ago
jchallis 4y ago
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 https://www.ias.edu/ideas/paths-math-jinyoung-park
- StopDarkPattern 4y ago
  - CuriousCosmic 4y ago
    Jinyoung Park is literally one of the co-authors of the paper in question.
    - lol1lol 4y ago
      She was at Institute for Advanced Study at Princeton. It's -the- most elite intellectual society. The top 1% of the 1% academics have to compete for admission. If that doesn't wash away illformed biases, I don't know what can! What she accomplished is no joke!! Huge respect tbh.
- marai2 4y ago
  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 too old and I started too late or I didn't learn enough amount of mathematics in college ..." and now here she is with some world class work to her name.
  - urthor 4y ago
    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."
axiom92 4y ago
Neat comment on the arxiv (https://arxiv.org/abs/math/0603218 https://arxiv.org/abs/math/0603218): The gap between expectations and reality is studied, 7 pages (these comments are added by the submitting author).
ineptech 4y ago
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 moved from the flattish "top" of the Bernoulli distribution to the steepish "slope" of the distribution. And at larger numbers still, the differences between adjacent numbers become negligible again as I reach the flattish "trough" at the edge of the distribution. You could say that the top of the distribution has values that are all pretty similar to each other, the bottom values are also similar to each other, and sides are a region where small differences are comparatively much more important. Is this roughly what the article means when it discusses thresholds? The rather sharp transition from "both pretty likely" to "the second one is a lot less likely" to "both pretty unlikely"? And if so, how sharply would the slope of the distribution have to change to qualify as being a threshold?
- scheme271 4y ago
  I think it's slightly different. Consider this problem instead, what's the chances of two people sharing the same birthday in a group. It's (365364...*(365-n+1))/(365^n). If you plot this out, it increases exponentially. At n=23 it's about 50%. At around 60, it's a bit more than 99%. It's similar to the other problems, where a given condition can have an arbitrarily high chance of being present at surprisingly low graph sizes.
  - lupire 4y ago
    That's sigmoid (starts exponential and then smoothly changes into an asymptotically constant)
- Pakaran 4y ago
  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 chance of a specific structure, such as a cycle of some length or a spanning tree of certain dimension, can go from not particularly likely (<20%) to significantly likely (95%+) in just a single additional node. Those transition thresholds at which the percentage changes in an intuitively surprising way are the subject matter of interest here.
gardnr 4y ago
> 2 (of a scientific theory or solution to a problem) pleasingly ingenious and simple: the grand unified theory is compact and elegant in mathematical terms. A 6 page proof described as "elegant" must be incredibly dense.
- alanbernstein 4y ago
  The proof section is 3.5 pages. That's really pretty short, as far as modern math results go. I get your point, though.
  - oaiey 4y ago
    The abstract is a one liner and the intro has in the first line a formula or two. No idea if this is the tone of math papers but I call this dense :)
    - CuriousCosmic 4y ago
      Compared to some of the papers I've read recently, this is extremely elegant and succinct and doesn't just jam all the math in line by line. Comparatively one of the papers I looked at the other day was something like 100 pages long with a ~30 page proof section with very little free whitespace packed full of complex mathematics.
- mjreacher 4y ago
  As the other poster noted, for a big math result this is comparatively rather short. For a concrete example[0], a recent important result related to the Arnold conjecture is 268 pages long, with another 100 pages in appendices. [0]: https://arxiv.org/abs/2103.01507 https://arxiv.org/abs/2103.01507
- iciac 4y ago
  You might be interested in this 1 page paper by John Nash, which proves the existence of equilibria for finite N-player games (an extremely powerful result). In essence it uses a set theory result (Kakutani's fixed point theorem), and simply notes that his description of a N-player game meets the required conditions for that result to hold. http://www.sscnet.ucla.edu/polisci/faculty/chwe/austen/nash1950.pdf http://www.sscnet.ucla.edu/polisci/faculty/chwe/austen/nash1...
quickthrower2 4y ago
What level of expertise is this proof accessible to? Could a final year undergraduate understand this perhaps with a bit of help or background reading? I am talking about reading and understanding it, not necessary validating the correctness.
- M1rco 4y ago
  I think so. To be honest not 100% sure but it seems you would need a bit probability theory + understanding what graphs/hypergraphs are. So my first impression is, it is very accessible, which I would also expect from an elegant proof...
- chx 4y ago
  I would say yes because I am very close to understanding it :) Although I have a math teacher degree, we didn't really learn that much higher level stuff and also it's been twenty years since I touched anything like this. Notation wise I am missing A△B and not much else. For the theorems mentioned, I am reasonably sure if I worked through https://www.ihes.fr/~duminil/publi/2017percolation.pdf https://www.ihes.fr/~duminil/publi/2017percolation.pdf I would understand this paper in question. Edit: ah! I paged through the percolation introduction and it mentions A∆B ∶= (B ∖ A) ∪ (A ∖ B) so that's the symmetric difference between A and B. And it seems the first ten pages is enough, we only need to get to the Russo theorem.
- jfoutz 4y ago
  Be bold! Any paper, any field, if you can get your hands on it, Take a half an hour and read the words. Look at the pictures, Look at the graphs. Take a break. Go for a walk, maybe get some coffee, and decide if you want to continue. This will give you a very rough survey of the terrain. Often, I'll quit right here if there's nothing for me to latch on to. Take a couple of hours, take notes about the things you don't understand - maybe take a minute here or there to look up concepts, maybe take a minute there to graph equations. Get a good night's sleep. Look at your notes and think about all the stuff you don't understand. There are plenty of things I don't get _at all_. There are also things I can latch onto. Put some serious effort into linking the equations with the words. Decide if you want to spend days or weeks really digging in and _understanding_. I find each step rewarding. I often quit early, and move on to the next shiny new thing. There's some real value in each step. I learn about things I never new existed. I certainly can't explain them, but sometimes things pop up again and again and I do get the motivation to take a deeper dive - not necessarily mastery, but at least an understanding of my depth of ignorance. Maybe watch a lecture on that topic for perspective. You never know what's going to be useful. Nurture that spark of interest. You might get nothing out of it today, but 10 years from now, you'll see some other problem and vaguely recall this is kinda like that other thing I never really got. There's definitely some opportunity cost. But if you're just farting around on reddit, an hour here and there can be really enjoyable, and possibly someday useful.
galaxyLogic 4y ago
I wonder if this has implications for evolution of life. Life is about DNA which is about a graph of nucleoids connecting to each other in specific structures. But DNA must have evolved out of random structures and random mutations. So if there's a threshold at which structures become inevitable, then DNA has a chance to be born?
- giorgioz 4y ago
  Yes I was also wondering the implications that in a system like a universe being born out of a big bang eventually life structures will appear with a certain probability.
- zeristor 4y ago
  There is the field of catalytic random networks, the gist being that DNA can encode for enzymes which greatly increase the rate of protein generation. I read a book on it by Stuart Kauffman from the Santa Fe Institute of Complexity about 20 years ago; things may well have changed since then, but the core idea was amazing. Also reminds me of rates of reaction from Physical Chemistry, how some concentrations of chemicals can have a huge impact on the overall reaction. Edit: Updated with the author’s name.
- G3rn0ti 4y ago
  > But DNA must have evolved out of random structures and random mutations Before DNA there was only RNA. DNA came later but established itself because it is much better at conserving information. There are still retro vira carrying their genetic information in the form of RNA reminiscent of that RNA era. So the course of evolution might have been like this: 1) random RNA coils slowly gained structures being able to catalyze reactions e.g. like replicating itself. 2) Replicators become catalysts for other reactions. 3) Specialized RNA molecules start entangling themselves like e.g. one of them replicating the others while another provides access to chemistry providing energy (aka "food"). 4) RNAs start encoding proteins and enzymes adding to the entanglements. 5) Membranes appear isolating the entanglements from the environment inventing cells. 6) DNAs are created from RNAs forming the modern biochemical tri-unity of DNA, RNA and proteins.
elromulous 4y ago
Direct link to the PDF: https://arxiv.org/pdf/2203.17207 https://arxiv.org/pdf/2203.17207
SubiculumCode 4y ago
- mdp2021 4y ago
  With statements like "left handed people can reason too" or "I drove a red car and nothing happened" you are implying a doubt, that the opposite could be an idea worth considering. If a prejudice has a context, that context is relevant - otherwise the idea is presented as general. [Edited for content a second time: I quoted an article I was just reading by chance, presenting data that are exemplary of another point, about the relation between generic statements and actual differences: I now remove it realizing I missed a detail in that quote that excluded the professional context.]
- rswail 4y ago
  You've stated an axiom.
deleted 4y ago
[deleted]
fjfaase 4y ago
A nice 'visual' illustration of the threshold is found in Percolation theory https://en.wikipedia.org/wiki/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:Transition_de_percolation_2.gif https://en.wikipedia.org/wiki/Percolation_theory#/media/File...
- ccbccccbbcccbb 4y ago
  I recommend everyone interested in percolation theory to also check https://meltingasphalt.com/interactive/going-critical/ https://meltingasphalt.com/interactive/going-critical/ and play with critical thresholds interactively!
  - pietroppeter 4y ago
    Great link, thanks for sharing!
  - cecilpl2 4y ago
    This was fascinating! It started with some simple simulations, but led into some very enlightening generalizations about why culture spreads more rapidly in cities than in the countryside, and why new language spreads more rapidly among adolescents.
  - spiralx 4y ago
    Thank you!
- feral 4y ago
  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.
  - scoot 4y ago
m12k 4y ago
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.
dr_dshiv 4y ago
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?
high_byte 4y ago
very interesting. I would like to see that math applied to the emergence of life. how slim were our chances? or maybe not slim at all and maybe even unavoidable?
anuvrat1 4y ago
Off Topic: Can I get some more resources like quanta, which explains new research on mainstream or obscure subjects to a layman?
- jiggawatts 4y ago
  Scientific American, or American Scientist are my go-to favourites. https://www.scientificamerican.com/ https://www.scientificamerican.com/ https://www.americanscientist.org/ https://www.americanscientist.org/
zogomoox 4y ago
So it seems this allows us to understand when phase transitions occur, I wonder if this has applications in improving high temperature superconductors.
pfdietz 4y ago
Entry at Gil Kalai's blog on this result: https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/ https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-p...
itissid 4y ago
Wasn't there also a connection between solving constraint satisfaction (k-SAT Boolean CSP examples) where the clause length to the number of clauses makes it super easy or super hard for solvers to solve for a solution? I vaguely remember this from reading literature when writing heuristic solvers for my CS grad course in AI search.
- itissid 4y ago
  To answer my own question here are some references to the problem at hand https://dl.acm.org/doi/10.1145/3491210 https://dl.acm.org/doi/10.1145/3491210
_8j50 4y ago
Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past that lead up to an event, you would not be able to find the cause of that event because it was truly random. Do they mean "unpredictable for humans with known means of predicting"? You might as well use the term "magical" or "miraculous" if you use "random".
- d--b 4y ago
  This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".
  - _8j50 4y ago
    How can you prove something that isn't real? How is randomness defined as a concept in mathematics?
    - DavidSJ 4y ago
      Randomness is usually defined in terms of a probability distribution, which is just a measure where the total mass assigned to all elements adds up to 1.
    - majkinetor 4y ago
      You can actually only prove unreal things because you impose limitations. Real things can not be proven, but only disproved.
    - siver_john 4y ago
      As long as you can clearly define your starting axioms you can mathematically prove or disprove anything. The physical example would be to just say, suppose a universe with the same properties of ours exist but where the gravitational constant is twice as large prove whether X can occur in that universe. As far as how randomness is defined I believe that might be field dependent but this is me getting out of my depth (I've only taken a few courses on combinatorics).
rurban 4y ago
As I already commented in the first submission of this article: Now that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh. This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements with Unicode. switch in C is only efficient for dense tables, but not sparse. sparse tables are linear, but could be constant. A switch in Pascal was constant, but so far GCC and llvm didn't care. gperf neither. see http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html and http://programming.sirrida.de/hashing.html#c_case_of_string http://programming.sirrida.de/hashing.html#c_case_of_string
- nsane 4y ago
  Isn't the proof for Hamiltonian cycles? From what I could understand from your link to CHM92, it only requires a cyclic graph to stop, which isn't necessarily supposed to touch all vertices. Is that right?
  - jonnycomputer 4y ago
    The Hamiltonian cycle is only a motivating example. The conjecture which was proven is much more general. https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/ https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-p...
- less_less 4y ago
  Huh, I was thinking the same thing about a related problem: compressed static maps by solving sparse matrices: https://docs.rs/compressed_map/0.1.0/compressed_map/ https://docs.rs/compressed_map/0.1.0/compressed_map/ To get a concrete bound though, you'd probably need to know what is K.
ThinkBeat 4y ago
I notice that most links on physics, astronomy and math cover pre-prints. Would it not be prudent to wait for the final version. Is all the peer reviews and "fact checking" done prior to the preprint?
- Ar-Curunir 4y ago
  For a big result like this, enough experts read the paper to catch glaring mistakes. Sort of a de facto peer review
  - mjreacher 4y ago
    Exactly, Quanta would have the experts they interview go over the paper first if they didn't already go over it before and evaluate it before making any comments. Plus arXiv papers are freely accessible ;)
- snowwrestler 4y ago
  Reporters often rely on social input to decide what to cover—when someone they trust tells them, “you should check this out.” Then there is an exploratory phase where they gather some basic facts and reach out to contacts to see if it is in fact newsworthy, and maybe to start gathering quotes to add context and fill out the story. At some point they say “this is real” and start working with a editor on a schedule to publish it. Whether a paper is on a preprint serve is not a big deal. If a lot of experts are excited about it, that’s a story anyway. And if it falls apart later due to some surprise flaw… well that is also a story!
- lupire 4y ago
  Publications don't check facts. They just check formatting and interestingness and plausibility. Peer review is totally separate, not part of publication's pseudo "peer review".
d--b 4y ago
Can anyone with a solid CS background comment on whether this relates to P!=NP at all? I mean this deals with Hamiltonian cycles (which is the focus of a well know NP hard problems). It talks about lower boundaries for randomness (which relates to the information stored in the graph). The article talks about gaps which are logarithmic. I can't quite articulate it, but somehow intuitively, it sounds like it could connect.
leephillips 4y ago
How can a Hamiltonian cycle be increasing? If you have one and you add an edge, then you no longer have a chain of edges that passes through every vertex exactly once, because two vertices will have two edges.
- omnicognate 4y ago
  The chain of edges forming the cycle doesn't have to include all edges in the graph. There just has to exist a set of edges that form a Hamiltonian cycle. Adding further edges doesn't change that (but adding further vertices would). Edit: Put another way, it's not the Hamiltonian cycle itself that's increasing, it's the property of there existing a Hamiltonian cycle in the graph.
  - leephillips 4y ago
    So the definition in the article, “a chain of edges that passes through every vertex exactly once”, is incorrect?
    - omnicognate 4y ago
      No, that's the correct definition of a Hamiltonian cycle. However, the article isn't as clear as it could be about what the "increasingness" aspect applies to. > It’s possible to think about any property, so long as it is “increasing” — that is, if adding more edges to a graph that already contains the property will not destroy the property. The "property" here isn't the Hamiltonian cycle itself, it's the property "a Hamiltonian cycle exists within this graph". This property, rather than the cycle itself, is increasing: if you add edges to a graph that contains a Hamiltonian cycle it will still contain a Hamiltonian cycle.
      - deleted 4y ago
        [deleted]
      - leephillips 4y ago
        Ah, I get it now. Thanks.
dandare 4y ago
It always fascinated me how basically two quarks, one electron and some bosons can create so much chemical complexity. It feels like trowing just 6 types of lego bricks into a huge bag and after a lot of random mixing obtaining whole universe of diversity.
- zeroonetwothree 4y ago
  All the complexity of computing comes from just two bits. (Some even argue that’s true of the universe itself)
  - dandare 4y ago
    Not true, the bits live in a super complex hardware, the don't create any complexity on their own.
  - 19h 4y ago
    Except there’s no such thing as bits on the hardware level. There’s voltages. High and low. That’s usually 5V and 0V, respectively.
    - meetups323 4y ago
      You're thinking too concretely. The hardware we know is only one tiny implementation of computation. The broader concept holds across any writeable tape of any sort, whether it uses voltages in silicon, rocks on a beach, or exists only in a person's mind, does not matter one bit -- they're all equally powerful.
bolingo007 4y ago
Yes
qwertygnu 4y ago
>The methods that would eventually lead to [new discovery] began with a breakthrough on a seemingly unrelated problem. Science, baby!
lupire 4y ago
> 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.
- yshklarov 4y ago
  Actually, you can if you bend the coin!
lupire 4y ago
> young mathematicians Is a 40 yr old mathematician "young"?
sharpener 4y ago
Maybe someone familiar with the graph theory math can help me. I don't understand why these properties aren't numerically accessible. Why is the estimation necessary? E.g. Assume N nodes, and edges E can be created at random with redundancy (picking same edge e twice just keeps the prior edge) by picking pairs of points. Assume N random edge picks are made, then the probability of e.g. a Hamiltonian cycle appearing in those N picks can be calculated. (My quick back of envelope sketch says P(H-cycle) = N! / N^N , but please consult the expert literature.) But one can also calculate the probability of a H-cycle given N+1 random picks, N+2 random picks, ... and that appears as = P(H-cycle) * (1 + extra factors that account for increases in other edges not redundantly in the H-cycle) (Again, my back of envelope sketch for N + 2 picks gives: = P(H-cycle) * ( 1 + 2/(N-1)[N - 3 - 1/N]) , but please consult the expert literature.) These probabilities would seem to tell a user that given a graph with N nodes and E edges, that if e.g. in the H-cycle case, E > N the user can get an explicit probability for the likelihood of a H-cycle being present. Are there graph properties that prevent this approach being viable?

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 4y 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 4y 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 4y ago
  Ah yes all clear now :)
thomasahle 4y 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 4y ago
  Surely not _any_ property? From the article I understood that it’s only those that are monotonic under adding edges?
  - nawgz 4y 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 4y 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 4y ago
        [deleted]
    - thaumasiotes 4y 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 4y ago
  - thomasahle 4y 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.
- 4y ago
da39a3ee 4y ago
If you think something is absurdly obvious you usually need to re-read what you've read.
- thaumasiotes 4y 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 4y ago
    Obligatory xkcd: https://xkcd.com/2042/ https://xkcd.com/2042/
    - thaumasiotes 4y 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 4y 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 4y 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?
- 4y ago
gspr 4y 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 4y ago
It's not about _can produce_ as much as will it and when which is now an open path for further discovery.

thetwentyone 4y ago

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.

greggsy 4y ago
I feel like there’s a market for a publishing service that could partner with popular blogs and websites. They could either allow articles to be selected by the user or the partner site, which could then be auto-paginated and printed being being posted to the subscriber. Hell, sell a service where you will curate articles based on used interests. Add some relevant Twitter threads for letters to the editor. Partner sites could also benefit from some increased subscriber revenue, and ads could actually be relevant again (remember when Scientific American advertisements were kind of cool and industry related?). Call the prototype deadtreepress.io or something. (I recognise the environmental implications, but I think paper and postage can be sustainable in some regions. Maybe you could integrate offsets into the price?)
- comboy 4y ago
  I feel I would want that too even though I got used to reading on screens. Maybe it could be pdf, I think it may be about some finite amount of content to consume. I guess for me some every 3-12 months ebook with articles that are still relevant and will likely stay relevant for at least a few years would be awesome.
- dmix 4y ago
  This is a great idea. You could draw in a casual nerdy audience willing to pay a reasonable price for access to high quality OpenAI style explainer pages with access to the raw data and papers.
- swatcoder 4y ago
  It’s a fine idea, but ignores the importance of typesetting and design for print. I’m sure plenty of people would want something like this regardless, but the product would usually look much less polished than people expect to see in printed and bound materials and that would reflect on the authors/editors. Authors and editors who take pride in the presentation of their work might be a hard sell.

plaguepilled 4y ago

Here's a direct link to the preprint if you want to skip the fluff: https://arxiv.org/abs/2203.17207 https://arxiv.org/abs/2203.17207

Sniffnoy 4y ago
Hm, they prove the existence of a K, but don't put any explicit bounds on it. Someone's going to have to proof-mine this one...
yshklarov 4y ago
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.
- plaguepilled 4y ago
  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?
  - scoot 4y ago
    > 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.
    - plaguepilled 4y ago
      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.
  - jessriedel 4y ago

jchallis 4y ago

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 https://www.ias.edu/ideas/paths-math-jinyoung-park

StopDarkPattern 4y ago
- CuriousCosmic 4y ago
  Jinyoung Park is literally one of the co-authors of the paper in question.
  - lol1lol 4y ago
    She was at Institute for Advanced Study at Princeton. It's -the- most elite intellectual society. The top 1% of the 1% academics have to compete for admission. If that doesn't wash away illformed biases, I don't know what can! What she accomplished is no joke!! Huge respect tbh.
marai2 4y ago
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 too old and I started too late or I didn't learn enough amount of mathematics in college ..." and now here she is with some world class work to her name.
- urthor 4y ago
  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."

axiom92 4y ago

Neat comment on the arxiv (https://arxiv.org/abs/math/0603218 https://arxiv.org/abs/math/0603218): The gap between expectations and reality is studied, 7 pages (these comments are added by the submitting author).

ineptech 4y ago

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 moved from the flattish "top" of the Bernoulli distribution to the steepish "slope" of the distribution. And at larger numbers still, the differences between adjacent numbers become negligible again as I reach the flattish "trough" at the edge of the distribution. You could say that the top of the distribution has values that are all pretty similar to each other, the bottom values are also similar to each other, and sides are a region where small differences are comparatively much more important. Is this roughly what the article means when it discusses thresholds? The rather sharp transition from "both pretty likely" to "the second one is a lot less likely" to "both pretty unlikely"? And if so, how sharply would the slope of the distribution have to change to qualify as being a threshold?

scheme271 4y ago
I think it's slightly different. Consider this problem instead, what's the chances of two people sharing the same birthday in a group. It's (365364...*(365-n+1))/(365^n). If you plot this out, it increases exponentially. At n=23 it's about 50%. At around 60, it's a bit more than 99%. It's similar to the other problems, where a given condition can have an arbitrarily high chance of being present at surprisingly low graph sizes.
- lupire 4y ago
  That's sigmoid (starts exponential and then smoothly changes into an asymptotically constant)
Pakaran 4y ago
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 chance of a specific structure, such as a cycle of some length or a spanning tree of certain dimension, can go from not particularly likely (<20%) to significantly likely (95%+) in just a single additional node. Those transition thresholds at which the percentage changes in an intuitively surprising way are the subject matter of interest here.

gardnr 4y ago

> 2 (of a scientific theory or solution to a problem) pleasingly ingenious and simple: the grand unified theory is compact and elegant in mathematical terms. A 6 page proof described as "elegant" must be incredibly dense.

alanbernstein 4y ago
The proof section is 3.5 pages. That's really pretty short, as far as modern math results go. I get your point, though.
- oaiey 4y ago
  The abstract is a one liner and the intro has in the first line a formula or two. No idea if this is the tone of math papers but I call this dense :)
  - CuriousCosmic 4y ago
    Compared to some of the papers I've read recently, this is extremely elegant and succinct and doesn't just jam all the math in line by line. Comparatively one of the papers I looked at the other day was something like 100 pages long with a ~30 page proof section with very little free whitespace packed full of complex mathematics.
mjreacher 4y ago
As the other poster noted, for a big math result this is comparatively rather short. For a concrete example[0], a recent important result related to the Arnold conjecture is 268 pages long, with another 100 pages in appendices. [0]: https://arxiv.org/abs/2103.01507 https://arxiv.org/abs/2103.01507
iciac 4y ago
You might be interested in this 1 page paper by John Nash, which proves the existence of equilibria for finite N-player games (an extremely powerful result). In essence it uses a set theory result (Kakutani's fixed point theorem), and simply notes that his description of a N-player game meets the required conditions for that result to hold. http://www.sscnet.ucla.edu/polisci/faculty/chwe/austen/nash1950.pdf http://www.sscnet.ucla.edu/polisci/faculty/chwe/austen/nash1...

quickthrower2 4y ago

What level of expertise is this proof accessible to? Could a final year undergraduate understand this perhaps with a bit of help or background reading? I am talking about reading and understanding it, not necessary validating the correctness.

M1rco 4y ago
I think so. To be honest not 100% sure but it seems you would need a bit probability theory + understanding what graphs/hypergraphs are. So my first impression is, it is very accessible, which I would also expect from an elegant proof...
chx 4y ago
I would say yes because I am very close to understanding it :) Although I have a math teacher degree, we didn't really learn that much higher level stuff and also it's been twenty years since I touched anything like this. Notation wise I am missing A△B and not much else. For the theorems mentioned, I am reasonably sure if I worked through https://www.ihes.fr/~duminil/publi/2017percolation.pdf https://www.ihes.fr/~duminil/publi/2017percolation.pdf I would understand this paper in question. Edit: ah! I paged through the percolation introduction and it mentions A∆B ∶= (B ∖ A) ∪ (A ∖ B) so that's the symmetric difference between A and B. And it seems the first ten pages is enough, we only need to get to the Russo theorem.
jfoutz 4y ago
Be bold! Any paper, any field, if you can get your hands on it, Take a half an hour and read the words. Look at the pictures, Look at the graphs. Take a break. Go for a walk, maybe get some coffee, and decide if you want to continue. This will give you a very rough survey of the terrain. Often, I'll quit right here if there's nothing for me to latch on to. Take a couple of hours, take notes about the things you don't understand - maybe take a minute here or there to look up concepts, maybe take a minute there to graph equations. Get a good night's sleep. Look at your notes and think about all the stuff you don't understand. There are plenty of things I don't get _at all_. There are also things I can latch onto. Put some serious effort into linking the equations with the words. Decide if you want to spend days or weeks really digging in and _understanding_. I find each step rewarding. I often quit early, and move on to the next shiny new thing. There's some real value in each step. I learn about things I never new existed. I certainly can't explain them, but sometimes things pop up again and again and I do get the motivation to take a deeper dive - not necessarily mastery, but at least an understanding of my depth of ignorance. Maybe watch a lecture on that topic for perspective. You never know what's going to be useful. Nurture that spark of interest. You might get nothing out of it today, but 10 years from now, you'll see some other problem and vaguely recall this is kinda like that other thing I never really got. There's definitely some opportunity cost. But if you're just farting around on reddit, an hour here and there can be really enjoyable, and possibly someday useful.

galaxyLogic 4y ago

I wonder if this has implications for evolution of life. Life is about DNA which is about a graph of nucleoids connecting to each other in specific structures. But DNA must have evolved out of random structures and random mutations. So if there's a threshold at which structures become inevitable, then DNA has a chance to be born?

giorgioz 4y ago
Yes I was also wondering the implications that in a system like a universe being born out of a big bang eventually life structures will appear with a certain probability.
zeristor 4y ago
There is the field of catalytic random networks, the gist being that DNA can encode for enzymes which greatly increase the rate of protein generation. I read a book on it by Stuart Kauffman from the Santa Fe Institute of Complexity about 20 years ago; things may well have changed since then, but the core idea was amazing. Also reminds me of rates of reaction from Physical Chemistry, how some concentrations of chemicals can have a huge impact on the overall reaction. Edit: Updated with the author’s name.
G3rn0ti 4y ago
> But DNA must have evolved out of random structures and random mutations Before DNA there was only RNA. DNA came later but established itself because it is much better at conserving information. There are still retro vira carrying their genetic information in the form of RNA reminiscent of that RNA era. So the course of evolution might have been like this: 1) random RNA coils slowly gained structures being able to catalyze reactions e.g. like replicating itself. 2) Replicators become catalysts for other reactions. 3) Specialized RNA molecules start entangling themselves like e.g. one of them replicating the others while another provides access to chemistry providing energy (aka "food"). 4) RNAs start encoding proteins and enzymes adding to the entanglements. 5) Membranes appear isolating the entanglements from the environment inventing cells. 6) DNAs are created from RNAs forming the modern biochemical tri-unity of DNA, RNA and proteins.

elromulous 4y ago

Direct link to the PDF: https://arxiv.org/pdf/2203.17207 https://arxiv.org/pdf/2203.17207

SubiculumCode 4y ago

mdp2021 4y ago
With statements like "left handed people can reason too" or "I drove a red car and nothing happened" you are implying a doubt, that the opposite could be an idea worth considering. If a prejudice has a context, that context is relevant - otherwise the idea is presented as general. [Edited for content a second time: I quoted an article I was just reading by chance, presenting data that are exemplary of another point, about the relation between generic statements and actual differences: I now remove it realizing I missed a detail in that quote that excluded the professional context.]
rswail 4y ago
You've stated an axiom.

deleted 4y ago

[deleted]

fjfaase 4y ago

A nice 'visual' illustration of the threshold is found in Percolation theory https://en.wikipedia.org/wiki/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:Transition_de_percolation_2.gif https://en.wikipedia.org/wiki/Percolation_theory#/media/File...

ccbccccbbcccbb 4y ago
I recommend everyone interested in percolation theory to also check https://meltingasphalt.com/interactive/going-critical/ https://meltingasphalt.com/interactive/going-critical/ and play with critical thresholds interactively!
- pietroppeter 4y ago
  Great link, thanks for sharing!
- cecilpl2 4y ago
  This was fascinating! It started with some simple simulations, but led into some very enlightening generalizations about why culture spreads more rapidly in cities than in the countryside, and why new language spreads more rapidly among adolescents.
- spiralx 4y ago
  Thank you!
feral 4y ago
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.
- scoot 4y ago

m12k 4y ago

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.

dr_dshiv 4y ago

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?

high_byte 4y ago

very interesting. I would like to see that math applied to the emergence of life. how slim were our chances? or maybe not slim at all and maybe even unavoidable?

anuvrat1 4y ago

Off Topic: Can I get some more resources like quanta, which explains new research on mainstream or obscure subjects to a layman?

jiggawatts 4y ago
Scientific American, or American Scientist are my go-to favourites. https://www.scientificamerican.com/ https://www.scientificamerican.com/ https://www.americanscientist.org/ https://www.americanscientist.org/

zogomoox 4y ago

So it seems this allows us to understand when phase transitions occur, I wonder if this has applications in improving high temperature superconductors.

pfdietz 4y ago

Entry at Gil Kalai's blog on this result: https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/ https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-p...

itissid 4y ago

Wasn't there also a connection between solving constraint satisfaction (k-SAT Boolean CSP examples) where the clause length to the number of clauses makes it super easy or super hard for solvers to solve for a solution? I vaguely remember this from reading literature when writing heuristic solvers for my CS grad course in AI search.

itissid 4y ago
To answer my own question here are some references to the problem at hand https://dl.acm.org/doi/10.1145/3491210 https://dl.acm.org/doi/10.1145/3491210

_8j50 4y ago

Ok, please ELI5 this for me, The very statement that anything at all is random is completley absurd to me, especially from an academic context. Are they using a definition of random that is equivalent to "nearly impossible to predict"? , I mean, yes, from the perspective of a limited observer random things can exist, but in an absolute sense, for something to be random then even with the knowledge of all things past that lead up to an event, you would not be able to find the cause of that event because it was truly random. Do they mean "unpredictable for humans with known means of predicting"? You might as well use the term "magical" or "miraculous" if you use "random".

d--b 4y ago
This is mathematics, not physics. You can define stuff that don't "really" exist in the world, but that work for the purpose of calculating stuff. "randomness" has as much right to exist in a mathematical sense as a "point" or a "plane".
- _8j50 4y ago
  How can you prove something that isn't real? How is randomness defined as a concept in mathematics?
  - DavidSJ 4y ago
    Randomness is usually defined in terms of a probability distribution, which is just a measure where the total mass assigned to all elements adds up to 1.
  - majkinetor 4y ago
    You can actually only prove unreal things because you impose limitations. Real things can not be proven, but only disproved.
  - siver_john 4y ago
    As long as you can clearly define your starting axioms you can mathematically prove or disprove anything. The physical example would be to just say, suppose a universe with the same properties of ours exist but where the gravitational constant is twice as large prove whether X can occur in that universe. As far as how randomness is defined I believe that might be field dependent but this is me getting out of my depth (I've only taken a few courses on combinatorics).

rurban 4y ago

As I already commented in the first submission of this article: Now that's something I can really use in one of my current problems. Calculating a minimal perfect hash by creating acyclic random graphs. This conjecture gives now tresholds when to stop trying creating random graphs and start afresh. This eg is needed for large perfect hashes in gperf or integer sets in compilers, such as eg. for C switch statements with Unicode. switch in C is only efficient for dense tables, but not sparse. sparse tables are linear, but could be constant. A switch in Pascal was constant, but so far GCC and llvm didn't care. gperf neither. see http://ilan.schnell-web.net/prog/perfect-hash/algo.html http://ilan.schnell-web.net/prog/perfect-hash/algo.html and http://programming.sirrida.de/hashing.html#c_case_of_string http://programming.sirrida.de/hashing.html#c_case_of_string

nsane 4y ago
Isn't the proof for Hamiltonian cycles? From what I could understand from your link to CHM92, it only requires a cyclic graph to stop, which isn't necessarily supposed to touch all vertices. Is that right?
- jonnycomputer 4y ago
  The Hamiltonian cycle is only a motivating example. The conjecture which was proven is much more general. https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-park-and-huy-tuan-pham-settled-the-expectation-threshold-conjecture/ https://gilkalai.wordpress.com/2022/04/02/amazing-jinyoung-p...
less_less 4y ago
Huh, I was thinking the same thing about a related problem: compressed static maps by solving sparse matrices: https://docs.rs/compressed_map/0.1.0/compressed_map/ https://docs.rs/compressed_map/0.1.0/compressed_map/ To get a concrete bound though, you'd probably need to know what is K.

ThinkBeat 4y ago

I notice that most links on physics, astronomy and math cover pre-prints. Would it not be prudent to wait for the final version. Is all the peer reviews and "fact checking" done prior to the preprint?

Ar-Curunir 4y ago
For a big result like this, enough experts read the paper to catch glaring mistakes. Sort of a de facto peer review
- mjreacher 4y ago
  Exactly, Quanta would have the experts they interview go over the paper first if they didn't already go over it before and evaluate it before making any comments. Plus arXiv papers are freely accessible ;)
snowwrestler 4y ago
Reporters often rely on social input to decide what to cover—when someone they trust tells them, “you should check this out.” Then there is an exploratory phase where they gather some basic facts and reach out to contacts to see if it is in fact newsworthy, and maybe to start gathering quotes to add context and fill out the story. At some point they say “this is real” and start working with a editor on a schedule to publish it. Whether a paper is on a preprint serve is not a big deal. If a lot of experts are excited about it, that’s a story anyway. And if it falls apart later due to some surprise flaw… well that is also a story!
lupire 4y ago
Publications don't check facts. They just check formatting and interestingness and plausibility. Peer review is totally separate, not part of publication's pseudo "peer review".

d--b 4y ago

Can anyone with a solid CS background comment on whether this relates to P!=NP at all? I mean this deals with Hamiltonian cycles (which is the focus of a well know NP hard problems). It talks about lower boundaries for randomness (which relates to the information stored in the graph). The article talks about gaps which are logarithmic. I can't quite articulate it, but somehow intuitively, it sounds like it could connect.

leephillips 4y ago

How can a Hamiltonian cycle be increasing? If you have one and you add an edge, then you no longer have a chain of edges that passes through every vertex exactly once, because two vertices will have two edges.

omnicognate 4y ago
The chain of edges forming the cycle doesn't have to include all edges in the graph. There just has to exist a set of edges that form a Hamiltonian cycle. Adding further edges doesn't change that (but adding further vertices would). Edit: Put another way, it's not the Hamiltonian cycle itself that's increasing, it's the property of there existing a Hamiltonian cycle in the graph.
- leephillips 4y ago
  So the definition in the article, “a chain of edges that passes through every vertex exactly once”, is incorrect?
  - omnicognate 4y ago
    No, that's the correct definition of a Hamiltonian cycle. However, the article isn't as clear as it could be about what the "increasingness" aspect applies to. > It’s possible to think about any property, so long as it is “increasing” — that is, if adding more edges to a graph that already contains the property will not destroy the property. The "property" here isn't the Hamiltonian cycle itself, it's the property "a Hamiltonian cycle exists within this graph". This property, rather than the cycle itself, is increasing: if you add edges to a graph that contains a Hamiltonian cycle it will still contain a Hamiltonian cycle.
    - deleted 4y ago
      [deleted]
    - leephillips 4y ago
      Ah, I get it now. Thanks.

dandare 4y ago

It always fascinated me how basically two quarks, one electron and some bosons can create so much chemical complexity. It feels like trowing just 6 types of lego bricks into a huge bag and after a lot of random mixing obtaining whole universe of diversity.

zeroonetwothree 4y ago
All the complexity of computing comes from just two bits. (Some even argue that’s true of the universe itself)
- dandare 4y ago
  Not true, the bits live in a super complex hardware, the don't create any complexity on their own.
- 19h 4y ago
  Except there’s no such thing as bits on the hardware level. There’s voltages. High and low. That’s usually 5V and 0V, respectively.
  - meetups323 4y ago
    You're thinking too concretely. The hardware we know is only one tiny implementation of computation. The broader concept holds across any writeable tape of any sort, whether it uses voltages in silicon, rocks on a beach, or exists only in a person's mind, does not matter one bit -- they're all equally powerful.

bolingo007 4y ago

Yes

qwertygnu 4y ago

>The methods that would eventually lead to [new discovery] began with a breakthrough on a seemingly unrelated problem. Science, baby!

lupire 4y ago

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

yshklarov 4y ago
Actually, you can if you bend the coin!

lupire 4y ago

> young mathematicians Is a 40 yr old mathematician "young"?

sharpener 4y ago

Maybe someone familiar with the graph theory math can help me. I don't understand why these properties aren't numerically accessible. Why is the estimation necessary? E.g. Assume N nodes, and edges E can be created at random with redundancy (picking same edge e twice just keeps the prior edge) by picking pairs of points. Assume N random edge picks are made, then the probability of e.g. a Hamiltonian cycle appearing in those N picks can be calculated. (My quick back of envelope sketch says P(H-cycle) = N! / N^N , but please consult the expert literature.) But one can also calculate the probability of a H-cycle given N+1 random picks, N+2 random picks, ... and that appears as = P(H-cycle) * (1 + extra factors that account for increases in other edges not redundantly in the H-cycle) (Again, my back of envelope sketch for N + 2 picks gives: = P(H-cycle) * ( 1 + 2/(N-1)[N - 3 - 1/N]) , but please consult the expert literature.) These probabilities would seem to tell a user that given a graph with N nodes and E edges, that if e.g. in the H-cycle case, E > N the user can get an explicit probability for the likelihood of a H-cycle being present. Are there graph properties that prevent this approach being viable?