The Numbers of Dependent k-Sets in a Graph Are Log Concave

A set of vertices in a graph is said to be dependent if it is not independent. Let pk(G) denote the number of dependent sets of size k in the graph G. We show that, for any graph G, the sequence {pk(G)} is logarithmically concave.