Original title: Fractionally Isomorphic Graphs and Graphons
Authors: Hladký, Jan ; Hng, Eng Keat
Document type: Papers
Conference/Event: EUROCOMB 2023: European Conference on Combinatorics, Graph Theory and Applications /12./, Prague (CZ), 20230828
Year: 2023
Language: eng
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 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.
Keywords: graph; graph fractional isomorphism; graphon
Project no.: GX21-21762X
Funding provider: GA ČR
Host item entry: EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications
Note: Související webová stránka: https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-080

Institution: Institute of Computer Science AS ČR (web)
Document availability information: Fulltext is available in the digital repository of the Academy of Sciences.
Original record: https://hdl.handle.net/11104/0351812

Permalink: http://www.nusl.cz/ntk/nusl-541564


The record appears in these collections:
Research > Institutes ASCR > Institute of Computer Science
Conference materials > Papers