Improved lower bounds on the randomized complexity of graph properties

We prove a lower bound of Ω(n^4/3 log^1/3 n) on the randomized decision tree complexity of any nontrivial monotone n-vertex graph property, and of any nontrivial monotone bipartite graph property with bipartitions of size n. This improves the previous best bound of Ω(n ^4/3) due to Hajnal (Combinatorica 11 (1991) 131-143). Our proof works by improving a graph packing lemma used in earlier work, and this improvement in turn stems from a novel probabilistic analysis. Graph packing being a well-studied subject in its own right, our improved packing lemma and the probabilistic technique used to prove it may be of independent interest.