OpenFrontiers
Join
← Back to the index
OP-2990OpenProbability

Asymptotic combinatorics and algebraic analysis · 1994-prob-205

Combinatorial probability · ICM 1994: Asymptotic combinatorics and algebraic analysis

MSC 60 · Probability theory and stochastic processes

Inferred from the community field; finer classification has not been reviewed.

Source assessment · not reviewedAs of 2026-08-18Source & evidence ↓
Read original source ↗ 0Submit progressLean 4 ↓Discussion (0)

Problem statement

Develop a systematic theory for the asymptotic behavior of probability measures on growing combinatorial objects. More precisely, let CnC_n be a finite or countable family of combinatorial objects of size nn, and let μn\mu_n be a probability measure on CnC_n, where the families under consideration include integer partitions, Young diagrams, configurations, Z≥0\mathbb{Z}_{\ge 0}-graded locally finite graphs (graphs whose vertices are partitioned into levels indexed by Z≥0\mathbb{Z}_{\ge 0}, with finitely many edges incident to each vertex), and higher-dimensional analogues of these objects. Formulate verifiable general criteria for choosing normalization or rescaling maps rn:Cn→Xr_n:C_n\to X into a single topological space XX, for establishing weak convergence of the pushforward measures (rn)#μn(r_n)_\#\mu_n, and for determining which of the following two cases occurs: the ergodic, or limit-shape, case, in which (rn)#μn(r_n)_\#\mu_n converges weakly to a Dirac measure δx\delta_x concentrated at one limiting object x∈Xx\in X; or the nonergodic case, in which (rn)#μn(r_n)_\#\mu_n converges weakly to a nondegenerate probability measure on XX.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗
Remaining questions in this record

Remaining questions recorded by the source

These are retained within the parent record and are not counted as additional index entries.

Question 1

For each n≥0n\geq 0, let P(n)\mathcal P(n) be the set of integer partitions of nn. For λ∈P(n)\lambda\in\mathcal P(n), let Rk(λ)R_k(\lambda) be the multiplicity of the part kk. Let gk,j≥0g_{k,j}\geq 0 for k≥1k\geq1 and j≥0j\geq0, with gk,0=1g_{k,0}=1, and suppose that

an:=∑λ∈P(n)∏k≥1gk,Rk(λ) a_n:=\sum_{\lambda\in\mathcal P(n)}\prod_{k\geq1}g_{k,R_k(\lambda)}

is positive for every nn. Define the multiplicative probability measure

μ(n)(λ)=1an∏k≥1gk,Rk(λ),λ∈P(n). \mu^{(n)}(\lambda)=\frac1{a_n}\prod_{k\geq1}g_{k,R_k(\lambda)},\qquad \lambda\in\mathcal P(n).

Characterize, by necessary and sufficient conditions on the weights gk,jg_{k,j}, when there exist positive scaling constants αn\alpha_n and a nonincreasing piecewise-continuous function φ:R≥0→R≥0\varphi:\mathbb R_{\geq0}\to\mathbb R_{\geq0} with ∫0∞φ(t) dt=1\int_0^\infty\varphi(t)\,dt=1 such that, for every finite collection of continuity points t1,…,tm>0t_1,\ldots,t_m>0 of φ\varphi,

(αnn∑k>αntiRk(λ))i=1m→n→∞μ(n)-probability(φ(ti))i=1m. \left(\frac{\alpha_n}{n}\sum_{k>\alpha_n t_i}R_k(\lambda)\right)_{i=1}^m \xrightarrow[n\to\infty]{\mu^{(n)}\text{-probability}} \bigl(\varphi(t_i)\bigr)_{i=1}^m.

In every case where such convergence holds, determine the scaling αn\alpha_n, up to multiplication by a sequence converging to a positive constant, and determine the limit shape φ\varphi.

Source reference: Yuri Yakubovich, "Ergodicity of Multiplicative Statistics," Journal of Combinatorial Theory, Series A 119 (2012), no. 6, 1250-1279, DOI: 10.1016/j.jcta.2012.03.002, arXiv:0901.4655.

Question 2

Let f(z)=∑j≥0gjzjf(z)=\sum_{j\geq0}g_jz^j be a power series with nonnegative coefficients, g0=1g_0=1, and g1>0g_1>0, whose radius of convergence is ρ∈(0,1)\rho\in(0,1), and suppose that ff has a pole at ρ\rho. Let b1=1b_1=1 and bk≥0b_k\geq0 for k≥2k\geq2, assume that every power series f(z)bk=∑j≥0gk,jzjf(z)^{b_k}=\sum_{j\geq0}g_{k,j}z^j has nonnegative coefficients, and suppose that

Bk:=∑j=1kbj=kβℓ(k), B_k:=\sum_{j=1}^k b_j=k^\beta\ell(k),

where β>0\beta>0 and ℓ\ell is slowly varying, meaning that ℓ(cx)/ℓ(x)→1\ell(cx)/\ell(x)\to1 as x→∞x\to\infty for every c>0c>0. Define

F(x):=∏k≥1f(xk)bk=∑n≥0anxn F(x):=\prod_{k\geq1}f(x^k)^{b_k}=\sum_{n\geq0}a_nx^n

and, for each nn, define a probability measure on the integer partitions P(n)\mathcal P(n) by

μ(n)(λ)=1an∏k≥1gk,Rk(λ), \mu^{(n)}(\lambda)=\frac1{a_n}\prod_{k\geq1}g_{k,R_k(\lambda)},

