scientific article; zbMATH DE number 1564004

From MaRDI portal
Publication:4528825





A class of directed graphs is hereditary if it is closed under deleting and renumbering vertices. The entropy of an infinite hereditary class \({\mathcal X}\) is defined as \[ h({\mathcal X})=\lim_{n\rightarrow\infty}\frac{\log_2|{\mathcal X}_n|}{n^2}, \] where \({\mathcal X}_n\) is the set of all graphs in \({\mathcal X}\) with vertex set \(\{1,2,\dots,n\}\). First, it is proven that \(h({\mathcal X})\) always exists. The main result asserts that if the entropy is positive then it cannot be less than \(1/4\). In addition, all minimal classes with entropy \(1/4\) are described.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4528825)