scientific article; zbMATH DE number 1099508

From MaRDI portal
Publication:4369478





A class \(X\) of graphs is called hereditary if each subgraph of an element of \(X\) belongs to \(X\). Let \(X_n\) be the set of graphs in \(X\) whose vertices are labelled with \(1,2,\dots ,n\). It is known that, for every infinite hereditary class \(X\) different from the class of all graphs, the equation \(\log_2|X_n|=\bigl( 1-\frac 1{c(X)}\bigr) \frac{n^2}2+o(n^2)\) holds, where \(c(X)\) is a natural number [see \textit{V. E. Alekseev}, Diskretn. Mat. 4, No. 2, 148-157 (1992; Zbl 0766.05088) and \textit{V. E. Alekseev}, Discrete Math. Appl. 3, No. 2, 191-199 (1993; Zbl 0797.05077)]. The set of hereditary classes \(X\) such that \(c(X)=1\) is called a unitary layer. In the article, the lowest four levels of the unitary layer are studied for which the order of magnitude of \(\log_2|X_n|\) is one of the following: 1, \(\log_2 n\), \(n\), or \(n\log_2 n\). It is shown that no intermediate type of behavior can exist. The first three levels are described completely and all minimal elements are found for all the four levels.











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 Q4369478)