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.
@article{10_37236_4266,
author = {Svante Janson and Andrew J. Uzzell},
title = {On the typical structure of graphs in a monotone property},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {3},
doi = {10.37236/4266},
zbl = {1298.05273},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4266/}
}
TY - JOUR
AU - Svante Janson
AU - Andrew J. Uzzell
TI - On the typical structure of graphs in a monotone property
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/4266/
DO - 10.37236/4266
ID - 10_37236_4266
ER -
%0 Journal Article
%A Svante Janson
%A Andrew J. Uzzell
%T On the typical structure of graphs in a monotone property
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/4266/
%R 10.37236/4266
%F 10_37236_4266
Svante Janson; Andrew J. Uzzell. On the typical structure of graphs in a monotone property. The electronic journal of combinatorics, Tome 21 (2014) no. 3. doi: 10.37236/4266
