Remarks on Graphons

Attila Nagy

Published 2018-01-14Version 1

The notion of the graphon (a symmetric measurable fuzzy set of $[0, 1]^2$) was introduced by L. Lov\'asz and B. Szegedy in 2006 to describe limit objects of convergent sequences of dense graphs. In their investigation the integral \[t(F,W)=\int _{[0, 1]^k}\prod _{ij\in E(F)}W(x_i,x_j)dx_1dx_2\cdots dx_k\] plays an important role in which $W$ is a graphon and $E(F)$ denotes the set of all edges of a $k$-labelled simple graph $F$. In our present paper we show that the set of all fuzzy sets of $[0, 1]^2$ is a right regular band with respect to the operation $\circ$ defined by \[(f\circ g)(s,t)=\vee _{(x,y)\in [0, 1]^2}(f(x,y)\wedge g(s,t));\quad (s, t)\in [0, 1]^2,\] and the set of all graphons is a left ideal of this band. We prove that, if $W$ is an arbitrary graphon and $f$ is a fuzzy set of $[0, 1]^2$, then \[|t(F; W)-t(F; f\circ W)|\leq |E(F)|(\sup(W)-\sup(f))\Delta (\{W> \sup(f)\} )\] for arbitrary finite simple graphs $F$, where $\Delta (\{W> \sup(f)\})$ denotes the area of the set $\{W>\sup(f)\}$ of all $(x, y)\in [0, 1]^2$ satisfying $W(x,y)>\sup(f)$.