\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.34}{21(3)}{2014}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\hyphenation{graph-on graph-ons}

\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{}Z}

\newcommand{\CC}{\mathcal{C}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\labeled}{\mathcal{L}}
\def\P{\mathcal{P}}
\newcommand{\PP}{\mathcal{P}}
\newcommand{\Q}{\mathcal{P}}
\newcommand{\QQ}{\mathcal{P}}
\newcommand{\graphs}{\mathcal{U}}
\newcommand{\unlabeled}{\mathcal{U}}
\newcommand{\graphons}{\mathcal{W}}

\newcommand{\diff}{\mathrm{d}}

\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\deltacut}{\delta_{\square}}
\newcommand{\dcut}{d_{\square}}
\newcommand{\limitsx}[1]{\widehat{#1}}
\newcommand{\maxlimits}[1]{\widehat{#1}^*}

\DeclareMathOperator{\col}{col}
\DeclareMathOperator{\ind}{ind}
\DeclareMathOperator{\Ent}{Ent}
\DeclareMathOperator{\Forb}{Forb}
\DeclareMathOperator{\rand}{rand}
\newcommand{\tind}{t_{\ind}}
\newcommand{\tprod}[2]{\prod_{ij \in E(#1)} #2(x_i, x_j)}
\newcommand{\tindprod}[2]{\prod_{ij \in E(#1)} #2(x_i, x_j) \prod_{ij \notin E(#1)} \bigl(1 - #2(x_i, x_j)\bigr)}
\newcommand{\diffprod}[1]{\diff\mu(x_1) \cdots \diff\mu(x_{#1})}

\newcommand\bigpar[1]{\bigl(#1\bigr)}
\newcommand\Bigpar[1]{\Bigl(#1\Bigr)}
\newcommand\biggpar[1]{\biggl(#1\biggr)}
\newcommand\lrpar[1]{\left(#1\right)}
\newcommand\set[1]{\ensuremath{\{#1\}}}
\newcommand\bigset[1]{\ensuremath{\bigl\{#1\bigr\}}}
\newcommand\Bigset[1]{\ensuremath{\Bigl\{#1\Bigr\}}}
\newcommand\biggset[1]{\ensuremath{\biggl\{#1\biggr\}}}
\newcommand\lrset[1]{\ensuremath{\left\{#1\right\}}}
\newcommand\oi{[0,1]}
\newcommand\ooi{[0,1)}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

%opening
\title{\bf On the Typical Structure of Graphs\\ in a Monotone Property}

\author{Svante Janson\thanks{Partly supported by the Knut and Alice Wallenberg Foundation.} \qquad Andrew J. Uzzell\thanks{Supported by the Knut and Alice Wallenberg Foundation.}\\
\small Department of Mathematics\\[-0.8ex]
\small Uppsala University\\[-0.8ex]
\small P.O.~Box 480\\[-0.8ex]
\small SE-751 06 Uppsala, Sweden\\[-0.8ex]
\small\tt \{svante.janson,andrew.uzzell\}@math.uu.se
}

\date{\dateline{Apr 9, 2014}{Aug 20, 2014}{Aug 28, 2014}\\
\small Mathematics Subject Classifications: 05C75, 05C80, 05C30}

\begin{document}

\maketitle

\vspace*{-2ex}
\begin{abstract}
Given a graph property $\P$, it is interesting to determine the typical structure of graphs that satisfy $\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 $\P$ is a monotone property and $r$ is the largest integer for which every $r$-colorable graph satisfies $\P$, then almost every graph with~$\P$ is close to being a balanced $r$-partite graph.

\bigskip\noindent \textbf{Keywords:} Graph limits; Monotone properties; Structure of graphs
\end{abstract}

\section{Introduction and main results}\label{se:intro}

Given a graph property~$\P$, it is natural to study the structure of a typical graph that satisfies $\P$.  A graph property is \emph{monotone} if it is closed under taking subgraphs and \emph{hereditary} if it is closed under taking induced subgraphs.  Thus, every monotone property is also hereditary.  Many authors have studied the structure of typical graphs in various hereditary properties---see, e.g.,~\cite{ABBM11,BBS09,EFR86,EKR76,HJS,JUstring}, as well as the survey~\cite{Bol07}. In this note, we use results from graph limit theory to study the structure of a typical graph in a general monotone property.

Before stating our main result, let us recall certain basic notions of graph limit theory.  For more details, see, e.g., \cite{BCLSV1,DJ08,LS06}, as well as the monograph~\cite{LovaszBook}.  Here, we simply recall that certain sequences of graphs are defined to be \emph{convergent}.  A convergent sequence has a limit, called a \emph{graph limit}, which is unique if it exists.

Lov\'asz and Szegedy~\cite{LS06} showed that a graph limit~$\Gamma$ may be represented by a \emph{graphon}, a symmetric, measurable function~$W : \oi^2 \to \oi$.  (So, abusing notation slightly, we will sometimes write $G_n \to W$ if the sequence $\set{G_n}_{n = 1}^{\infty}$ converges to the graph limit~$\Gamma$ represented by $W$.)  More than one graphon may represent the same graph limit; we say that the graphons $W_1$ and~$W_2$ are \emph{equivalent}, and write $W_1 \cong W_2$, if they represent the same graph limit.

Let $X_1$, $X_2, \dots$ be i.i.d.~uniformly distributed random variables in $\oi$.  Given a graphon $W$, the \emph{$W$-random graph} $G(n, W)$ is a graph with vertex set~$[n]$ in which vertices $i$ and~$j$ are adjacent with probability~$W(X_i, X_j)$, independently of all other edges.

Let $h(x) = -x \log_2(x) - (1 - x)\log_2(1 - x)$ denote the binary entropy function.  The \emph{entropy} of a graphon~$W$ is
\[
\Ent(W) = \int_0^1 \int_0^1 h\bigl(W(x,y)\bigr) \, \diff\mu(x)\diff\mu(y),
\]
where $\mu$ denotes the Lebesgue measure.  As noted in~\cite{HJS}, if $W_1 \cong W_2$, then $\Ent(W_1) = \Ent(W_2)$.  In other words, entropy is a property of a graph limit, rather than of the graphon that represents it.  Thus, we may define the entropy~$\Ent(\Gamma)$ of a graph limit~$\Gamma$ to be the entropy of any graphon that represents it.

Hatami, Janson, and Szegedy~\cite{HJS} posed the question of which graphons may arise as limits of sequences of graphs with a given property~$\P$.  In addition to the intrinsic interest of this question, it turns out that if $\P$ is hereditary, then certain limits of sequences of graphs in $\P$ (namely, those with maximum entropy) give a great deal of information about the number and typical structure of graphs in~$\P$. (We do not distinguish between a graph property and the class of graphs with that property.)  In order to state these results, we need to introduce more notation.

Let $\graphs_n$ denote the set of unlabeled graphs on $n$ vertices and let $\labeled_n$ denote the set of labeled graphs with vertex set~$[n]$.  Given a graph property~$\P$, we let $\P_n = \P \cap \graphs_n$ denote the set of unlabeled elements of~$\P$ with $n$ vertices and let $\P^L_n$ denote the set of labeled elements of~$\P$ with vertex set~$[n]$.  The function $n \mapsto \abs{\P_n}$ is called the (unlabeled) \emph{speed} of~$\P$; the labeled speed is defined similarly.  Observe that
\begin{equation}\label{eq:labeledunlabeled}
\bigl\lvert \P_n \bigr\rvert \leq \bigl\lvert \P^L_n \bigr\rvert \leq n! \bigl\lvert \P_n \bigr\rvert.
\end{equation}

Given a graph property~$\P$, we let $\limitsx{\P}$
%= \overline{\P} \cap \limitsx{\graphs}$
denote the set of graph limits of sequences in $\P$.  We furthermore let $\maxlimits{\P}$ denote the set of elements of $\limitsx{\P}$ of maximum entropy, i.e.,
\[
\maxlimits{\P} = \biggl\{\Gamma \in \limitsx{\P} \, : \, \Ent(\Gamma) = \max_{\Gamma' \in \limitsx{\P}} \Ent(\Gamma')\biggr\}.
\]
We will also use these symbols to refer to the set of graphons (respectively, the set of maximum-entropy graphons) representing limits of sequences in $\P$.  It is shown in~\cite{HJS} that if $\Q$ is hereditary (and not finite), then $\max_{\Gamma \in \limitsx{\Q}} \Ent(\Gamma)$ is achieved---in other words, $\maxlimits{\Q}$ is nonempty.

In~\cite[Theorem 1.6]{HJS}, Hatami, Janson, and Szegedy showed that if a hereditary property~$\P$ has a single graph limit~$\Gamma$ of maximum entropy, then a typical element of~$\P$ is close to~$\Gamma$ (in terms of the standard cut metric on the space of graph limits).

\begin{theorem}\label{th:problimit}
Suppose that $\Q$ is a hereditary property and that $\max_{\Gamma \in \limitsx{\Q}} \Ent(\Gamma)$ is attained by a unique graph limit~$\Gamma_{\Q}$.  Then
\begin{enumerate}
\item[(i)] if $G_n \in \unlabeled_n$ is a uniformly random unlabeled element of~$\Q_n$, then $G_n$ converges in probability to~$\Gamma_{\Q}$ as $n \to \infty$;
\item[(ii)] if $G_n \in \labeled_n$ is a uniformly random labeled element of~$\Q^L_n$, then $G_n$ converges in probability to~$\Gamma_{\Q}$ as $n \to \infty$.
\end{enumerate}
\end{theorem}

Now we define a special class of graphons.  All of these graphons will be defined on $\ooi^2$, rather than on $\oi^2$; it is easy to see that this change is immaterial. Given $r \in \N$ and $i \in [r]$, let $I_i = [(i - 1)/r, i/r)$ and let $E_r = \cup_{i \neq j} I_i \times I_j$.  We also let $E_{\infty} = \ooi^2$.  Given $r \in \N \cup \set{\infty}$, we let $R_r$ denote the set of graphons $W$ such that $W(x, y) = 1/2$ if $(x, y) \in E_r$ and $W(x, y) \in \set{0, 1}$ otherwise.  It is easy to see that if $W \in R_r$, then
\[
\Ent(W) = \iint_{E_r} h(1/2)\, \diff\mu(x)\diff\mu(y) = \mu(E_r) = 1  - \dfrac{1}{r}.
\]
For $r \in \N$ and $0 \leq s \leq r$, we let $W^*_{r,s}$ denote the graphon in $R_r$ that equals~$1$ on $I_i \times I_i$ for $i \leq s$ and equals~$0$ on $I_i \times I_i$ for $s + 1 \leq i \leq r$.  Observe that $R_{\infty}$ consists only of the graphon that equals~$1/2$ everywhere on $\ooi^2$; for notational convenience, we denote this graphon by $W^*_{\infty, 0}$.

Given $r \in \N$ and $0 \leq s \leq r$, we let $\CC(r, s)$ denote the class of graphs whose vertex sets can be partitioned into $s$ (possibly empty) cliques and $r - s$ (possibly empty) independent sets.  In particular, $\CC(r, 0)$ is the class of $r$-colorable graphs.  Observe that for each $r$ and~$s$, the class~$\CC(r,s)$ is hereditary, and that $\CC(r, 0)$ is monotone.

It is shown in~\cite[Theorem 1.9]{HJS} that if $\P$ is a hereditary property, then the maximum entropy of an element of~$\limitsx{\P}$ takes one of countably many values, and furthermore that this value determines the asymptotic speed of~$\P_n$.

\begin{theorem}\label{th:speedlimit}
If $\P$ is a hereditary property, then there exists $r \in \N \cup \set{\infty}$ such that  $\max_{\Gamma \in \limitsx{\P}} \Ent(\Gamma) = 1 - 1/r$ and such that every graph limit $\Gamma \in \maxlimits{\P}$ can be represented by a graphon~$W \in R_r$.  Moreover,
\begin{equation*}\label{eq:speedlimit}
\abs{\P_n} = 2^{\bigl(1 - \frac{1}{r} + o(1) \bigr) \binom{n}{2}}.
\end{equation*}
\end{theorem}

Given a graph~$F$, we say that a graph~$G$ is \emph{$F$-free} if no subgraph of~$G$ is isomorphic to~$F$.  Given a (possibly infinite) family of graphs~$\F$, we say that $G$ is \emph{$\F$-free} if it is $F$-free for every $F \in \F$.  Observe that for any family~$\F$, the class of $\F$-free graphs is monotone.  (Conversely, every monotone class $\P$ equals the class of $\F$-free graphs for some family~$\F$---for example, $\F = \graphs \setminus \P$.)  We write $\Forb(\F)$ for the class of $\F$-free graphs and write $\Forb(F)$ when $\F = \set{F}$.  Note in particular that $\Forb(\emptyset)$ equals the class of all unlabeled finite graphs, which we denote by $\graphs$.

The \emph{coloring number} of a family of graphs~$\F$ is
\[
	\col(\F) = \min_{F \in \F} \chi(F).
\]
In particular, we define
\begin{equation}\label{eq:emptycolnumber}
\col(\emptyset) = \infty.
\end{equation}
Our main result says that if $\col(\F) = r + 1$, then a typical element of~$\Forb(\F)$ resembles a balanced $r$-partite graph in which cross-edges are present independently with probability~$1/2$.

\begin{theorem}\label{th:Ffreelimit}
Let $\F$ be a family of graphs and let $r = \col(\F) - 1$.  If $\P = \Forb(\F)$, then as $n$ tends to~$\infty$, a sequence of uniformly random unlabeled (respectively, labeled) elements of~$\P_n$ (respectively, elements of~$\P^L_n$) converges in probability to the graph limit~$\Gamma_r$ represented by $W^*_{r, 0}$.
\end{theorem}

Note that the quantity~$r$ in the statement of the theorem also equals the largest integer~$t$ for which every $t$-colorable graph is in $\Forb(\F)$.

It follows from Theorems \ref{th:speedlimit} and~\ref{th:Ffreelimit} that if $\col(\F) = r + 1$ then
\begin{equation}\label{eq:ForbFspeed}
\bigl\lvert \Forb(\F)_n \bigr\rvert = 2^{\bigl(1 - \frac{1}{r} + o(1) \bigr) \binom{n}{2}},
\end{equation}
which was first shown in~\cite{EFR86}. Let us also note that Balogh, Bollob\'as, and Simonovits~\cite{BBS04} obtained a fairly sharp bound on the error term in~\eqref{eq:ForbFspeed}.

\begin{remark}
The proof of Theorem~\ref{th:Ffreelimit} shows that if $r = \col(\F) - 1$ and $\P = \Forb(\F)$, then $W^*_{r,0}$ is the unique maximum-entropy element of~$\limitsx{\P}$.  For certain families~$\F$, it is also possible to describe the set of all $\F$-free graph limits.  For example, the set of limits of bipartite graphs is determined in~\cite[Example 2.1]{HJS}, and a very similar argument holds for $r$-partite graphs when $r \geq 3$.  However, we know of no representation of the set of all $\F$-free graph limits for arbitrary $\F$.
\end{remark}

\begin{remark}
Erd\H{o}s, Frankl, and R\"{o}dl~\cite{EFR86} showed that if $\chi(F) = r + 1$, then every $F$-free graph $G$ may be made $K_{r+1}$-free by removing $o(n^2)$ edges from $G$.  This result is similar in spirit to Theorem~\ref{th:Ffreelimit}, but we see no direct implication: if $\set{G_n}_{n = 1}^{\infty}$ is a sequence of uniformly random $F$-free graphs and $\set{G'_n}_{n = 1}^{\infty}$ is the sequence of resulting $K_{r+1}$-free graphs, then the distribution of $G'_n$ need not be uniform in $\Forb(K_{r+1})_n$.
\end{remark}

\begin{remark}
Theorem~\ref{th:Ffreelimit} says that if $\col(\F) = r + 1$ then almost every (labeled or unlabeled) $\F$-free graph is close to a balanced $r$-partite graph.  (Conversely, every $r$-partite graph is trivially $\F$-free.) In the case of labeled graphs, Pr\"{o}mel and Steger~\cite{PS92} proved a much stronger result for a specific class of monotone properties: they characterized the graphs~$F$ for which almost every labeled $F$-free graph \emph{is} $(\chi(F) - 1)$-partite.  Given a graph~$F$, we say that $e \in E(F)$ is \emph{critical} if $\chi(F - e) < \chi(F)$.  Pr\"{o}mel and Steger showed that if $\chi(F) = r + 1$ then
\[
\bigl\lvert \Forb(F)^L_n \bigr\rvert = \bigl(1 + o(1)\bigr) \bigl\lvert \CC(r, 0)^L_n \bigr\rvert
\]
if and only if $F$ contains a critical edge.  They also showed that if $F$ does not contain a critical edge, then there exists a constant~$c_r > 0$ not depending on~$F$ such that
\begin{equation}\label{eq:nocriticaledge}
\bigl\lvert \Forb(F)^L_n \bigr\rvert \geq c_r n \bigl\lvert \CC(r, 0)^L_n \bigr\rvert
\end{equation}
for all $n$~sufficiently large.  Theorem~\ref{th:Ffreelimit} shows that if $\F$ is any family of graphs with $\col(\F) = r + 1$, then $\Forb(\F)^L$ and $\CC(r, 0)^L$ have roughly the same asymptotic speed.  Note that this result does not contradict~\eqref{eq:nocriticaledge} when $\F = \{F\}$ and $F$ does not contain a critical edge: if $\chi(F) = r + 1$, then, in view of \eqref{eq:labeledunlabeled} and  \eqref{eq:ForbFspeed}, Theorem~\ref{th:Ffreelimit} implies the weaker statement that $\abs{\Forb(F)^L_n}$ and $\abs{\CC(r, 0)^L_n}$ differ by a factor of~$2^{o(n^2)}$.
\end{remark}




\section{Proof of Theorem \ref{th:Ffreelimit}}\label{se:proof}

\begin{lemma}\label{le:monotonicity}
Let $\Q$ be a monotone property and let $W \in \limitsx{\Q}$.  If $W'$ is a graphon such that $W' \leq W$ pointwise, then $W' \in \limitsx{\Q}$.
\end{lemma}

\begin{proof}
Consider the sequences of random graphs $\{G(n, W)\}_{n=1}^{\infty}$ and~$\{G(n, W')\}_{n=1}^{\infty}$.  Since $W' \leq W$ pointwise, a standard argument shows that the two sequences can be coupled so that for each~$n$, $G(n, W') \subseteq G(n, W)$ almost surely.  It is shown in~\cite[Theorem 3.1]{Jan13b} that if $W \in \limitsx{\Q}$ then, for each $n$, $G(n, W) \in \Q$ almost surely.  It follows that for each $n$, we almost surely have $G(n, W') \in \Q$, as well.  Finally, it is shown in~\cite[Theorem 4.5]{BCLSV1} that $G(n, W') \to W'$ almost surely as $n \to \infty$, which implies that $W' \in \limitsx{\Q}$, as claimed.
\end{proof}

Now we prove our main result, Theorem~\ref{th:Ffreelimit}.

\begin{proof}[Proof of Theorem~\ref{th:Ffreelimit}.]
We begin by showing that, up to equivalence of graphons, $\limitsx{\P}$ contains a unique element of maximum entropy.  By Theorem~\ref{th:speedlimit}, there exists~$t \in \N \cup \set{\infty}$ such that $\maxlimits{\P} \subseteq R_t$ up to equivalence of graphons.

First, suppose that $t < \infty$.  Observe that if $W \in \maxlimits{\P} \cap R_t$, then $W \geq W^*_{t,0}$ pointwise, which by Lemma~\ref{le:monotonicity} implies that $W^*_{t,0} \in \maxlimits{\P}$.  We claim that, up to equivalence of graphons, $W^*_{t,0}$ is in fact the only maximum-entropy element of~$\limitsx{\P}$.  Indeed, let $W' \in \maxlimits{\P} \cap R_t$ and suppose that $\mu(W' = 1) > 0$.  But then Lemma~\ref{le:monotonicity} implies that $\min\{W', 1/2\}$ is a graphon in $\limitsx{\P}$ with entropy strictly larger than~$1 - 1/t$, which contradicts the definition of~$t$.

Now we show that $t = \col(\F) - 1 = r$.  Suppose that $t < \infty$.  It is observed in~\cite[Remark 1.10]{HJS} that if $\P$ is hereditary and $0 \leq s \leq r < \infty$, then $W^*_{r,s} \in \limitsx{\P}$ if and only if $\CC(r, s) \subseteq \P$.  By the definition of~$\col(\F)$, it is easy to see that if $u \leq r$, then $\CC(u, 0) \subseteq \P$ and hence $W^*_{u,0} \in \limitsx{\P}$.  On the other hand, $\F$ contains some element of~$\CC(r + 1, 0)$, which implies that $\CC(r + 1, 0) \nsubseteq \P$.  This implies that $W^*_{u,0} \notin \limitsx{\P}$ when $u \geq r + 1$, and hence that $t = r$.

If $t = \infty$, then we claim that $\P = \Forb(\emptyset) = \graphs$; the conclusion then follows from~\eqref{eq:emptycolnumber}.  Suppose to the contrary that $\P$ does not contain some graph~$F$.  Then $\CC(\chi(F), 0) \nsubseteq \P$, which implies that $W^*_{\chi(F), 0} \notin \limitsx{\P}$.  However, $W^*_{\chi(F), 0} \leq W^*_{\infty, 0}$ pointwise, so Lemma~\ref{le:monotonicity} implies that $W^*_{\infty, 0} \notin \limitsx{\P}$, which is a contradiction.

Finally, since $\P$ is a hereditary property, it follows from Theorem~\ref{th:problimit} that a uniformly random (labeled or unlabeled) element of~$\P$ converges in probability to~$\Gamma_r$, as claimed.
\end{proof}

%\bibliographystyle{plain}
%\bibliography{graphlimitsbib}

\begin{thebibliography}{10}

\bibitem{ABBM11}
N.~Alon, J.~Balogh, B.~Bollob{\'a}s, and R.~Morris.
\newblock The structure of almost all graphs in a hereditary property.
\newblock {\em J. Combin. Theory Ser. B}, 101(2):85--110, 2011.

\bibitem{BBS04}
J.~Balogh, B.~Bollob{\'a}s, and M.~Simonovits.
\newblock The number of graphs without forbidden subgraphs.
\newblock {\em J. Combin. Theory Ser. B}, 91(1):1--24, 2004.

\bibitem{BBS09}
J.~Balogh, B.~Bollob{\'a}s, and M.~Simonovits.
\newblock The typical structure of graphs without given excluded subgraphs.
\newblock {\em Random Structures Algorithms}, 34(3):305--318, 2009.

\bibitem{Bol07}
B.~Bollob{\'a}s.
\newblock Hereditary and monotone properties of combinatorial structures.
\newblock In {\em Surveys in {C}ombinatorics 2007}, volume 346 of {\em London
  Math. Soc. Lecture Note Ser.}, pages 1--39. Cambridge Univ. Press, Cambridge,
  2007.

\bibitem{BCLSV1}
C.~Borgs, J.T. Chayes, L.~Lov{\'a}sz, V.T. S{\'o}s, and K.~Vesztergombi.
\newblock Convergent sequences of dense graphs {I}: Subgraph frequencies,
  metric properties and testing.
\newblock {\em Adv. Math.}, 219(6):1801--1851, 2008.

\bibitem{DJ08}
P.~Diaconis and S.~Janson.
\newblock Graph limits and exchangeable random graphs.
\newblock {\em Rend. Mat. Appl. (7)}, 28(1):33--61, 2008.

\bibitem{EFR86}
P.~Erd{\H{o}}s, P.~Frankl, and V.~R{\"{o}}dl.
\newblock The asymptotic number of graphs not containing a fixed subgraph and a
  problem for hypergraphs having no exponent.
\newblock {\em Graphs Combin.}, 2(1):113--121, 1986.

\bibitem{EKR76}
P.~Erd{\H{o}}s, D.J. Kleitman, and B.L. Rothschild.
\newblock Asymptotic enumeration of {$K_{n}$}-free graphs.
\newblock In {\em Colloquio {I}nternazionale sulle {T}eorie {C}ombinatorie
  ({R}ome, 1973), {T}omo {II}}, pages 19--27. Atti dei Convegni Lincei, No. 17.
  Accad. Naz. Lincei, Rome, 1976.

\bibitem{HJS}
H.~Hatami, S.~Janson, and B.~Szegedy.
\newblock Graph properties, graph limits, and entropy.
\newblock Preprint, \arxiv{1312.5626}, 2013.

\bibitem{Jan13b}
S.~Janson.
\newblock Graph limits and hereditary properties.
\newblock {\em European J. Combin.}, to appear.

\bibitem{JUstring}
S.~Janson and A.J. Uzzell.
\newblock On string graph limits and the structure of a typical string graph.
\newblock Preprint, \arxiv{1403.2911}, 2014.

\bibitem{LovaszBook}
L.~Lov{\'a}sz.
\newblock {\em Large networks and graph limits}, volume~60 of {\em Amer. Math.
  Soc. Colloq. Publ.}
\newblock Amer. Math. Soc., Providence, RI, 2012.

\bibitem{LS06}
L.~Lov{\'a}sz and B.~Szegedy.
\newblock Limits of dense graph sequences.
\newblock {\em J. Combin. Theory Ser. B}, 96(6):933--957, 2006.

\bibitem{PS92}
H.J. Pr{\"o}mel and A.~Steger.
\newblock The asymptotic number of graphs not containing a fixed color-critical
  subgraph.
\newblock {\em Combinatorica}, 12(4):463--473, 1992.

\end{thebibliography}


\end{document}