Fractionally Isomorphic Graphs and Graphons

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F23%3A00583814" target="_blank" >RIV/67985807:_____/23:00583814 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-080" target="_blank" >https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-080</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-080" target="_blank" >10.5817/CZ.MUNI.EUROCOMB23-080</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Fractionally Isomorphic Graphs and Graphons

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Fractionally Isomorphic Graphs and Graphons

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GX21-21762X" target="_blank" >GX21-21762X: Limity grafů a související obory</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2023

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

EUROCOMB’23. Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications

ISBN

—

ISSN

2788-3116

e-ISSN

2788-3116

Počet stran výsledku

8

Strana od-do

579-586

Název nakladatele

MUNI Press

Místo vydání

Brno

Místo konání akce

Prague

Datum konání akce

28. 8. 2023

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—