Very Large Cliques are Easy to Detect
joint with Alexander Andreev
Abstract.
It is known that, for every constant k larger than 2, the presence of a
k-clique (a complete subgraph on k vertices) in an n-vertex
graph cannot be detected by a monotone boolean circuit using fewer
than (n/\log n)^k gates. We show that, for every constant
k, the presence of an (n-k)-clique in an n-vertex graph can be
detected by a monotone circuit using only n^2\log n gates.
Moreover, if we allow unbounded fanin, then a logarithmic number of gates is
enough.