Abstract
Nešetřil and Ossona de Mendez introduced the notion of first order convergence as an attempt to unify the notions of convergence for sparse and dense graphs. It is known that there exist first order convergent sequences of graphs with no limit modeling (an analytic representation of the limit). On the positive side, every first order convergent sequence of trees or graphs with no long path (graphs with bounded tree-depth) has a limit modeling. We strengthen these results by showing that every first order convergent sequence of plane trees (trees with embeddings in the plane) and every first order convergent sequence of graphs with bounded path-width has a limit modeling.
Introduction
In the study of combinatorics and graph theory, understanding the behavior of graph sequences as they grow infinitely large is a fundamental challenge. For "dense" graphs, where the number of edges is proportional to the square of the number of vertices, the theory of graphons provides a robust analytic framework. For "sparse" graphs, Benjamini-Schramm convergence offers a way to describe local limits. However, a more ambitious and unified framework was proposed by Jaroslav Nešetřil and Patrice Ossona de Mendez: first-order (FO) convergence.
In this framework, a sequence of graphs converges if the probability that any given first-order logic formula is true for a random set of vertices stabilizes. The ultimate goal of this research is to identify a "limit modeling"—an analytic object that serves as the infinite representation of the sequence. While it is conjectured that all nowhere-dense graph classes (a broad category of sparse graphs) possess such limits, this has proven difficult to demonstrate. This paper provides a significant breakthrough by proving the existence of limit modelings for two complex structures: plane trees and graphs with bounded path-width.
Theoretical Framework: FO Convergence and Limit Modelings
First-order convergence is based on the idea that the logical properties of a graph should stabilize as the graph grows. A sequence of graphs $(G_n)$ is FO-convergent if for every first-order formula $\phi$, the probability that $\phi$ holds for a tuple of vertices chosen uniformly at random from $G_n$ converges to a limit.
A limit modeling is a Borel structure that captures these limiting probabilities. While previous research established that sequences with bounded tree-depth (graphs lacking long paths) have limit modelings, extending this to more flexible structures like general trees or graphs with cycles remained an open problem. This paper bridges that gap by focusing on the structural properties of plane trees and the topological constraints of path-width.
Methodology
The authors utilize a two-stage strategy involving logical decomposition and interpretation schemes to establish their results.
1. Hintikka Chains and Stone Measures
To analyze the FO properties of graph sequences, the researchers employ Hintikka chains. These are sequences of formulas that describe the local neighborhood of a vertex in increasing detail. By identifying "$\varepsilon$-major nodes"—vertices that are logically "close" to a significant portion of the graph—the authors define Stone measures. These measures map the distribution of logical types across the graph, providing a way to track how structural properties behave in the limit.
2. Interpretation Schemes
A core innovation of the paper is the use of FO-interpretations to translate complex graphs into simpler ones. The authors demonstrate that graphs with bounded path-width can be encoded into colored plane trees.
- First, they prove that every FO-convergent sequence of plane trees (trees with a fixed cyclic order of neighbors) has a limit modeling.
- Second, they use an interpretation scheme to show that if the encoded tree sequence has a limit, the original graph sequence with bounded path-width must also possess a limit modeling.
Key Insights and Results
The Role of Plane Trees
Unlike standard trees, plane trees include an embedding in the plane, which provides a fixed cyclic order for neighbors at each vertex. This additional structural information provides the necessary logical "hooks" to describe more complex relationships. The authors prove (Theorem 1) that every FO-convergent sequence of plane trees has a limit modeling that satisfies the strong finitary mass transport principle. This principle ensures the limit object behaves physically, preventing mathematical anomalies where small sets of vertices are disproportionately matched to large sets.
Path-width as a Milestone
Bounded path-width represents a significant step beyond previous results. While bounded tree-depth forbids long paths, bounded path-width allows for them, as well as cycles and more intricate internal structures. By proving that every FO-convergent sequence of graphs with bounded path-width has a limit modeling (Theorem 14), the authors provide the first proof for a truly "non-trivial" class of graphs in the context of the limit modeling conjecture.
Conclusion and Future Work
This research significantly advances the field of graph limit theory by providing a constructive mapping ($t_A$) that translates interval representations of graphs into colored plane trees. This proves that path-width is FO-interpretable within the world of trees.
Despite these gains, the ultimate goal remains the proof of Conjecture 1: that every nowhere-dense class of graphs (including all minor-closed classes like planar graphs) has a limit modeling. While bounded path-width is a subset of bounded tree-width and planar graphs, the decomposition techniques and Stone measures developed here provide the foundational tools necessary to eventually tackle these broader, more complex sparse graph categories.
Summary updated