This week, Professor Siemion Fajtlowicz assigned two home work problems:

1. How many graphs with vertices 1 … n are there?

2. Up to isomorphism, how many graphs are there with n vertices?

3. If you invite 6 random people to a party, show that 3 of them will know each other or 3 of them will be mutual strangers — and show that this is guaranteed to always be the case — but only if you invite a minimum of 6 random people to the party. It will not be the case if we only invite 5 random people or 4 random people, et cetera.

____________________________________________________________________________________________________________________________
Question 1 and 2 may appear to be identical questions, but they are not at all identical though they are related.

Question 1 is asking for the number of elements of S. Question 2 is asking for the number of elements of the quotient G\S, a very different and much more difficult question.

Theorem. There are

\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}

graphs with vertex set \displaystyle \{1,2,3,...,n-1,n\} .

Proof. The question is easily answered. Given n vertexes, if we start from vertex 1 and connect an edge to each of the remaining vertexes, so that 1 goes to 2, 1 goes to 3, and so on until 1 goes to (n-1) , and 1 goes finally to n. Now, including the null edge or simply 1 itself connected to nothing, which is a legitimate graph, we have that there are n graphs. Repeating this for each additional vertex, and taking into account that the edge may originate at either one of the vertexes making for two graphs — if allowing full duplicates — then we will have that there are exactly,

\displaystyle ^{1+2+3+...+(n-1)+n}

possible graphs raised to the power of 2 to account for starting at either vertex, which gives us:

\displaystyle {{2}^{1+2+3+...+(n-1)+n}}={{2}^{\sum\limits_{i/{{\mathbb{Z}}_{+}}}{i}}}={{2}^{\frac{n(n+1)}{2}}}

Therfore, the number of graphs with vertices 1 to n are:

\displaystyle {{2}^{\left( \begin{matrix} n \\ 2 \\ \end{matrix} \right)}}

and this is simply a more compact way of writing the RHS of the previous result using binomial coefficients. QED

____________________________________________________________________________________________________________________________

Theorem. Up to isomorphism, there are

\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}

graphs with n vertices.

The answer to the question is much more difficult, because the answer involves some hefty but basic machinery from Group Theory and Combinatorics involving Burnside’s Lemma and Polya’s Enumeration Theorem such that this question may be reworded in those terms, so that it becomes:

How large is the set \displaystyle \sum\nolimits_{n}{{}}\backslash S where \displaystyle \sum\nolimits_{n}{{}} denotes the symmetric group on n letters and \displaystyle S is the set of graphs with vertex set \displaystyle {1,2,3,...,n-1,n} ?

The answer is

\displaystyle \frac{1}{n!}\sum\limits_{n\in \sum\nolimits_{n}{{}}}{{{2}^{o\left( \sigma \right)}}}

where \displaystyle o\left( \sigma \right) denotes the number of \displaystyle \sigma orbits on the set.

____________________________________________________________________________________________________________________________

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.

© 2012 Kurt Lovelace – All Rights Reserved

2 thoughts on “Graph Isomorpshism and Coloring

  1. Just to clarify something about the party of six example – “three mutual friends” means a clique of three, and not just three vertices that are connected, right? i.e. “Bob knows Sally and Sally knows Ishmael” is not sufficient to make Bob, Sally, and Ishmael mutual friends.

    1. Absolutely correct, gcbenison. They must all know one another in order to be ‘mutual friends.’ If we use use the color RED to mean mutual friend, then there must be a RED line connecting the vertex of Bob to the vertex of Sally to the vertex of Ishmael — a triangle of connections colored RED.

      I added a nice graph of K(6) I just created in Mathematica to help clarify. You may suppose the green triangle to be three mutual strangers, while the red triangle represents three mutual friends.

      Also, I might add that this problem may be viewed as “one of avoidance” — that is, in a certain sense, one cannot “avoid” having either three friends or three strangers, if there are six people, as one of these two must be true. This applies to all the Ramsey type problems — they may all be viewed as problems of inevitability and hence a deep unexpected structure within finite sets — that if we have a finite graph of a given size, then we must have a given or unavoidable colorability “structure” with that graph — it simply cannot be avoided.

Please Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s