graphons

Graphons are mathematical objects used to study the structure of large, dense graphs. Introduced by Lovász and Szegedy in 2006, graphons provide a way to represent the limit of a sequence of dense graphs, capturing their asymptotic behavior. They are defined as measurable functions W: [0,1]² → [0,1], where the value W(x,y) represents the probability of an edge between vertices corresponding to x and y in the limit graph.

Graphons can be used to define a distance between graphs, known as the cut distance, which measures the difference in edge densities between two graphs. This distance is useful in graph theory and related fields, as it allows for the comparison of large, complex graphs.

There are several ways to construct graphons, including from random graphs, regular graphs, and other graph families. Graphons can also be used to study graph limits, which are the limits of sequences of graphs under certain convergence criteria. These limits can be used to study the asymptotic behavior of graphs, such as their connectivity, spectral properties, and other structural features.

Graphons have applications in various fields, including computer science, social network analysis, and biology. In computer science, graphons can be used to study the structure of large-scale networks, such as the internet or social media platforms. In social network analysis, graphons can be used to model the structure of social networks and study their evolution over time. In biology, graphons can be used to study the structure of biological networks, such as protein-protein interaction networks or metabolic networks.