On the typical structure of graphs in a monotone property (Q740672): Difference between revisions

Summary: Given a graph property \(\mathcal{P}\), it is interesting to determine the typical structure of graphs that satisfy \(\mathcal{P}\). In this paper, we consider monotone properties, that is, properties that are closed under taking subgraphs. Using results from the theory of graph limits, we show that if \(\mathcal{P}\) is a monotone property and \(r\) is the largest integer for which every \(r\)-colorable graph satisfies \(\mathcal{P}\), then almost every graph with \(\mathcal{P}\) is close to being a balanced \(r\)-partite graph.