The expected number of pairwise stable networks: exact values, an nⁿ-term formula, and a one-inequality reduction of the limit question

Abstract

Herings, Seel and Predtetchinski (arXiv:2606.23440) consider n individuals whose utilities for the networks on them are independent atomless random variables, and the number sₙ of pairwise stable networks in the sense of Jackson and Wolinsky. They prove E(sₙ)=Σ_(g)1/Xₙ(g), a sum over all 2^(n(n-1)/2) networks of the reciprocal seniority degree, evaluate it to four decimals for n ≤ 7, call larger n impractical, prove √(e) ≤ liminfE(sₙ^*) ≤ limsupE(sₙ^*) ≤ e for the normalized sequence E(sₙ^*)=E(sₙ)/cₙ with cₙ=2^(n(n-1)/2)(2/(n+1))ⁿ, and leave open whether E(sₙ^*) converges and to what, noting that monotonicity would give L² convergence. We observe that a network is an orientation of the complete graph and that the seniority degree of i is one plus its out-degree, so the sum runs over tournaments and depends only on the score sequence—the enumeration MacMahon carried out in 1920—and that exact quadrature of the source's own integral formula turns the 2^(n(n-1)/2)-term sum into an nⁿ-term rational identity whose weights are the Adams–Moulton coefficients. This gives the exact rationals for n ≤ 7, each rounding to the printed decimal, the value E(s₈)=4206906030446363/1714608000000=2453.5672…, and, by the score-sequence recursion outside the formal development, exact values to n=14. All seven exactly known values of E(sₙ^*) are strictly increasing and lie strictly below √(e), the lower end of the bracket. We prove that the single inequality E(sₙ^*) ≤ √(e) for all n, together with the source's own asymptotic bracket, already forces E(sₙ^*) → √(e): the open question reduces to one inequality, monotonicity is not needed, and if the inequality persists the bracket collapses to its lower endpoint. Numerically n(√(e)-E(sₙ^*)) decreases to 0.79 at n=14. Two corrections to the source are recorded: there are 2²¹, not 2²⁸, networks on seven individuals, and two cells of its Table 3 are misprinted. The identities, the values for n ≤ 8, the comparisons and the reduction are verified in Lean 4 against Mathlib.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   b298807aa7a788599fdb5f7fb29127a000023bf11022a0a5bada020ceb48bf3f