A graphon perspective for fractional isomorphism

0508686 - ÚI 2020 RIV SK eng J - Journal Article
Grebík, Jan - Rocha, Israel
A graphon perspective for fractional isomorphism.
Acta Mathematica Universitatis Comenianae. Roč. 88, č. 3 (2019), s. 759-765. ISSN 0231-6986.
[EUROCOMB 2019. European Conference on Combinatorics, Graph Theory and Applications /9./. Bratislava, 26.08.2019-30.08.2019]
R&D Projects: GA ČR GJ16-07822Y
Institutional support: RVO:67985807
Keywords : fractional isomorphism * graphons * doubly stochastic operators * measure disintegration theorem
OECD category: Pure mathematics
Method of publishing: Open access
http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1236/724

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.
Permanent Link: http://hdl.handle.net/11104/0299523