One application of graph theory that’s particularly interesting to me
is called Ramsey theory. It’s particularly interesting as someone who
debunks a lot of creationist nonsense, because Ramsey theory is in
direct opposition to some of the basic ideas used by bozos to
purportedly refute evolution. What Ramsey theory studies is when some
kind of ordered structure *must* appear, even in a pathologically
chaotic process. Ramsey theory is focused largely on *structures* that
exhibit particular properties, and those structures are usually
represented as graphs.
For example, the most common introductory application of Ramsey theory
is to ask: given a complete graph KN. What is the minimum
N for which you *cannot* assign a 2-coloring to its nodes without
getting a single-colored triangle. The solution is 6: there is no possible assignment of two colors to edges in a complete graph without having at least one single-colored triangle. This is, in fact, known as Ramsey’s theorem.
There are a lot of other similar problems, which all have the flavor of looking at progressively larger structures, and asking how large the structure needs to grow before it *must* necessarily contain a particular substructure.
There’s the clique theorem, which asks: given a graph with N nodes,
for some number k<N, how many edges can you add before the graph
*must* contain at least one k-clique?
A case where the underlying proof is graph theoretic, but the graph
isn’t completely obvious is the Hales-Jewett theorem. This says for any
two numbers N and C, there is a number H such that any assignment of C colors to the cells of an H-dimensional (N×N×N×…×N) cube
*must* contain at least one full row which has the same color. To see how
this reduces to a graph problem, think of each cell of the cube as a vertex,
assigning colors to the vertices, and then looking for a certain kind of
path through nodes assigned the same color.
Hales-Jewett is also sometimes called the tic-tac-toe theorem, because one
way of interpreting it is: H is the minimum dimensionality of a game of
N-in-a-row tic-tac-toe with C players where one player *must* win; the game cannot possibly end in a draw.
The reason why this should be of particular interest in terms of the evolution debates should be obvious: the creationists like to make arguments of the form “X cannot happen, because order cannot arise from chaos”. Bzzzt. No, given a large enough disordered system, order *must* inevitably arise in some part of it. What Ramsey theory shows is that disorder, carried to a sufficiently high degree, is a kind of order in itself. In Ramsey proofs, in general, the only way to drag out a process to its Ramsey bound is by *deliberately* being adversarially
chaotic: doing things in a way that specifically delays the order as long as possible. Take K20, and assign a 2-coloring to its edges. Odds are, you’re going to get a single-colored triangle long before you’ve fully colored a subgraph isomorphic to K6; you have to deliberately work to avoid coloring a triangle before you’ve colored a subgraph of K6.
Now I wanna know what dimension I have to play tic-tac-toe in to prevent a draw!
The wikipedia entry proves that H=8 is sufficient, but it may be possible to go lower. I must know!
Actually, I’ve found the answer now! Thank you, MathWorld.
For 3-in-a-row, the 3×3 board is actually pretty much the largest board possible that *isn’t* forced into a win. Increasing any of the dimensions (such as a 3×4 board) or adding additional dimensions (such as a 3x3x3 board) remove the possibility of a draw.
As an added bonus, when doing 4-in-a-row, the 4x4x4 board (standard for 3d tic-tac-toe) is the minimum size for ensuring a win. It’s impossible to draw!
The mutants are everywhere — TAG!
http://qw88nb88.wordpress.com/2007/07/17/meme-mut8nt-r4/
Mark, I think you’ve done Ramsey a little disservice: that R(3, 3) = 6 is a result with a short, elementary proof. Ramsey’s theorem is the much harder result that for any n, there exists an N such that two-coloring the edges of a K_N necessarily results in a monochromatic K_n.
He never said that R(3,3) was all there was to Ramsey Theory. He simply said that it was a common introductory application of it. This is simply true – it’s always the first thing I see when people teach Ramsey Theory, because it’s such a simple, easy-to-grasp example.
In your post, you say that the coloring is applied to the nodes, but Ramsey’s theorem is about coloring the edges, and if the question is about coloring the nodes, the answer is 5, not 6.
Issue with finding an “always winnable” tic-tac-toe board is that, played perfectly, one player will always win.
Still, nifty stuff.
Joe: Correct. Of course, the proof that the first player always has a winning strategy is existential. There exists no general procedure to actually figure out what “playing perfectly” would be.
Evolution as change over time is not disputed.
Life from lifeless matter has NEVER(repeat NEVER) been duplicated in a lab. If abiogenesis requires 100 steps we haven’t even made the first 2 work.
The math of random creation is against you:
http://www.direct.ca/trinity/crutches.html
DavidM:
This random babble of yours has *what* to do with *anything* I said in my post?
The point of Ramsey theory is that small-scale order is an inevitable outcome of large-scale randomness. Contrary to the constant claims of various creationist twits, it is *not* impossible for order to emerge from randomness. Despite the constant drumming of
that William Debmski, Granville Sewell and their ilk that order cannot emerge from disorder without the intervention of some intelligent agent, the fact is that they’re wrong: order can, and *must* emerge from disorder.
What we have or have not done in a lab today is irrelevant to that point. (Or, in fact, to *any* point. The fact that we have not yet done something in a lab has no bearing on whether it’s possible for us to do it in a lab (every day, people are performing experiments which were never performed before); and whether or not it’s doable in a lab
has nothing to do with whether or not it’s possible in the world outside of the lab. (I don’t know about you, but I don’t particularly expect to see any stars collapse into black holes in a laboratory.)
Random babble? Did you even read what you posted?
“It’s particularly interesting as someone who debunks a lot of creationist nonsense, because Ramsey theory is in direct opposition to some of the basic ideas used by bozos to purportedly refute evolution”
Point of fact YOU bring evolution into the argument when it has no place in it. Its like saying: the Sun evaporates water, therefore one day there will be no water left.
Name calling and slander to those you disagree with is what I would call babbling.
Refute the numbers in the link I posted. Even if I give you many *orders of magnitude* of ‘order appearing from disorder’ it still reeks of impossibility.
As a point of fact, saying evolution-as-origin without any proof of it *IS* faith based science.
Its particularly the end of the blog that reinforces the faith based science concept. That section reminds me of the evolutionary approach where you flip a number of bits, and eventually some of them just “stick”.
Your comments are irrelevant to the post. Mark was not making a statement about the likelihood of abiogenesis. Instead, he was refuting the commonly expressed notion that chaos is absolute, and order requires intelligence. Low-level order is a necessary property of high-level chaos, and Ramsey Theory is one demonstration of that.
Mark has debunked ‘big numbers’ arguments before, and very well, but this isn’t a post about that. This didn’t even have a comment about that.
And, of course, all the math in the world doesn’t remove the fact that, however unlikely abiogenesis on earth may be, abiogenesis in heaven (presumably forming a complete God rather than a primitive semi-organism) is so immensely, staggeringly more improbable that your entire argument is rendered trivial.
If life couldn’t have arisen by itself on Earth, it certainly couldn’t have done so in Heaven, either. Especially since God didn’t evolve, according to most accounts. How many point mutations is it to go from void to divinity, again?
DavidM: Your link is full of babble because it starts off by getting the process wrong.
Think of it this way: what are the odds of picking the number six at random? Well, that depends. Are you rolling a die, generating 256-bit numbers, or picking names out of a hat?
The whole point of evolutionary theory is to propose a process giving the known results. That process is not random string generation by independent random selection for each position in the string.
When your description of what can’t happen contains no evolution, that’s a sign that you aren’t rebutting evolution.
Ironic, seeing that you didn’t read it either. Mark made it very clear that Ramsey theory and similar results shows that the creationist strawman for evolution doesn’t work in itself.
Of course, since a strawman is a faulty and misappropriate description, it doesn’t matter for science. But it does matter for the public debate, as Mark says.
Since evolution concerns already existing populations of replicators, the question of abiogenesis is further random babble. It may involve some of the mechanisms that has already proven their worth in evolutionary biology, and in fact an analogous chemical selection is a proposed mechanism.
And as you should know if you are into modeling this, basic “variation with selection” doesn’t need very large populations to work fast. (For a real world example, 10 generations sufficed to get the alleles that eliminates Wolbachia gender selection fixed in butterflies.)
There are several known and verified processes that fix alleles. Why don’t you learn some of them?
The one most famous is by selection, where properties expressed by these alleles contribute positively for survival, which fixes those alleles over time. There is no creationism randomness involved in selection, which responds to the immediate environment of the population. See the butterfly example above.
The one that corresponds most to your description is neutral drift, where alleles which are neither negative nor positive for fitness may be fixed by some very small probability. This probability goes up for small populations, and in case of bottlenecks the survivors can drift a lot. (Since obviously, there is a larger risk for some neutral alleles to disappear.) This would be expected of the butterflies in our example.
Then you have genetic hitchhiking, where genes happen to get fixed when they are linked to a beneficial gene. That is a process with both a random coincidence and a contingent deterministic selection. (Which, of course, the whole of “hereditary variation and selection” already is.) Guess that will twist your head off because of all the spinning it will endure when it discovers that the world isn’t as simple black and white as the creationist preachers paint it. 😛
DavidM:
I assure you that I read what I posted, and I was careful to word it correctly.
One of the incessant arguments coming from anti-evolutionists is the idea that
order *must* be the result of a deliberate action; that random processes cannot
ever produce order.
Ramsey theory shows, quite clearly, how utterly wrong that is.
Abiogenesis is a different question, and a highly complicated one. As I’ve said numerous times before on this blog: I don’t think that there is any way to accurately assess the
probability of abiogenesis given our current state of knowledge. There are some reasonably convincing arguments that a self-replicating molecule is inevitable under the right conditions; there are some reasonably convincing arguments that a self-replicating molecule is highly unlikely under any conditions. Which of those arguments is correct? Or is the truth somewhere in the middle? I don’t think we have enough information
to be able to really answer that question at the present. Perhaps given some time, we’ll be able to more definitively say what the likelihood of the initial self-replicator was; but for now, it’s an open question.
And that’s *still* a completely different issue from what I was discussing in the post. The post is about Ramsey theory, and how small-scale order is an inevitable product of large-scale randomness – which is in direct contradiction to the claims of numerous creationists. Whether or not abiogenesis is correct, whether or not abiogenesis is possible, is irrelevant. As I keep saying: the point is, creationists keep saying that order
*cannot* be the result of randomness. Just look at the bozo who Bill Dembski cited a couple of weeks ago; his *entire* argument is based on the idea that order never comes from randomness. Ramsey theory says, in a definitive way, that he – and anyone else making that claim – is wrong.
This random babble of yours has *what* to do with *anything* I said in my post?
If mankind evolved from monkeys, then WHY IS THERE TIC-TAC-TOE???
Coin: “If mankind evolved from monkeys, then WHY IS THERE TIC-TAC-TOE???”
Because monkeys are better at using their toes!
Sorry. We were talking about Ramsey Theory, right?
See also:
Burr, S. A. “Generalized Ramsey Theory for Graphs–A Survey.” In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). New York: Springer-Verlag, pp. 52-75, 1974.
Erdos, P. and Szekeres, G. “On Some Extremum Problems in Elementary Geometry.” Ann. Univ. Sci. Budapest Eotvos Soc. Math. 3-4, 53-62, 1961.
Graham, R. L. and Nesetril, J. “Ramsey Theory in the Work of Paul Erdos.” In The Mathematics of Paul Erdos (Ed. R. L. Graham and J. Nesetril). Heidelberg, Germany: Springer-Verlag, 1996.
Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdos and the Search for Mathematical Truth. New York: Hyperion, pp. 51-57, 1998.
Looking over at MathWorld:
Dilworth’s Lemma.
Erdos-Stone Theorem: A generalization of Turán’s theorem to non-complete graphs….
Extremal Graph Theory: The study of how the intrinsic structure of graphs ensures certain types of properties (e.g., clique-formation and graph colorings) under appropriate conditions….
Structural Ramsey Theory: A generalization of Ramsey theory to mathematical objects in which one would not normally expect structure to be found…
Turán’s Graph Theorem.
Lots and lots of good stuff.
And when will we learn that Creationists don’t WANT to learn Math?
DavidM:
You should go easy on that that word, “Never.” Scientists have taken fragments of RNA, mixed them with DNA, and watched them assemble themselves into a virus. Are fragments of RNA alive? Is DNA? Is a virus alive?
Yes, it’s not abiogenesis. And yes, it’s debatable that a virus is alive. But to me it looks eerily like nonliving matter pulling itself together and coming to life.
You’re wrong on one thing. The point that order does come out of chaos is what makes it amazing but what you are using is but an analogy to life. To say that out of chaos came order in life is, of course, far more complicated but so is God. So what your wrong about is that it somehow “debunks a lot of creationist nonsense”, that statement is nonsense.
I do like what you have to say though and appreciate it because we need to separate the wrong from right and all the misinterpretations people have over ideas and one another.
I am not at all fazed by any of the replies I have seen either and, in fact, I would love to have some information like websites and books on the mathematical side of evolution if anyone could provide some I would appreciate it a lot. Thanks.
Chaotic order has a nice ring to it and is not something any well educated Christian is afraid of or thinks debunks creation.
God is and always will be.
Kyle:
You’re not listening to what I’m saying.
The incessant argument that I’m critiquing is the kind of nonsense that spews from Granville Sewell, William Dembski, Ken Ham, and people like that, who constantly repeat, like a mantra, that order *cannot* arise from chaos. Ramsey theory absolutely refutes their argument, which is the only argument I’m criticizing here.
I’m not arguing about abiogenesis. I’m not saying that Ramsey theory proves anything one way or another about abiogenesis. I’m not claiming
that Ramsey theory proves anything one way or another about christianity or religion. As I keep saying, that’s not the topic of this post. This post mostly just talks about the idea of Ramsey theory, which is a fascinating
application of graph theory. What little it says beyond the mathematical presentation is simply that anyone who argues that order cannot be the product of randomness *is wrong*.
The most basic mathematical models for evolution is population genetics and quantitative genetics. (Since evolution is describing how populations behaves.)
Population genetics is a bottom up description from first principles which deals with the dynamics of allele frequencies under the influence of evolutionary forces. Quantitative genetics is a top down description which begins from the characteristics of realized phenotypes.
A blog that describes this including introductory material is the ScienceBlogs sister blog Gene Expression.
Of course, there are also a lot of math on such things as cladograms over characteristics or species relationships, statistical methods for genomes, et cetera. But the core of the science would be the above.
The link failed, so here is a new try: introductory material on the math of evolutionary models.
I would also like to point to another ScienceBlogs sister blog that describes math as applied to evolution a lot, evolgen. A series describing how to detect natural selection using molecular data is particularly interesting to compare with the above.
Here is a post that links to the series and includes showing how the divergence between two species of Drosophila is tested out to be due to selection by two different tests (as opposed to neutral drift).
The math is no more complicated than to take quotients to get frequencies, so you can shortly see for yourself real tests of evolution. If just all science was so easy to access as evolution. 🙂
The implications of Ramsey theory for understanding evolution are interesting, but not particularly useful. There are even simpler demonstrations of order arising from chaos – anyone who rejects those simpler examples that clearly show it’s possible won’t be convinced by more complex examples that show it’s inevitable.
Still, this is pretty neat stuff. It just won’t help with the irrational people.
arXiv:0707.2853 [pdf]
Phase transition in the maximum clique problem: the case of Erdos-Renyi graphs
Authors: Kazuhito Shida
Comments: About 7 pages, 2 tables, 4 figures,
Subjects: Statistical Mechanics (cond-mat.stat-mech)
A phase transition, like the one already found on Boolean satisfiability problem by Kirkpatrick and Selman, is found on max clique problem on ER graphs. Although number of the datapoints is limited, the transition seems to obey finite size scaling. The transition also shows concentration of the graph instances which need particularly large CPU time to solve.
Xanthir (#5): He didn’t say it was all there is to Ramsey Theory, but he did say that the fact that R(3, 3) = 6 is known as Ramsey’s Theorem. It’s not: Ramsey’s Theorem is the substantially more powerful result that I quoted.