arbiter
JournalsAccount

Perfect partitions of a random set of integers

Boris Pittel

Journal of Applied Probability2026https://doi.org/10.1017/jpr.2026.10086preprint
AJG 2ABDC A
Weight
0.50

Abstract

Let $X_1,\ldots, X_n$ be independent integers distributed uniformly on [ M ], $M\ge 2$ . A partition S of [ n ] into $\nu$ non-empty subsets $S_1,\ldots, S_{\nu}$ is called perfect if all $\nu$ values $\sum_{j\in S_{\alpha}}X_j$ are equal. For a perfect partition to exist, $\sum_j X_j$ has to be divisible by $\nu$ . In 2001, for $\nu=2$ , Christian Borgs, Jennifer Chayes, and the author proved that, conditioned on $\sum_j X_j$ being even, with high probability a perfect partition exists if $\kappa\;:\!=\; \lim {{n}/{\log M}}>{{1}/{\log 2}}$ , and that with high probability no perfect partition exists if $\kappa {{2(\nu-1)}/{\log[(1-2\nu^{-2})^{-1}]}}$ the total number of perfect partitions is exponentially high with probability $\gtrsim (1+\nu^2)^{-1}$ , i.e. below $1/\nu$ , the limiting probability that $\sum_j X_j$ is divisible by <jats:inline-graphic xmlns:x

Open via your library →

Cite this paper

https://doi.org/https://doi.org/10.1017/jpr.2026.10086

Or copy a formatted citation

@article{boris2026,
  title        = {{Perfect partitions of a random set of integers}},
  author       = {Boris Pittel},
  journal      = {Journal of Applied Probability},
  year         = {2026},
  doi          = {https://doi.org/https://doi.org/10.1017/jpr.2026.10086},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

Perfect partitions of a random set of integers

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.