As we know, the $k$-clique function $CLIQUE(n,k)$ takes a (spanning) subgraph $G\subseteq K_n$ of a complete $n$-vertex graph $K_n$, and outputs $1$ iff $G$ contains a $k$-clique. Variables in this case correspond to edges of $K_n$. It is know (Razborov, Alon-Boppana) that, for $3\leq k\leq n/2$, this function requires monotone circuits of size about $n^k$.
But what if we take one fixed graph $G\subseteq K_n$, and consider the monotone boolean function $CLIQUE(G,k)$, which takes a subset $S\subseteq [n]$ of vertices, and outputs $1$ iff some $k$ vertices in $S$ form a clique in $G$. Variables in this case correspond to vertices of $K_n$, and the function is just the standard clique function but restricted to the spanning subgraphs of one fixed graph $G$.
1. Does there exist $n$-vertex graphs $G$ for which $CLIQUE(G,k)$ requires monotone circuits of size larger than $n^{O(\log n)}$? I guess - NO.
2. Is $CLIQUE(G_n,k)$ an NP-hard problem for some sequence of graphs $(G_n\colon n=1,2\ldots)$? I guess - NO.
Note that if $C_1,\ldots,C_r$ are all maximal cliques in $G$, then $CLIQUE(G,k)$ can be computed as an OR of $r$ threshold-$k$ functions, the $i$-th of which tests whether $|S_a\cap C_i|\geq k$. Thus, if $r=poly(n)$, then the entire circuit is of polynomial size. But what about graphs with an exponential number of maximal cliques? (A clique is maximal it no vertex can be added to it.)
It is possible to "embed" $CLIQUE(m,k)$ into $CLIQUE(H,k)$ for a particular graph $H$ on $n=2^m$ vertices. In particular, Bollobas and Thomason (1981) have shown that, if $H$ is a Hadamard graph whose vertices are subsets of $[m]$, and two vertices $u$ and $v$ are adjacent iff $|u\cap v|$ is even, then $H$ contains an isomorphic copy of every graph $G$ on $m$ vertices. Can this fact be combined with Razborov´s lower bound (of about $m^k$) for $CLIQUE(m,k)$ to conclude that $CLIQUE(H,k)$ requires monotone circuits of size about $m^k$? A potential problem here is that, even though the graph $H$ "contains" all $m$-vertex graphs, these graphs are not on the same set of vertices. And Razborov's argument rquires that positive and negative inputs ($k$-cliques and complements of complete $(k-1)$-partite graphs) are graphs on the same set of vertices. Moreover, all positive inputs ($k$-cliques) are just isomorphic copies of one and the same fixed $k$-clique.
3. Any ideas? Has anybody seen such type of problems being considered? I mean, decision problems for subgraphs of a fixed graph. Or, say, the SAT problem for sub-CNFs of one fixed (satisfiable) CNF (obtained by removing some literals)?
Motivation: Problems of this kind are related to the complexity of combinatorial optimization algorithms. But they seem to be interesting in themself. Why should we seek for algorithms that are efficient on all graphs? In reality, we are usually interested in the properties of small pieces of one (large) graph (network of streets in a country, or facebook, or the like).
Remark 1: If the graph $G=(L\cup R,E)$ is bipartite, then the vertex-edge incidence matrix of the inequalities $x_u+x_v\leq 1$ for all $(u,v)\not\in E$ is totally unimodular, and one can solve the clique problem on induced subgraphs of $G$ via linear programming. Thus, for bipartite graphs $G$, $CLIQUE(G,k)$ has a small (albeit non-monotone) circuit.
Remark 2: An indication, that in the case of bipartite graphs $G$, the answer to Question 1 "should" indeed be NO is that then the following monotone Karchmer-Wigderson game on $G$ needs only $O(\log n)$ bits of communication. Let $k$ be the largest number of vertices in a complete bipartite subgraph of $G$. Alice gets a set $A$ of red nodes, Bob a set $B$ of blue nodes such that $|A|+|B|>k$. The goal is to find a non-edge between $A$ and $B$.