Fractionally Isomorphic Graphs and Graphons

EUROCOMB’23

Jan Hladký Eng Keat Hng

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-080

PDF
Abstract
Fractional isomorphism is a well-studied relaxation of graph isomorphism with a very rich theory. Grebík and Rocha [Combinatorica 42, pp 365-404 (2022)] developed a concept of fractional isomorphism for graphons and proved that it enjoys an analogous theory. In particular, they proved that if $G_1,G_2,\ldots$ converge to a graphon $U$, $H_1,H_2,\ldots$ converge to a graphon $W$ and each $G_i$ is fractionally isomorphic to $H_i$, then $U$ is fractionally isomorphic to $W$. Answering the main question from ibid, we prove the converse of the statement above: If $U$ and $W$ are fractionally isomorphic graphons, then there exist sequences of graphs $G_1,G_2,\ldots$ and $H_1,H_2,\ldots$ which converge to $U$ and $W$ respectively and for which each $G_i$ is fractionally isomorphic to $H_i$. As an easy but convenient corollary of our methods, we get that every regular graphon can be approximated by regular graphs.

Pages:
579–586
References

H. Dell, M. Grohe, and G. Rattan. Lovász meets Weisfeiler and Leman. In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 40, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018.

Z. Dvořák. On recognizing graphs by numbers of homomorphisms. J. Graph Theory, 64(4):330-342, 2010.
https://doi.org/10.1002/jgt.20461

J. Grebík and I. Rocha. A graphon perspective for fractional isomorphism. Acta Math. Univ. Comenian. (N.S.), 88(3):759-765, 2019.

J. Grebík and I. Rocha. Fractional isomorphism of graphons. Combinatorica, 42(3):365-404, 2022.
https://doi.org/10.1007/s00493-021-4336-9

L. Lovász. Large networks and graph limits, volume 60 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2012.
https://doi.org/10.1090/coll/060

M. V. Ramana, E. R. Scheinerman, and D. Ullman. Fractional isomorphism of graphs. Discrete Math., 132(1-3):247-265, 1994.
https://doi.org/10.1016/0012-365X(94)90241-0

G. Tinhofer. Graph isomorphism and theorems of Birkhoff type. Computing, 36(4):285-300, 1986.
https://doi.org/10.1007/BF02240204

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Jan Hladký, Eng Keat Hng

PDF