Monotone Circuit Complexity of Matching

We show that the perfect matching function on n-vertex graphs requires monotone circuits of size 2 n Ω(1) . This improves on the n Ω(log n) lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.