기초과학연구원 이산수학그룹
On November 26, 2024, Eng Keat Hng from the IBS Extremal Combinatorics and Probability Group gave a talk on characterizing fractionally isomorphic graphons in terms of the Galton-Watson branching process. The title of his talk was “Graphon branching processes and fractional isomorphism“.
In 2005, Bollobás, Janson and Riordan introduced and extensively studied a general model of inhomogeneous random graphs parametrised by graphons. In particular, they studied the emergence of a giant component in these inhomogeneous random graphs by relating them to a broad collection of inhomogeneous Galton-Watson branching processes.
Fractional isomorphism of finite graphs is an important and well-studied concept at the intersection of graph theory and combinatorial optimisation. 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.
In our work, we characterise inhomogeneous random graphs that yield the same inhomogeneous Galton-Watson branching process (and hence have a similar component structure).
This is joint work with Jan Hladký and Anna Margarethe Limbach.