녹원학원 수학과학영재교육 010-3549-5206 : At any party with 6 guests, either 3 are mutual friends or else 3 are mutual strangers

2019년 4월 14일 일요일

At any party with 6 guests, either 3 are mutual friends or else 3 are mutual strangers

____________________________________________________

At any party with 6 guests, either 3 are mutual friends or else 3 are mutual strangers. That is, the symmetric Ramsey Number R(3,3) = 6

If we consider just one person, then the other five must fall into one of the two classes of being either a friend or a stranger. This follows immediately from the pigeonhole principle, namely that, if m pigeons occupy n holes where $\displaystyle n<m$ , then at least one hole contains:

$\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor +1$

pigeons, where $\displaystyle \left\lfloor {} \right\rfloor$ is the greatest integer function. The proof of this follows from the fact that the largest multiple of n that divides into m is the fractional part left over after n divides m-1 or

$\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor$

and so for n pigeons, we get

$\displaystyle n\left\lfloor \frac{m-1}{n} \right\rfloor$

pigeons that could be put into $\displaystyle \left\lfloor \frac{m-1}{n} \right\rfloor$ holes. But we have m pigeons, and so there must be more than this many pigeons in the holes.

Now, for our problem, we have two classes, friends and strangers. If we choose one person, then that leaves 5 people with whom that person is either a friend or a stranger. And so, by the pigeonhole principle, for five objects going into two classes we must have at least:

$\displaystyle \left\lfloor \frac{5-1}{2} \right\rfloor +1=3$

members in one of the classes. In terms of a graph theoretical viewpoint, we have, starting with one vertex extended out to the other five “people” vertexes, that:

where the red edges represent friends and the blue edges represent strangers. We easily see that, regardless of how we choose one of our 2 colors, 3 of them must be blue or else 3 of them must be red, for if we have five red, then we have met the required condition that at least 3 be red, and likewise if 4 are red, we again fulfill the requirement that at least 3 be red; and so, this whole sequence of argument applies if we swap blur for red. Therefore, we are always guaranteed that there are 3 mutual friends or else that there are 3 mutual strangers in any group of 6 people. QED

In terms of Ramsey Numbers, the statement would be written $\displaystyle R(3,3)=6$ .

This is utterly fascinating, because what this is really telling us it that there is a type of structure built into any random finite set. In this case, for any binary operation or else any question or property that has two values, we have it that any finite set of 6 is sufficient to support there being 3 of one or 3 of the other of that property, and that one of the two sets of 3 always exists inside of the 6 items.

This is a glimpse into a type of “deep structure” embedded within the fabric of finite sets. This is more than merely surprising, as one should not really be expecting to find any such structure whatsoever in a random set.
____________________________________________________________________________________________________________________________

Going somewhat beyond this homework problem, from experimental math studies using Mathematica, I conjecture that:

$\displaystyle R(n,n)=\frac{1}{12}(3{{n}^{4}}-20{{n}^{3}}+63{{n}^{2}}-82n+48)$

holds for n<=20 in a completely trivial and weak algebraic sense that the Ramsey Numbers in this range do indeed appear in this formula.

However, there is no natural or reasonable theoretical connection whatsoever between this formula and Ramsey Numbers other than the search for generating functions and sequence matching studies that I conducted. So, for n = 3 to 20 this formula yields:

$\displaystyle \text{R(3,3) = 6}$
$\displaystyle \text{R(4,4) = 18}$
$\displaystyle \text{R(5,5) = }49$
$\displaystyle \text{R(6,6) = }116$
$\displaystyle \text{R(7,7) = }242$
$\displaystyle \text{R(8,8) = }456$
$\displaystyle \text{R(9,9) = }793$
$\displaystyle \text{R(10,10) = }1,294$
$\displaystyle \text{R(11,11) = }2,006$
$\displaystyle \text{R(12,12) = }2,982$
$\displaystyle \text{R(13,13) = }4,281$
$\displaystyle \text{R(14,14) = }5,968$
$\displaystyle \text{R(15,15) = }8,114$
$\displaystyle \text{R(16,16) = }10,796$
$\displaystyle \text{R(17,17) = }14,097$
$\displaystyle \text{R(18,18) = }18,106$
$\displaystyle \text{R(19,19) = }22,918$
$\displaystyle \text{R(20,20) = }28,634$

which all fall nicely into current best-known intervals for these numbers. But these values are essentially nonsense. However, it is currently believed that $\displaystyle \text{R(5,5) = }43$ rather than 49. But there is no polynomial expression that yields 43 and the other lower already known numbers in the sequence of Ramsey Numbers evident from running long and large searches for such. Therefore, I believe that any meaningful approximate or asymptotic formula must be non-polynomial.

Therefore, my intuition says that there may well exist an exponential, non-polynomial expression for the Ramsey Numbers — perhaps similar to the P(n) function of Rademacher such as

$\displaystyle p(n)=\frac{1}{\pi \sqrt{2}}\sum\limits_{k=1}^{\infty }{\sqrt{k}}{{A}_{k}}(n)\frac{d}{dn}\left( \frac{1}{\sqrt{n-\frac{1}{24}}}\sinh \left[ \frac{\pi }{k}\sqrt{\frac{2}{3}\left( n-\frac{1}{24} \right)} \right] \right)$

where

$\displaystyle {{A}_{k}}(n)=\sum\limits_{0\le m<k;\ (m,k)=1}{{{e}^{\pi i\left[ s(m,k)\ -\ \frac{1}{k}2nm \right]}}}.$

But then I may be dreaming here because there need be no sequential connection between one of these numbers and the other — if each is a unique value in it’s own problem space.

What I find frustrating with papers on Ramsey Numbers that I have read is their lack of a more probing approach. We know that calculating Ramsey Numbers is NP-hard. One paper even suggested that this is Hyper-NP hard — but did not specify in what manner they meant this to be true. Most likely they were referring to the absurdly rapid exponential growth of the possible solution space. But where are the more basic insights into the nature of these numbers? Most of what we have now is not much beyond Paul Erdős work in the 1930’s!

In a recent paper on Ramsey Numbers, the physicist Kunjun Song, said: “Roughly speaking, Ramsey theory is the precise mathematical formulation of the statement: Complete disorder is impossible. or Every large enough structure will inevitably contain some regular substructures. The Ramsey number measures how large on earth does the structure need to be so that the speci ed (sic.) substructures are guaranteed to emerge.”

I think that we have yet to ask ourselves the deeper questions to get further along here. I am now researching the different ways in which the same questions may be asked, such as via Shannon limits of graphs and quantum algorithms to see what pure mathematical insight might be gleamed from these approaches. I am looking for good questions that, if properly phrased, should provide a road-map for further fruitful research.

댓글 없음:

댓글 쓰기