Common neighbourhood from bipartite density
ID: common-neighbourhood-from-bipartite-density
If a bipartite graph with class sizes has at least edges, double count pairs consisting of an -set in the first class and a common neighbour in the second. Convexity of binomial coefficients gives some with . When , the quotient is at least . This turns density into a large complete bipartite subgraph.
New to topics? Read the docs here!