where Rk(λ)R_k(\lambda) is the multiplicity of the part kk in λ\lambda. For 0<x<ρ0<x<\rho, let μx\mu_x be the probability measure on all integer partitions satisfying

μx(P(n))=anxnF(x), \mu_x(\mathcal P(n))=\frac{a_nx^n}{F(x)},

and let xn∈(0,ρ)x_n\in(0,\rho) be the unique solution of xnF′(xn)/F(xn)=nx_nF'(x_n)/F(x_n)=n. Assume that there is a constant γ>0\gamma>0 such that μxn(P(n))≥n−γ\mu_{x_n}(\mathcal P(n))\geq n^{-\gamma} for all sufficiently large nn. Prove that, if λ\lambda is sampled from μ(n)\mu^{(n)}, then for every t>0t>0 with t≠1t\neq1,

1n∑k>tRk(λ)→n→∞P1[0,1](t). \frac1n\sum_{k>t}R_k(\lambda)\xrightarrow[n\to\infty]{\mathbb P}\mathbf 1_{[0,1]}(t).

Equivalently, prove that the scaling αn=1\alpha_n=1 gives the degenerate limit shape φ(t)=1[0,1](t)\varphi(t)=\mathbf 1_{[0,1]}(t).

Source reference: Yuri Yakubovich, "Ergodicity of Multiplicative Statistics," Journal of Combinatorial Theory, Series A 119 (2012), no. 6, 1250-1279, Conjecture 10, DOI: 10.1016/j.jcta.2012.03.002, arXiv:0901.4655.

Progress & source assessment

Source-reported assessment from the ICM catalogue snapshot. This is not an independent review by Frontier Science.

Unresolved.

No general theory in the literature covers the full scope of the statement. Existing criteria require substantial model-specific structure and do not, for an arbitrary sequence (Cn,μn)(C_n,\mu_n) in all the listed classes, select a common limit space and rescaling, prove weak convergence, and decide between a Dirac and a nondegenerate limit. In fact, even the much narrower problem of characterizing ergodicity for all multiplicative measures on ordinary integer partitions is explicitly described as open in the literature below.

Key evidence and partial progress:

  • Anatoly M. Vershik, "Asymptotic Combinatorics and Algebraic Analysis," in Proceedings of the International Congress of Mathematicians, Zurich 1994, Vol. II, Birkhauser, 1995, pp. 1384-1394. DOI: 10.1007/978-3-0348-9078-6_133. This is the source of the problem. It surveys limit-shape and nondegenerate-limit results for several specific measures, including uniform and Plancherel measures on partitions and the cycle-length measure of random permutations, but states that a systematic theory and general criteria for the two regimes are unknown.

  • Yuri Yakubovich, "Ergodicity of Multiplicative Statistics," Journal of Combinatorial Theory, Series A 119 (2012), no. 6, 1250-1279. DOI: 10.1016/j.jcta.2012.03.002; arXiv: 0901.4655. For multiplicative measures with partition function F(x)=∏k≥1f(xk)bkF(x)=\prod_{k\geq1}f(x^k)^{b_k} and regular-variation assumptions on (bk)(b_k), Theorem 6 gives an ergodicity criterion in the grand-canonical ensemble and Theorem 9 gives sufficient conditions for a deterministic limit shape in the conditioned ensemble. The paper calls this only a partial answer and says the multiplicative-measure question remains open in full generality.

  • Leonid V. Bogachev, "Unified Derivation of the Limit Shape for Multiplicative Ensembles of Random Integer Partitions with Equiweighted Parts," Random Structures & Algorithms 47 (2015), 227-266. DOI: 10.1002/rsa.20540; arXiv: 1111.3311. Under analytic hypotheses on a single factor F0F_0, this derives the scaling and deterministic limit shape for the equiweighted product class F(z)=∏ℓ≥1F0(zℓ)F(z)=\prod_{\ell\geq1}F_0(z^\ell), including examples from assemblies, multisets, and selections. It does not cover arbitrary multiplicative measures, nonmultiplicative measures, graded graphs, or higher-dimensional objects.

  • Jiaoyang Huang, "Law of Large Numbers and Central Limit Theorems through Jack Generating Functions," Advances in Mathematics 380 (2021), article 107545. DOI: 10.1016/j.aim.2020.107545; arXiv: 1807.09928. This gives equivalences between asymptotic conditions on germs of Jack generating functions and laws of large numbers or central limit theorems for the associated random particle systems. These are powerful general criteria inside a representation-theoretic class, but they do not apply to arbitrary probability measures or supply the universal rescaling framework requested here.

  • Anatoly M. Vershik, "Asymptotic Theory of Path Spaces of Graded Graphs and Its Applications," Japanese Journal of Mathematics 11 (2016), 151-218. DOI: 10.1007/s11537-016-1527-z; arXiv: 1604.03022. This develops intrinsic metrics and a standardness criterion for filtrations associated with graded graphs, explaining regular and nonstandard asymptotic behavior. It is a general framework for one listed object class, but it does not provide the statement's requested classification for arbitrary measures across all the listed classes.

Thus the literature contains extensive theories and complete answers for important subclasses, in both the limit-shape and nondegenerate regimes, but the common theory and exhaustive general criteria requested in the exact statement remain missing.

References
  1. [1]ICM Conjectures · 1994-prob-205 link
  2. [2]ICM 1994: Asymptotic combinatorics and algebraic analysis link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Sign in to run an attempt. New accounts start with enough credits for ten.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Sign in to add a note.