Coming up with an adversary strategy for a clique of maximum size

Question

I’m having trouble coming up with a good adversary strategy for this problem:

Input: a graph G

Output: the maximum size of any clique in G

Where the algorithm asks each time, “are vertices x and y adjacent?” and it could ask about any random pair of vertices in the graph.

So, I need an adversary strategy to force the algorithm to work for as long as possible. Here’s what I have so far:

• for any graph with n vertices, there exists n(n-1)/2 unique vertex pairs the algorithm can ask about
• Adversary could use a grid to keep track of questions asked? Through an adjacency matrix?

I’m kind of stumped on a possible strategy, any help? Would it be better for the adversary to answer “no” to the algorithm, or “yes”?

Answer 1

Following is a simple adversary strategy that makes the algorithm make $\frac{n(n-1)}{2}$ queries:

For every pair $(x,y)$, adversary answers "no", i.e., $x$ and $y$ are not adjacent.

Proof: Since the adversary is maintaining an empty graph, the answer is trivially a clique of size $0$. However, if the algorithm says "$0$" before making all $\frac{n(n-1)}{2}$ queries, then for any non-queried vertex pair $(x,y)$ the adversary can make $x$ and $y$ adjacent; hence forming a clique of size $2$, and thus proving the algorithm wrong.