Graphon Colourings and Limits of Graph Partitions
Abstract
We develop a framework for pure and mixed graphon colourings and use it to study the limiting behaviour of graph partition parameters under cut convergence. Pure colourings correspond to measurable partitions, while mixed colourings assign a probability distribution on the colour set to each point. We develop the representation, equivalence and convergence theory, and show that every mixed graphon colouring has an equivalent pure representative, possibly on a different probability space. For each fixed finite colour set, we establish compactness and describe the topology of coloured graph limits using the cut norm on graphons and the weak-* topology on colourings. The usual coloured cut distance characterises convergence for pure colourings, but not for general mixed colourings. As applications, we prove that the Cheeger constant and modularity converge to their mixed graphon counterparts along cut-convergent graph sequences whose orders tend to infinity, assuming uniformly linear minimum degree and positive limiting edge density, respectively. Both mixed functionals are invariant under graphon equivalence. We also establish their continuity in cut distance on the corresponding classes of graphons, with a stability bound for the Cheeger constant. For modularity, we further characterise coloured graphons attaining extremal modularity values and prove attainment of the mixed optimum for each fixed number of colours. We also exhibit a graphon whose modularity supremum is not attained by any finite colouring.
Related
- Monochromatic cycle partitions in 3-mean edge-colourings
- Bounds for Unions of Several Parts in Balanced Graph Partitions
- Nonlocal-to-local variational limits of energies on partitions
- Graph Models of Cultural M-Grams: Polygonal Number Networks, Topological Index Partitions, and Geometric Transformations
- Additive Quasi-isometry via rooted graph partitions and layering partition
BibTeX
@misc{janson2026graphon,
title = {{Graphon Colourings and Limits of Graph Partitions}},
author = {Svante Janson and Tiffany Y. Y. Lo and Colin McDiarmid and Anda Skeja and Fiona Skerman},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38599},
eprint = {2610.38599},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38599},
}
RIS
TY - UNPB
TI - Graphon Colourings and Limits of Graph Partitions
AU - Svante Janson
AU - Tiffany Y. Y. Lo
AU - Colin McDiarmid
AU - Anda Skeja
AU - Fiona Skerman
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38599
UR - https://arxiv.org/abs/2610.38599
AB - We develop a framework for pure and mixed graphon colourings and use it to study the limiting behaviour of graph partition parameters under cut convergence. Pure colourings correspond to measurable partitions, while mixed colourings assign a probability distribution on the colour set to each point. We develop the representation, equivalence and convergence theory, and show that every mixed graphon colouring has an equivalent pure representative, possibly on a different probability space. For each fixed finite colour set, we establish compactness and describe the topology of coloured graph limits using the cut norm on graphons and the weak-* topology on colourings. The usual coloured cut distance characterises convergence for pure colourings, but not for general mixed colourings. As applications, we prove that the Cheeger constant and modularity converge to their mixed graphon counterparts along cut-convergent graph sequences whose orders tend to infinity, assuming uniformly linear minimum degree and positive limiting edge density, respectively. Both mixed functionals are invariant under graphon equivalence. We also establish their continuity in cut distance on the corresponding classes of graphons, with a stability bound for the Cheeger constant. For modularity, we further characterise coloured graphons attaining extremal modularity values and prove attainment of the mixed optimum for each fixed number of colours. We also exhibit a graphon whose modularity supremum is not attained by any finite colouring.
ER -