Very large cliques are easy to detect

It is known that, for every constant k⩾3k⩾3, the presence of a k-clique (a complete sub-graph on k vertices) in an n  -vertex graph cannot be detected by a monotone boolean circuit using much fewer than nknk gates. We show that, for every constant k  , the presence of an (n-k)(n-k)-clique in an n  -vertex graph can be detected by a monotone circuit using only a logarithmic number of fanin-2 OR gates; the total number of gates does not exceed O(n2logn)O(n2logn). Moreover, if we allow unbounded fanin, then a logarithmic number of gates is enough.