A logical approach to concentration

Michael Benedikt, Maksim ZhukovskiiarXiv 2026 · DOI · arXiv

TL;DR

This paper introduces a powerful "meta-theorem" for random graph theory by bridging mathematical logic and probability. The authors define a real-valued logic capable of expressing complex graph properties (like subgraph counts and maximum degrees) and prove that any property definable in this language is guaranteed to concentrate—meaning its value stays remarkably close to its average—in Erdős-Rényi random graphs.

What Problem Does This Paper Address?

In the study of random graphs, researchers often want to know if a specific characteristic (like the number of triangles or the maximum degree) is "predictable." Formally, they look for concentration of measure: does the random variable stay close to its expected value as the graph grows larger?

Traditionally, proving concentration for a new graph function required bespoke, often difficult probabilistic proofs using tools like Kim-Vu polynomial concentration or Martingale inequalities. There was no general "rule of thumb" to say, "If you can describe your function in this specific way, it is guaranteed to concentrate."

This paper provides that missing framework. It moves beyond classical "zero-one laws" (which only deal with True/False properties) into the realm of real-valued functions, providing a unified logical language for concentration.

Methods

The authors develop a new logical framework called Aggregate Real-Valued Logic ($Agg_{\mathcal{F}}$).

  1. The Language: The logic starts with basic building blocks (constants, edge relations, equality) and builds complexity using:
  2. Aggregate Operators: Summation ($\Sigma$), global/local averaging (Avg), and Maximum/Minimum (Max/Min).
  3. Connective Functions: Real-valued functions that act like Boolean "AND/OR" but for numbers.
  4. Relative Lipschitz Functions: A key technical contribution is the definition of "Relative Lipschitz" functions. The authors show that standard Lipschitz continuity isn't enough to preserve concentration when you allow summation; instead, the function's sensitivity must scale relative to the magnitude of its inputs.
  5. Inductive Approximation: The core proof technique involves showing that any complex term in this logic can be approximated by simpler "atomic types" (in dense graphs) or "closure types" (in sparse graphs). They prove that these approximations stabilize as the number of vertices $n$ goes to infinity.

Datasets

As a theoretical mathematics and computer science paper, it does not use empirical datasets. Instead, it evaluates its logic on the Erdős-Rényi random graph model $G(n, p)$:

  • Dense Case: Where the probability of an edge $p$ is a constant.
  • Sparse Case: Where $p = n^{-\alpha}$ for an irrational $\alpha \in (0, 1)$.

The choice of irrational $\alpha$ is crucial; it is well-known in logic that for rational $\alpha$, even simple first-order properties fail to converge, making concentration impossible.

Key Insights and Ideas

  • Logic as a Meta-Theorem: Instead of proving concentration for one function at a time, the authors prove it for an entire language. If your graph function is expressible in $Agg_{\mathcal{F}}$, the concentration proof is now "free."
  • Summation is the Game Changer: Previous real-valued logics focused on averages (which stay bounded). By adding summation, the authors allow the logic to express "counting" properties (like the total number of triangles), which scale with the size of the graph.
  • The "Closure" Concept in Sparse Graphs: In sparse graphs, most vertices look the same (isolated). The authors use the concept of a "closure"—a small set of vertices forced into existence by dense local structures—to show that even in sparse environments, the logic can find enough structure to prove concentration.
  • Subsuming Classical Laws: The results are powerful enough to imply the classical FO zero-one laws of Fagin (dense) and Shelah-Spencer (sparse) as simple special cases.

Key Results

  • Universal Concentration: Every closed term in the defined logic concentrates around its mean in both dense and sparse (irrational $\alpha$) Erdős-Rényi graphs.
  • Asymptotic Predictability: For a specific class of "asymptotically polynomial" connectives, the authors show that the expected value of a term $\tau$ behaves predictably as $E[\tau] \approx c \cdot n^\gamma$ for some constants $c$ and $\gamma$.
  • Application to Known Statistics: The paper demonstrates that the logic can express (and thus prove concentration for) subgraph counts and maximum extension counts, matching the "right" order of magnitude for second-order terms found in previous literature.

Limitations and Future Work

  • The Rational Gap: The results do not hold for sparse graphs where $\alpha$ is rational. In these "threshold" regimes, graph properties often oscillate or behave erratically, and the authors acknowledge this is a fundamental limit of the logical approach.
  • Linear Sparsity: The case of $p = c/n$ (very sparse graphs) is not covered. This regime is particularly interesting for studying the "giant component" and other phase transitions.
  • Higher-Order Logics: The logic is "first-order" in nature. It cannot express properties like "is the graph connected?" or "is the graph 3-colorable?" (which require Monadic Second-Order logic). While concentration is known for some of these properties (like chromatic number), a general logical law for them remains an open challenge.
  • Optimality: While the framework proves concentration, it doesn't always provide the tightest possible bounds (e.g., exact constant factors in the error terms) compared to a proof specifically engineered for a single statistic.

Summary updated

Abstract

Concentration results say that a sequence of random variables becomes progressively concentrated around the mean. Such results are common in the study of functions of random graphs. We introduce a real-valued logic with various aggregate operators on graphs, including summation, and prove that every term in the language, seen as a random variable on random graphs within the classical Erdős-Rényi random graph model, is concentrated. We prove this for dense and sparse variants of Erdős-Rényi graphs. On the one hand, our results extend the line of work originating with Fagin and Glebskii et al. on zero-one laws for dense random graphs, as well as the zero-one law of Shelah and Spencer for sparse random graphs. On the other hand, they can be seen as a meta-theorem for inferring concentration results on random graphs, and we give examples of such applications.
BibTeX
@misc{benedikt2026logical,
  author = {Michael Benedikt and Maksim Zhukovskii},
  title = {{A logical approach to concentration}},
  year = {2026},
  eprint = {2602.17752},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.17752},
}
Figure