It does an okay job, but there are still a lot of unanswered questions, or assumed knowledge for a lay person:
> Mathematicians want to know when such a graph is likely to have some sort of interesting structure.
Why?
> a Hamiltonian cycle, a chain of edges that passes through every vertex exactly once
> adding more edges to a graph that already contains the property will not destroy the property.
Adding one edge after the exact number of edges required to create a Hamiltonian cycle (number of edges equal to number of vertices) would appear to break the property.
> mathematicians often rely on an easier computation, one that provides a minimum possible value, or lower bound, for the threshold [of probability]
How can there be a lower bound other than zero? However small the possibility, surely given an infinite number of cases, there are infinite possibilities of a particular structure being created.
> The sunflower conjecture considers whether collections of sets can be constructed in ways that resemble the petals of a sunflower.
What does this mean?
> If Hamiltonian cycles are “spread out” nicely, that means that not too many cycles contain the same edge or subset of edges.
This seems to suggest multiple Hamiltonian cycles in a graph, contradicting the earlier definition that every vertex must be connected. I guess they meant every vertex in any particular Hamiltonian cycle.
> Adding one edge after the exact number of edges required to create a Hamiltonian cycle (number of edges equal to number of vertices) would appear to break the property.
A Hamiltonian cycle is a simple cycle (no repeated vertices or edges) that contains every vertex of the graph. If a graph G has a Hamiltonian cycle, then adding more edges to G will not make that cycle go away; it will still be there. So the property of "has a Hamiltonian cycle" is not broken by adding more edges.
As a simple example: consider the graph which is the cycle on 5 vertices. That is, the graph has 5 vertices, and is just one big cycle with 5 edges. This graph has a Hamiltonian cycle (the entire graph itself is one such cycle). If we add an extra edge to this graph, say between vertices 1 and 3, the original Hamiltonian cycle does not go away.
> How can there be a lower bound other than zero? However small the possibility, surely given an infinite number of cases, there are infinite possibilities of a particular structure being created.
The lower bound can be other than zero because they are looking at the threshold (probability) at which the probability of the object existing goes from "very low" to "extremely high". This is alluded to in the following quote:
"When edges are added to a random graph of N vertices with a probability of less than log(N)/N, for instance, the graph is unlikely to contain a Hamiltonian cycle. But when that probability is adjusted to be just a hair greater than log(N)/N, a Hamiltonian cycle becomes extremely likely."
I don't know the precise probabilities, but this would be something like: "When the probability of an edge being present is less than log(N)/N then the probability of there being a Hamiltonian cycle is 1/(N^2). When the probability of an edge being present is slightly more than log(N)/N then the probability of there being a Hamiltonian cycle becomes (1 - 1/(N^2))."
(Note that I plucked the above probabilities out of thin air just for the sake of illustration, just to give you an idea of the form that these statements take. For the precise probabilities, please ask Google.)
> This seems to suggest multiple Hamiltonian cycles in a graph, contradicting the earlier definition that every vertex must be connected.
This is no contradiction. There can be multiple Hamiltonian cycles in a graph. Consider the complete graph on n vertices; there are roughly n-factorial-many Hamiltonian cycles. Any permutation of the vertices corresponds to one such cycle. Different permutations can correspond to the same cycle, so the number is not exactly n-factorial. But you get the idea.
> Consider the complete graph on n vertices; there are roughly n-factorial-many Hamiltonian cycles. Any permutation of the vertices corresponds to one such cycle. Different permutations can correspond to the same cycle, so the number is not exactly n-factorial.
Isn't it just (n-1)!/2 as each cycle can be cyclically permuted (n possibilities) and (for n>=3) also be reversed? (Cases n=2 and n=1 have only one cycle.)
(That wasn't the point you were trying to get to, I know. I'm just thinking about the precise number.)
Thanks for the answers to some of my questions. I think the conclusion is that the article is above my comprehension, which is absolutely fine given who I imagine Quanta's readership is.
> Mathematicians want to know when such a graph is likely to have some sort of interesting structure.
Why?
> a Hamiltonian cycle, a chain of edges that passes through every vertex exactly once > adding more edges to a graph that already contains the property will not destroy the property.
Adding one edge after the exact number of edges required to create a Hamiltonian cycle (number of edges equal to number of vertices) would appear to break the property.
> mathematicians often rely on an easier computation, one that provides a minimum possible value, or lower bound, for the threshold [of probability]
How can there be a lower bound other than zero? However small the possibility, surely given an infinite number of cases, there are infinite possibilities of a particular structure being created.
> The sunflower conjecture considers whether collections of sets can be constructed in ways that resemble the petals of a sunflower.
What does this mean?
> If Hamiltonian cycles are “spread out” nicely, that means that not too many cycles contain the same edge or subset of edges.
This seems to suggest multiple Hamiltonian cycles in a graph, contradicting the earlier definition that every vertex must be connected. I guess they meant every vertex in any particular Hamiltonian cycle.
And so on...