Regularity Partitions and The Topology of Graphons

By L. Lov'asz, Balázs Szegedy. 2010

124 citations recorded by the source corpus.

Dedicated to Endre Szemeredi on the occasion of his 70th birthday In this paper we highlight a topological aspect of the graph limit theory. 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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/731052451ea442c3c234e5c6c14d44300232bc9f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Regularity lemma for distal structures (2015, background): “(2) [27] Graphs of bounded VC-dimension: density arbitrarily close to 0 or 1, the size of the partition is bounded by a polynomial in (”
A semi-algebraic version of Zarankiewicz's problem (2014, methodology): “We note that a weaker result, namely |F| ≤ O ( m/δ ) d log d ( m/δ ) , can be obtained with a more simple proof using epsilon-nets (see [30] or [29]).”
Graphons, cut norm and distance, couplings and rearrangements (2010, background): “C O ] 3 J un 2”
INVARIANT MEASURES CONCENTRATED ON COUNTABLE STRUCTURES (2012, background): “(See also the simple arrays of [Kal99] and 0 – 1 valued graphons in [LS10].)”