A graphon perspective for fractional isomorphism

Main Article Content

Jan Grebík Israel Rocha


Fractional isomorphism of graphs plays an important role in practical applications of graph isomorphism test by means of the color refinement algorithm. We introduce a suitable generalization to the space of graphons in terms of Markov opertors on a Hilbert space, provide characterizations in terms of a push-forward of the graphon to a quotient space and also in terms of measurable partitions of the underlying space. Our proofs
use a weak version of the mean ergodic theorem, and correspondences between objects such as Markov projections, sub-$\sigma$-algebras, measurable decompositions, etc. That also provides an alternative proof for the characterizations of fractional isomorphism of graphs without the use of Birkhoff\textendash von Neumann Theorem.

Article Details

How to Cite
Grebík, J., & Rocha, I. (2019). A graphon perspective for fractional isomorphism. Acta Mathematica Universitatis Comenianae, 88(3), 759-765. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1236/724