Approximating fractionally isomorphic graphons

Eng Keat Hng

Czech Academy of Sciences

March 23, 2023, 12:20 in S6

Abstract

First introduced by Tinhofer in 1986, fractional isomorphism of finite graphs is an important and well-studied concept at the intersection of graph theory and combinatorial optimization. It has many different characterizations that involve a  range of very different and seemingly unrelated properties of graphs. Recently, Grebík and Rocha developed a theory of fractional isomorphism for graphons, i.e. limits of dense graph sequences, where they showed that every characterization of fractional isomorphism in graphs has a well-defined graphon counterpart and that these are indeed all equivalent characterizations of fractional isomorphism for graphons. They asked whether fractionally isomorphic graphons can be characterized as the limits of graph sequences which are entry-wise fractionally isomorphic (in the graph sense). We answer their question in the affirmative.

This is joint work with Jan Hladký.