Abstract
We work out the theory of fractional isomorphism of graphons as a generalization to the classical theory of fractional isomorphism of finite graphs. The generalization is given in terms of homomorphism densities of finite trees and it is characterized in terms of distributions on iterated degree measures, Markov operators, weak isomorphism of a conditional expectation with respect to invariant sub-σ-algebras and isomorphism of certain quotients of given graphons.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. Babai, P. Erdős and S. Selkow: Random graph isomorphism, SIAM Journal on Computing. 9 (1980), 628–635.
L. Babai: Graph Isomorphism in Quasipolynomial Time, arXiv:1512.03547.
P. Billingsley: Probability and Measure, Third edition, Wiley, 1995.
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós and K. Vesztergombi: Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing, Adv. Math. 219 (2008), 1801–1851.
C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós and K. Vesztergombi: Convergent sequences of dense graphs II, Multiway cuts and statistical physics, Ann. Math. 176 (2012), 151–219.
H. Dell, M. Grohe and G. Rattan: Lovász meets Weisfeiler and Leman, in: 45th International Colloquium on Automata, Languages, and Programming, ICALP, Prague, Czech Republic, 2018, 40:1–40:14.
Z. Dvořák: On recognizing graphs by numbers of homomorphisms, J. Graph Theory 64 (2010), 330–342.
T. Eisner, B. Farkas, M. Haase and R. Nagel: Operator Theoretic Aspects of Ergodic Theory, Graduate Texts in Mathematics, Springer International Publishing, 2015.
J. Grebík and I. Rocha: A graphon perspective for fractional isomorphism, Acta Math. Univ. Comenian. (N.S.) 88 (2019), 759–765.
J. Hladký and I. Rocha: Independent sets, cliques, and colorings in graphons, European J. Combin. 88 (2020), 103108.
J. Hladký, P. Hu and D. Piguet: Tilings in graphons, European J. Combin. 93 (2021), 103284.
A. S. Kechris: Classical Descriptive Set Theory, Graduate texts in mathematics, Springer-Verlag, 1995.
D. Kerr and H. Li: Independence and Dichotomies, Springer Monographs in Mathematics, Springer International Publishing, 2016.
L. Lovász: Operations with structures, Acta Mathematica Hungarica 18 (1967), 321–328.
L. Lovász and B. Szegedy: Limits of dense graph sequences, J. Combin. Theory Ser. B 96 (2006), 933–957.
L. Lovász: Large Networks and Graph Limits., volume 60 of Colloquium Publications, American Mathematical Society, 2012.
M. Ramana, E. Scheinerman and D. Ullman: Fractional isomorphism of graphs, Discrete Mathematics 132 (1994), 247–265.
W. Rudin: Functional Analysis, McGraw-Hill, New York 1973.
W. Rudin: Principles of mathematical analysis, Third edition, International Series in Pure and Applied Mathematics, McGraw-Hill, New York-Auckland-Düsseldorf, 1976.
W. Rudin: Real and Complex Analysis, McGraw-Hill, New York 1987.
E. Scheinerman and D. Ullman: Fractional Graph Theory, A Rational Approach to the Theory of Graphs.
G. Tinhofer: Graph isomorphism and theorems of Birkhoff type, Computing 36 (1986), 285–300.
G. Tinhofer: A note on compact graphs, Discrete Applied Mathematics 30 (1991), 253–264.
Acknowledgments
The authors are grateful to Jan Hladky for useful discussions and help, and to anonymous referees for many useful suggestions and comments that helped to improve the presentation of the paper. The first author also thanks Jan Bydžovský, Jan Hladký and Oleg Pikhurko for help with the current version of the introduction.
Author information
Authors and Affiliations
Corresponding author
Additional information
Grebík was supported by the Czech Science Foundation, grant number GJ16-07822Y, by the grant GAUK 900119 of Charles University and by Leverhulme Research Project Grant RPG-2018-424. Part of the work was done while Grebík was affiliated with Institute of Computer Science of the Czech Academy of Sciences, with institutional support RVO:67985807.
Rocha was supported by the Czech Science Foundation, grant number GJ16-07822Y and GA19-08740S. With institutional support RVO:67985807.