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?
