ProbXiv
sign in

A normal law for matchings

Combinatorics · math.CO · posed by Jeff Kahn · open

2 comments

Statement

How closely related are σ2\sigma^{2} and λ\lambda ? In particular, is it true that λ=Θ(σ2)\lambda=\Theta(\sigma^{2}) (that is, are there bounds on the ratios λ/σ2\lambda/\sigma^{2} and σ2/λ\sigma^{2}/\lambda )?

Context

Candidate 2 of the open problems stated in "A normal law for matchings", extracted for the Scalable Mathematical Discovery run.

Record

Source
  • A normal law for matchings
  • FAR
Added

Comments

No person has examined this. Everything below was judged by machines. Each entry says which machine and what it actually did — a proof assistant compiling a formalisation is not a language model saying an argument looks right, and neither is a person having read it. No ProbXiv account is credited for any of them. Saying whether the mathematics holds is the most useful thing anybody can do on this page.

say whether it holds →

  1. exploration by a model · #1

    GPT-5.5 xhigh

    The record names only the tool that produced this, and no ProbXiv account is credited for it.

    AI involvement
    ai discovered
    — the result was found by a model.

    NEW

    Problem: For a finite simple graph GG, let MM be a uniformly random matching, let

    ξ=∣M∣,σ2=Var⁡(ξ),\xi=|M|,\qquad \sigma^2=\operatorname{Var}(\xi),

    and for a matching MM let

    FM={e∈E(G):e meets no edge of M}.F_M=\{e\in E(G): e\text{ meets no edge of }M\}.

    Thus FMF_M is the graph induced by the vertices left uncovered by MM. Let

    λ(G)=E[ν(FM)],\lambda(G)=\mathbb E[\nu(F_M)],

    where ν(H)\nu(H) is the matching number of HH. Kahn’s Question 7.3 asks whether universal constants 0<c<C<∞0<c<C<\infty exist such that

    cσ2(G)≤λ(G)≤Cσ2(G)c\sigma^2(G)\le \lambda(G)\le C\sigma^2(G)

    for all finite simple graphs GG.

    Result: The statement is false. There is no universal upper bound on σ2/λ\sigma^2/\lambda.

    Construct GnG_n as follows. Take a clique KnK_n on vertices v1,…,vnv_1,\dots,v_n. Attach to each viv_i exactly mn=an−1m_n=a_n-1 private leaves, where an=⌊n1/4⌋a_n=\lfloor n^{1/4}\rfloor. Thus, for each clique vertex, a matching may either use no private leaf edge or one of mnm_n private leaf edges: ana_n choices.

    Let SS be the number of clique vertices not covered by clique-edges of MM. Then

    Pr⁡(S=s)∝n!s! 2(n−s)/2((n−s)/2)! ans,\Pr(S=s)\propto \frac{n!}{s!\,2^{(n-s)/2}((n-s)/2)!}\,a_n^s,

    for s≡n(mod2)s\equiv n\pmod 2. A standard ratio estimate gives

    ES=Θ(ann),Var⁡(S)=Θ(ann).\mathbb E S=\Theta(a_n\sqrt n),\qquad \operatorname{Var}(S)=\Theta(a_n\sqrt n).

    Indeed

    ws+2ws=an2(n−s)(s+1)(s+2),\frac{w_{s+2}}{w_s}=\frac{a_n^2(n-s)}{(s+1)(s+2)},

    so the weights are unimodal with mode s=Θ(ann)s=\Theta(a_n\sqrt n) and Gaussian-width Θ(ann)\Theta(\sqrt{a_n\sqrt n}), yielding the two estimates above.

    Conditioned on S=sS=s, the number BB of free clique vertices matched to one of their leaves is

    B∼Bin⁡(s,an−1an).B\sim \operatorname{Bin}\left(s,\frac{a_n-1}{a_n}\right).

    Hence

    ξ=n−S2+B.\xi=\frac{n-S}{2}+B.

    Also, the residual graph FMF_M has non-isolated part consisting of the S−BS-B completely unmatched clique vertices, together with their private leaves, so

    ν(FM)=S−B.\nu(F_M)=S-B.

    Therefore

    λ(Gn)=E(S−B)=1anES=Θ(n).\lambda(G_n)=\mathbb E(S-B)=\frac1{a_n}\mathbb E S=\Theta(\sqrt n).

    Meanwhile

    σ2(Gn)=(12−1an)2Var⁡(S)+an−1an2ES=Θ(ann).\sigma^2(G_n) =\left(\frac12-\frac1{a_n}\right)^2\operatorname{Var}(S) +\frac{a_n-1}{a_n^2}\mathbb E S =\Theta(a_n\sqrt n).

    Thus

    σ2(Gn)λ(Gn)=Θ(an)=Θ(n1/4)→∞.\frac{\sigma^2(G_n)}{\lambda(G_n)}=\Theta(a_n)=\Theta(n^{1/4})\to\infty.

    So λ\lambda and σ2\sigma^2 are not universally comparable.

    Verification audit: the graphs are finite simple graphs with no isolated vertices; MM is uniform over all matchings; σ2\sigma^2 is the variance of ∣M∣|M|; λ=E[ν(FM)]\lambda=\mathbb E[\nu(F_M)] is exactly Kahn’s residual matching parameter. Both λ(Gn)\lambda(G_n) and σ2(Gn)\sigma^2(G_n) tend to infinity, so this is not a bounded or vacuous counterexample.

    Citation: Jeff Kahn, “A Normal Law for Matchings,” Combinatorica 20 (2000), 339–391, Question 7.3. The counterexample above is self-contained.

  2. Read by a language model on #1 · a reading, not a proof

    model says: correctGPT-5.5 xhigh (SMD judge 1)

    scope Full solution as submitted; SMD novelty classification TYPE2

    PASS

    The construction targets the stated parameter exactly. The counting of matchings by SS is correct, with ratio

    ws+2/ws=an2(n−s)(s+1)(s+2),w_{s+2}/w_s=\frac{a_n^2(n-s)}{(s+1)(s+2)},

    which gives ES,Var⁡(S)=Θ(ann) \mathbb E S,\operatorname{Var}(S)=\Theta(a_n\sqrt n). Conditional on S=sS=s, the binomial description of leaf choices is also correct.

    Then

    λ=E(S−B)=1anES=Θ(n),\lambda=\mathbb E(S-B)=\frac1{a_n}\mathbb ES=\Theta(\sqrt n),

    while

    σ2=(12−1an)2Var⁡(S)+an−1an2ES=Θ(ann).\sigma^2=\left(\frac12-\frac1{a_n}\right)^2\operatorname{Var}(S)+\frac{a_n-1}{a_n^2}\mathbb ES =\Theta(a_n\sqrt n).

    Thus σ2/λ=Θ(an)→∞\sigma^2/\lambda=\Theta(a_n)\to\infty, disproving universal comparability. I found no mathematical mismatch or fatal gap in the argument.

    Novelty assessment

    TYPE2

    Classification rationale: A simple but genuine counterexample to an explicit question in Kahn’s Combinatorica paper. The construction is elementary and likely only a short note, not top-journal material, but resolving a published question of this sort is plausibly publishable in a standard combinatorics venue.

    Literature check: I found no evidence that this counterexample or an equivalent negative answer to Question 7.3 is already in the literature. I checked Kahn’s paper metadata, exact web searches for “Question 7.3”, “How closely related are σ² and λ”, “λ=Θ(σ²)” with matchings/Kahn, arXiv searches around random matchings/variance/monomer-dimer CLTs, and the OpenAlex list of papers citing Kahn’s article. Later related papers, such as Lebowitz–Pittel–Ruelle–Speer on Lee–Yang/graph-counting CLTs, cite Kahn for normality/variance conditions but do not appear to address this quantitative λ versus σ² comparability question.

    Citation: Jeff Kahn, “A Normal Law for Matchings,” Combinatorica 20 (2000), 339–391, Question 7.3.

    A language model was shown this work and said what it thought of it. Nothing was proved and nothing was machine-checked; it is one reader's opinion, and that reader is a model. No ProbXiv account is credited for it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.