Název: Fractionally Isomorphic Graphs and Graphons
Autoři: Hladký, Jan ; Hng, Eng Keat
Typ dokumentu: Příspěvky z konference
Konference/Akce: EUROCOMB 2023: European Conference on Combinatorics, Graph Theory and Applications /12./, Prague (CZ), 20230828
Rok: 2023
Jazyk: eng
Abstrakt: 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.
Klíčová slova: graph; graph fractional isomorphism; graphon
Číslo projektu: GX21-21762X
Poskytovatel projektu: GA ČR
Zdrojový dokument: EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications
Poznámka: Související webová stránka: https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-080

Instituce: Ústav informatiky AV ČR (web)
Informace o dostupnosti dokumentu: Dokument je dostupný v repozitáři Akademie věd.
Původní záznam: https://hdl.handle.net/11104/0351812

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-541564


Záznam je zařazen do těchto sbírek:
Věda a výzkum > AV ČR > Ústav informatiky
Konferenční materiály > Příspěvky z konference