Measures on monotone properties of graphs (Q5957296): Difference between revisions

A monotone property \({\mathcal P}\) is one that is closed under isomorphism and under taking subgraphs. The graphs of \({\mathcal P}\) with vertex set \([n]\) will be denoted by \({\mathcal P}_n\). Various enumeration measures of monotone properties are investigated. In particular, results on the speed of \({\mathcal P}\), which is \(|{\mathcal P}_n|\), the number of graphs in \({\mathcal P}_n\), and the size, which is the maximum number of edges in a graph of \({\mathcal P}_n\) and is denoted by \(e_{{\mathcal P}}(n)\), are proved. For example it is shown that \({\mathcal P}\) has polynomial speed if and and only if the size \(e_{\mathcal P}(n)\) is bounded, and the speed of \({\mathcal P}\) is exponential in \(n\) implies the size \(e_{{\mathcal P}}(n)\) is linear in \(n\). Many other results involving properties with exponential and superfactorial sizes are proved. Although a complete picture of the speed and size of monotone properties is not determined, very significant progress is made and the general outline is there.