[FRIAM] Ramsey a pragmatist mathmatician?

[jon zingale]

N,

As Marcus suggests, the colorful statement aims to evoke a feeling for the
exploding computational complexity associated with the calculation of Ramsey
numbers. The Ramsey number is interesting from a complexity perspective
because it gives a condition for when to expect a particular kind of
property (the existence of a clique) to manifest in a graph of
relationships. What is amazing is that the values we "know" are very small
and yet require a tremendous amount of computational effort to verify[5].
There are some good asymptotic bounds for larger Ramsey numbers, but in
general, this problem is considered very difficult to solve. The original
context where I heard Erdős speak about the problem was in the film 'N is a
Number'. To some extent, the problem elucidates the value of creative
thinking. There are problems of these types that no computer (and possibly
no quantum computer) can hope to brute force in the lifetime of the universe
and yet a mind may find a solution.

Problems like these abound in combinatorics, problems that are simple to
state and have direct physical interpretations and yet give rise to
tremendous complexity. I don't know much about Ramsey or his philosophy, but
you'd be hard-pressed to find a mathematician that was unfamiliar with *his*
number.

J

ps. I didn't mean to necessarily tie this idea to our discussion of
*zero-knowledge protocols* though it does point to a different kind of
*unknowable* perhaps, one to do with the physical limitations of
computation.

[5] For instance, we know that a given two-colored graph with either a red
or blue pentacle has somewhere between 43 or 48 vertices, but we don't know
which. Such a small number and yet...



--
Sent from: http://friam.471366.n2.nabble.com/