Fractionally Isomorphic Graphs and Graphons

0583814 - ÚI 2024 RIV CZ eng C - Konferenční příspěvek (zahraniční konf.)
Hladký, Jan - Hng, Eng Keat
Fractionally Isomorphic Graphs and Graphons.
EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications. Brno: MUNI Press, 2023 - (Kráľ, D.; Nešetřil, J.), s. 579-586. E-ISSN 2788-3116.
[EUROCOMB 2023: European Conference on Combinatorics, Graph Theory and Applications /12./. Prague (CZ), 28.08.2023-01.09.2023]
Grant CEP: GA ČR(CZ) GX21-21762X
Institucionální podpora: RVO:67985807
Klíčová slova: graph * graphon * graph fractional isomorphism
Obor OECD: Pure mathematics
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-080

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 two sequences of graphs that are fractionally isomorphic converge to two graphons, then these graphons are fractionally isomorphism. Answering the main question from ibid, we prove the converse of the statement above: If we have two fractionally isomorphic graphons, then there exist sequences of graphs that are fractionally isomorphic converge and converge to these respective graphons. As an easy but convenient corollary of our methods, we get that every regular graphon can be approximated by regular graphs.
Trvalý link: https://hdl.handle.net/11104/0351812