Project Graph limits and beyond

Overview

An "EXPRO project" funded by the Czech Science Foundation for the period January 2021-December 2025, the project "Graph limits and beyond" aims to advance understanding of limits of discrete structures (and dense and sparse graph limits in particular) and make connections to areas such as additive combinatorics and property testing. The project is hosted by the Institute of Computer Science of the Czech Academy of Sciences.

We have vivid collaboration with other researchers at the Institute, in particular with Matas Sileikis, and their students and postdocs. For the full list of members in these groups, see here.

Team members

Papers stemming from the project

Frederik Garbe, Fan Wei: A Characterization for spectral and trace positivity of matrix words
[arXiv].

Jan Hladký, Petr Savický: Inhomogeneous random 2-SAT
[arXiv].

Jan Hladký, Petr Savický: Digraphons: connectivity and spectral aspects
[arXiv].

Jan Hladký, Daniel Iĺkovič, Jared León, Xichao Shu: On cospectral graphons
Electronic Journal of Combinatorics, Volume 33, Issue 1, P1.10, [arXiv], [published].

Frederik Garbe, Jan Hladký: A tower lower bound for the degree relaxation of the Regularity Lemma
Combinatorial Theory 5 (4), paper number 8, [arXiv], [published].

Jan Hladký, Eng Keat Hng, Anna Margarethe Limbach: Graphon branching processes and fractional isomorphism
[arXiv]. Accepted to Annales de l’Institut Henri Poincaré (B) Probabilités et Statistiques

Jan Hladký, Gopal Viswanathan: Random minimum spanning tree and dense graph limits
Random Structures and Algoritms, Volume 68, Issue 2, e70053, [arXiv], [published].

Eng Keat Hng: Characterization of flip process rules with the same trajectories
SIAM Journal on Discrete Mathematics,, Volulme 40, Issue 2 (2026), [arXiv], [published]

Jan Hladký, Gopal Viswanathan: Connectivity of inhomogeneous random graphs II
Random Structures and Algorithms volume 69, issue 2, e70098, [arXiv], [published].

Frederik Garbe, Jan Hladký, Gábor Kun, Kristýna Pekárková: On pattern-avoiding permutons
Random Structures and Algorithms, volume 65, pages 46-60; [arXiv], [published]. [Here] is an identical copy of the published paper available as open access.

Anna Margarethe Limbach, Martin Winter: When Do Graph Covers Preserve the Clique Dynamics of Infinite Graphs?
Matemática Contemporânea 2025, [arXiv], [published].

Frederik Garbe, Jan Hladký, Matas Šileikis, Fiona Skerman: From flip processes to dynamical systems on graphons
Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques, volume 60 (4), pages 2878-2922, [arXiv], [published]. [video]

Jan Hladký, Eng Keat Hng: Approximating fractionally isomorphic graphons
European Journal of Combinatorics, volume 113, 103751; [arXiv], [published]. [Extended abstract] appeared in the proceedings of Eurocomb 2023

Pedro Araújo, Jan Hladký, Eng Keat Hng, Matas Šileikis: Prominent examples of flip processes
Random Structures and Algorithms, volume 64, pages 692-740; [arXiv], [published]

Eng Keat Hng, Domenico Mergoni Cecchelli: Density of small diameter subgraphs in Kr-free graphs
[arXiv].

Jan Hladký, Hanka Řada: Permutation flip processes
At this moment only as an [extended abstract] in the proceedings of Eurocomb 2023.

Environmental and climate sustainability

Team members are encouraged to seek environmentally friendly ways of collaboration.

Practical

The code of the grant according the Czech Science Foundation (GACR) is 21-21762X. The internal grant number of the Institute of Computer Science is 412.