Hereditary hypergraph property

A property of uniform hypergraphs is hereditary if every induced subhypergraph of a hypergraph with that property also has the property. It is understood to be invariant under relabelling the vertex set. For example, excluding a specified induced hypergraph is hereditary. This permits counting restrictions to smaller vertex sets using the same counting function.

For a hereditary hypergraph property of $r$-uniform hypergraphs, ${\mathcal{P}}_n$ is the family on the labelled vertex set $[n]$. For $n\ge r$, its normalized speed lies between zero and two and is nonincreasing. Choose a uniformly random member on $n+1$ vertices and record its edge indicators. Each edge occurs in $n+1-r$ vertex-deletion restrictions. The Shearer inequality bounds its information entropy by the sum of the restriction entropies divided by $n+1-r$. Each restriction has at most $|{\mathcal{P}}_n|$ possible values. Division by $\left(\genfrac{}{}{0ex}{}{n+1}{r}\right)$ gives $\log d_{n+1}\le \log d_n$. Empty families are handled directly by heredity.