Abstract: 
Given a graph $G$ with $n$ vertices and a number $s$, the
decision problem Clique asks whether $G$ contains a fully connected
subgraph with $s$ vertices. For this NPcomplete problem there exists
a nontrivial lower bound: no monotone circuit of a size that is
polynomial in $n$ can solve Clique. This entry
provides an Isabelle/HOL formalization of a concrete lower bound (the
bound is $\sqrt[7]{n}^{\sqrt[8]{n}}$ for the fixed choice of $s =
\sqrt[4]{n}$), following a proof by Gordeev. 
BibTeX: 
@article{Clique_and_Monotone_CircuitsAFP,
author = {RenĂ© Thiemann},
title = {Clique is not solvable by monotone circuits of polynomial size},
journal = {Archive of Formal Proofs},
month = may,
year = 2022,
note = {\url{https://isaafp.org/entries/Clique_and_Monotone_Circuits.html},
Formal proof development},
ISSN = {2150914x},
}
