Differential calculus on graphon space

DOI10.1016/J.JCTA.2015.02.006MaRDI QIDQ2347882zbMATH OpenOpenAlexFDO

Authors Peter Diao, Dominique Guillot, Apoorva Khare, Bala Rajaratnam

Publication date 10 June 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.3736

zbMATH Keywords

consistency constraintsdifferential calculusgraph limitsgraphonGâteaux derivativehomomorphism densitiesquantum algebrassmooth graphon parameterTaylor series

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: Recently, the theory of dense graph limits has received attention from multiple disciplines including graph theory, computer science, statistical physics, probability, statistics, and group theory. In this paper we initiate the study of the general structure of differentiable graphon parameters $F$. We derive consistency conditions among the higher G^ateaux derivatives of $F$ when restricted to the subspace of edge weighted graphs $$. Surprisingly, these constraints are rigid enough to imply that the multilinear functionals $$ satisfying the constraints are determined by a finite set of constants indexed by isomorphism classes of multigraphs with $n$ edges and no isolated vertices. Using this structure theory, we explain the central role that homomorphism densities play in the analysis of graphons, by way of a new combinatorial interpretation of their derivatives. In particular, homomorphism densities serve as the monomials in a polynomial algebra that can be used to approximate differential graphon parameters as Taylor polynomials. These ideas are summarized by our main theorem, which asserts that homomorphism densities $t(H,-)$ where $H$ has at most $N$ edges form a basis for the space of smooth graphon parameters whose $(N+1)$st derivatives vanish. As a consequence of this theory, we also extend and derive new proofs of linear independence of multigraph homomorphism densities, and characterize homomorphism densities. In addition, we develop a theory of series expansions, including Taylor's theorem for graph parameters and a uniqueness principle for series. We use this theory to analyze questions raised by Lov'asz, including studying infinite quantum algebras and the connection between right- and left-homomorphism densities.

Recommendations

• On derivatives of graphon parameters
• Limits of dense graph sequences
• Differential calculus on the space of countable labelled graphs
• Random graphons and a weak positivstellensatz for graphs
• Moments of two-variable functions and the uniqueness of graph limits

Cites work

• A correlation inequality for bipartite graphs
• A measure-theoretic approach to the theory of dense hypergraphs
• A nonparametric view of network models and Newman–Girvan and other modularities
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• Estimating and understanding exponential random graph models
• Exchangeability and continuum limits of discrete random structures
• Finite graphs and amenability
• Finitely forcible graphons
• Graph limits and exchangeable random graphs
• Graph norms and Sidorenko's conjecture
• scientific article; zbMATH DE number 3722700 (Why is no real title available?)
• scientific article; zbMATH DE number 3780300 (Why is no real title available?)
• scientific article; zbMATH DE number 3238721 (Why is no real title available?)
• Interval graph limits
• Large deviations for random matrices
• Large networks and graph limits
• Limits of dense graph sequences
• Methods of geometric analysis in extension and trace problems. Vol. 1
• Moments of two-variable functions and the uniqueness of graph limits
• Spectral clustering and the high-dimensional stochastic blockmodel
• Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture
• Szemerédi's lemma for the analyst
• Testability and repair of hereditary hypergraph properties
• Testing properties of graphs and functions
• The coloring of graphs
• The large deviation principle for the Erdős-Rényi random graph
• The universal Urysohn space, Gromov metric triples and random metrics on the natural numbers

Cited in

(9)

• Ensemble equivalence for dense graphs
• The analytic evolution of Dyson-Schwinger equations via homomorphism densities
• Differential calculus on the space of countable labelled graphs
• Graphon-valued stochastic processes from population genetics
• A measure theoretic perspective on the space of Feynman diagrams
• On derivatives of graphon parameters
• Breaking of ensemble equivalence for dense random graphs under a single constraint
• Continuum graph dynamics via population dynamics: well-posedness, duality and equilibria
• The grapheme-valued Wright-Fisher diffusion with mutation

This page was built for publication: Differential calculus on graphon space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2347882)