The two-color Ramsey number, $R(m, n)$, is the minimum number of vertices, $||V||$, in a complete graph necessary for there to exist a clique of order $m$ or an independent set of order $n$. In terms of the maximum clique or party problem, $R(m, n)$ is the minimum number of guests that must be invited to a gathering s.t. $m$ guests will mutually know one-another and $n$ will not know one-another.

Imagine one wants to slightly improve the bounds for $R(m, n)$ by attempting to find a graph $G_{ce}$ with $||V|| = N$ vertices where the above constraint is invalid. In this case, one might proceed by exhaustively searching through a random subset of possible two-colorings of the complete graph of $N$ vertices, which we'll denote $S$.

However, there's a catch. We're only allowed to find a counterexample graph in $S$ by globally removing specific edges that are colored a particular way, and then counting the total number of connected vertices and colored edges of each type in the individual graphs. For example, if we label each of the $\frac{N(N-1)}{2}$ edges in the two-colored graphs in $S$, we can decide to remove an edge with a specific label in all graphs if it is colored red instead of blue. If $S$ is the set of all possible two-colored graphs, this would decrease by one the number of edges in exactly half of the graphs in $S$. We cannot remove an edge with a specific label in a specific graph, all edge deletions must be global.

Is it possible to isolate a counterexample graph $G_{ce}$ in this manner? If so, how might might we optimize our chances of finding it?

  • $\begingroup$ What is "pruning"? $\endgroup$ – Brendan McKay Jan 15 '12 at 0:49
  • $\begingroup$ @Brendan, by 'pruning' I mean removing an edge. $\endgroup$ – Allen Jan 15 '12 at 0:52
  • $\begingroup$ @Brendan McKay, I hopefully removed the confusing terminology. $\endgroup$ – Allen Jan 15 '12 at 0:58
  • $\begingroup$ Can't we just take a counterexample and then eliminate the edges that are colored differently from it? $\endgroup$ – Will Sawin Jan 15 '12 at 8:27
  • $\begingroup$ @Will Sawin, are you saying that this is roughly equivalent to asking for the direct construction of a counterexample graph? It's not necessarily clear to me that this is so? One receives feedback for how the individual graphs change in their relative red/blue edge counts and connectivity as edges are removed, which makes this feel more like a search process with an appropriate amount of computational expense. $\endgroup$ – Allen Jan 15 '12 at 22:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.