The numbers of dependent \(k\)-sets in a graph are log concave (Q1850583): Difference between revisions

A set of vertices in a graph is dependent if it is not independent. Let \(p_k(G)\) denote the number of dependent sets of size \(k\) in a graph \(G\). The author shows that for any graph \(G\) the sequence \(\{p_k(G)\}\) is log concave, i.e., \(p_k^2 \geq p_{k-1}p_{k+1}\) for all \(k\) \((1 \leq k \leq n-1)\) where \(n\) is the order of \(G\). The author uses a modification of the partitioning technique used by Hamidoune.