Differential calculus on the space of countable labelled graphs
- PDF / 652,454 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 176 Views
(0123456789().,-volV)(0123456789().,-volV)
Tusi Mathematical Research Group
ORIGINAL PAPER
Differential calculus on the space of countable labelled graphs Apoorva Khare1,2
•
Bala Rajaratnam3,4
Received: 25 May 2020 / Accepted: 29 September 2020 Ó Tusi Mathematical Research Group (TMRG) 2020
Abstract The study of very large graphs is a prominent theme in modern-day mathematics. In this paper we develop a rigorous foundation for studying the space of finite labelled graphs and their limits. These limiting objects are naturally countable graphs, and the completed graph space GðVÞ is identified with the 2-adic integers as well as the Cantor set. The goal of this paper is to develop a model for differentiation on graph space in the spirit of the Newton–Leibnitz calculus. To this end, we first study the space of all finite labelled graphs and their limiting objects, and establish analogues of left-convergence, homomorphism densities, a Counting Lemma, and a large family of topologically equivalent metrics on labelled graph space. We then establish results akin to the First and Second Derivative Tests for real-valued functions on countable graphs, and completely classify the permutation automorphisms of graph space that preserve its topological and differential structures. Keywords Countable labelled graphs Graph limits Differential calculus First derivative test
Mathematics Subject Classification 05C63 28C10
Communicated by Mario Krnic. & Apoorva Khare [email protected] Bala Rajaratnam [email protected] 1
Department of Mathematics, Indian Institute of Science, Bangalore, India
2
Analysis & Probability Research Group, Bangalore, India
3
University of California, Davis, USA
4
University of Sydney (visiting), Sydney, Australia
A. Khare and B. Rajaratnam
1 Introduction Large amounts of modern data comes in the form of networks/graphs, as compared to standard discrete or continuous data that lives on the integers or the real line respectively. Thus, subjects like Erdo¨s–Re´nyi random graphs, finite (large) graphs and their limits have a vast number of applications—to social networks (e.g., friendship graph), the internet (and world-wide web), ecological and biological networks (such as the human brain), resistance networks and chip design among others. In recent times, these areas have become the subject of a large body of literature. An important feature of these networks is that they are always changing (increasing) with respect to time. Additional vertices and edges are being added to the network, which makes the study of large graphs and their limits—in a unified setting—a necessary and important subject. There are several significant strides that have been made in the literature. Prominent among them is the comprehensive, unifying theory developed by Borgs, Chayes, Lova´sz, Sos, Szegedy, Vesztergombi, and several others. In this (unlabelled) theory the space of graphons was introduced and studied; see, e.g., the comprehensive monograph [16] and the references therein for more on graphons. T
Data Loading...
