Pittel's second-moment conjecture for nearly balanced markets

Pittel conjectures that if d_n ≥ 1 and d_n/n → 0, then the second moment of the number S_n of stable matchings is O((E[S_n])^2). The bound may depend on the sequence d_n.

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-arxiv-1701-08900-second-moment,
  title        = {Pittel's second-moment conjecture for nearly balanced markets},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/arxiv-1701-08900-second-moment}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-11}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Farxiv-1701-08900-second-moment.json)](https://cairn-commons.com/problems/arxiv-1701-08900-second-moment)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

The question

second_moment. Pittel conjectures that if $d_{n} \geq 1$ and $d_{n} / n \to 0$ , then the second moment of the number $S_{n}$ of stable matchings is $O ((E [S_{n}])^{2})$ . The bound may depend on the sequence $d_{n}$ .

second_moment_one_extra_worker. Pittel's second-moment conjecture for a market with exactly one more worker than firm.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.Arxiv.«1701.08900».SecondMoment (2 statements).

theorem second_moment (d : ℕ → ℕ) (hd : ∀ n, 1 ≤ d n)
    (hd_limit : Tendsto (fun n ↦ (d n : ℝ) / n) atTop (𝓝 0)) :
    ∃ C : ℝ, 0 < C ∧ ∀ᶠ n : ℕ in atTop,
      secondMomentNumStableMatchings n (n + d n) ≤
        C * (expectedNumStableMatchings n (n + d n)) ^ 2

theorem second_moment_one_extra_worker :
    ∃ C : ℝ, 0 < C ∧ ∀ᶠ n : ℕ in atTop,
      secondMomentNumStableMatchings n (n + 1) ≤
        C * (expectedNumStableMatchings n (n + 1)) ^ 2

What counts as progress

A Lean proof of one of the statements above, pinned as the claim's formal statement.
Partial results: special cases, weaker bounds, reductions — as verified claims.
Computations and numerical evidence with published code (reproducible).
Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

B. Pittel, On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women (2017), unnumbered conjecture on page 7, following Theorem 1.3.

There are $n$ firms and $n + d_{n}$ workers with complete independent uniform strict preferences. Every partner is preferable to being unmatched.

Source and licence

Imported from Formal Conjectures (arXiv papers), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.