On the Typical Structure of Graphs in a Monotone Property

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 i...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2014-08, Vol.21 (3), p.P3.34
Main Authors: Janson, Svante, Uzzell, Andrew J.
Format: Article
Language:English
Subjects:
Graph limits
Monotone properties
Structure of graphs
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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.
ISSN:1077-8926
1097-1440
1077-8926
DOI:10.37236/4266