{
  "id": "1002.4377",
  "version": "v1",
  "published": "2010-02-23T17:38:44.000Z",
  "updated": "2010-02-23T17:38:44.000Z",
  "title": "Regularity partitions and the topology of graphons",
  "authors": [
    "László Lovász",
    "Balázs Szegedy"
  ],
  "comment": "25 pages",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We highlight a topological aspect of the graph limit theory. Graphons are limit objects for convergent sequences of dense graphs. We introduce the representation of a graphon on a unique metric space and we relate the dimension of this metric space to the size of regularity partitions. We prove that if a graphon has an excluded induced sub-bigraph then the underlying metric space is compact and has finite packing dimension. It implies in particular that such graphons have regularity partitions of polynomial size.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-02-23T17:38:44.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C99",
      "60B05"
    ],
    "keywords": [
      "regularity partitions",
      "graph limit theory",
      "unique metric space",
      "finite packing dimension",
      "limit objects"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 25,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1002.4377L"
    }
  }
}