Finitely forcible graphons
From MaRDI portal
Publication:2275893
DOI10.1016/J.JCTB.2011.03.005zbMATH Open1223.05248arXiv0901.0929OpenAlexW1970138544MaRDI QIDQ2275893FDOQ2275893
Authors: Balázs Szegedy, László Lovász 
Publication date: 10 August 2011
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Abstract: We investigate families of graphs and graphons (graph limits) that are defined by a finite number of prescribed subgraph densities. Our main focus is the case when the family contains only one element, i.e., a unique structure is forced by finitely many subgraph densities. Generalizing results of Turan, Erdos-Simonovits and Chung-Graham-Wilson, we construct numerous finitely forcible graphons. Most of these fall into two categories: one type has an algebraic structure and the other type has an iterated (fractal-like) structure. We also give some necessary conditions for forcibility, which imply that finitely forcible graphons are "rare", and exhibit simple and explicit non-forcible graphons.
Full work available at URL: https://arxiv.org/abs/0901.0929
Recommendations
- Finitely forcible graphons with an almost arbitrary structure
- Finitely forcible graphons and permutons
- Infinite-dimensional finitely forcible graphon
- Compactness and finite forcibility of graphons
- Extremal graph theory and finite forcibility
- Complete forcing numbers of graphs
- Finitely forcible graph limits are universal
- On the forcing dimension of a graph
- On the total forcing number of a graph
- scientific article; zbMATH DE number 1814846
Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Structural characterization of families of graphs (05C75)
Cites Work
- Limits of dense graph sequences
- Moments of two-variable functions and the uniqueness of graph limits
- Counting graph homomorphisms
- Title not available (Why is that?)
- Graph Classes: A Survey
- Flag algebras
- Title not available (Why is that?)
- Complement reducible graphs
- Generalized quasirandom graphs
- Quasi-random graphs
- Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
- Quick approximation to matrices and applications
- Szemerédi's lemma for the analyst
- Supersaturated graphs and hypergraphs
- Regularity partitions and the topology of graphons
- On the Minimal Density of Triangles in Graphs
- Title not available (Why is that?)
- Contractors and connectors of graph algebras
- Threshold graph limits and random threshold graphs
- Extreme Points of Vector Functions
- On extreme points of convex sets
Cited In (31)
- Semantic limits of dense combinatorial objects
- Limits of kernel operators and the spectral regularity lemma
- Decomposition of tournament limits
- Quasi-random words and limits of word sequences
- From quasirandom graphs to graph limits and graphlets
- Typical large graphs with given edge and triangle densities
- Differential calculus on graphon space
- On a question of Vera T. Sós about size forcing of graphons
- On the density of a graph and its blowup
- Subgraph densities in Markov spaces
- Graph limits and hereditary properties
- Finitely forcible graphons with an almost arbitrary structure
- Graphon convergence of random cographs
- Weak regularity and finitely forcible graph limits
- Weak regularity and finitely forcible graph limits
- Existence of a symmetric bipodal phase in the edge-triangle model
- The phases of large networks with edge and triangle constraints
- Forcing generalised quasirandom graphs efficiently
- Modularity spectra, eigen-subspaces, and structure of weighted graphs
- Finitely forcible graphons and permutons
- Finitely forcible graph limits are universal
- Extremal graph theory and finite forcibility
- Quasirandom Latin squares
- Higher-order fluctuations in dense random graph models
- Infinite-dimensional finitely forcible graphon
- Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics
- Singularities in the entropy of asymptotically large simple graphs
- Multipodal structure and phase transitions in large constrained graphs
- Phase transitions in finite random networks
- Compactness and finite forcibility of graphons
- Quasirandom permutations are characterized by 4-point densities
This page was built for publication: Finitely forcible graphons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275893)
