Regularity partitions and the topology of graphons
From MaRDI portal
Publication:3078210
zbMATH Open1242.05188arXiv1002.4377MaRDI QIDQ3078210FDOQ3078210
Publication date: 18 February 2011
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.
Full work available at URL: https://arxiv.org/abs/1002.4377
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)
Cited In (44)
- Regularity lemmas for stable graphs
- Quantitative structure of stable sets in arbitrary finite groups
- Regular partitions of gentle graphs
- Regular decomposition of the edge set of a graph with applications
- Limits of kernel operators and the spectral regularity lemma
- Decomposition of tournament limits
- Compact graphings
- Structure and regularity for subsets of groups with finite VC-dimension
- Impartial digraphs
- The automorphism group of a graphon
- Efficient Removal Lemmas for Matrices
- From quasirandom graphs to graph limits and graphlets
- A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth
- Identifiability for Graphexes and the Weak Kernel Metric
- Approximate equivalence relations
- Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem
- Minimum degree and the graph removal lemma
- The removal lemma for tournaments
- Vapnik-Chervonenkis density in some theories without the independence property. I
- Graph limits and hereditary properties
- On the Descriptive Power of Probability Logic
- DOMINATION AND REGULARITY
- Asymptotic Structure for the Clique Density Theorem
- First-order limits, an analytical perspective
- A classification of orbits admitting a unique invariant measure
- An improved bound for regular decompositions of 3-uniform hypergraphs of bounded \(\mathrm{VC}_2\)-dimension
- Model theory and agnostic online learning via excellent sets
- Strongly polynomial sequences as interpretations
- The VC dimension of quadratic residues in finite fields
- Cycles of a given length in tournaments
- EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES
- Nondegenerate spheres in four dimensions
- A semi-algebraic version of Zarankiewicz's problem
- Efficient removal lemmas for matrices
- Linear embeddings of graphs and graph limits
- The Cut Metric for Probability Distributions
- Interval graph limits
- Limits of structures and the example of tree semi-lattices
- NOTES ON THE STABLE REGULARITY LEMMA
- Matching polytons
- Finitely forcible graphons
- Compactness and finite forcibility of graphons
- Erdős-Hajnal conjecture for graphs with bounded VC-dimension
- Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition
This page was built for publication: Regularity partitions and the topology of graphons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3078210)
