PaperlayerView exact revision on arXiv

Source-linked AI summary

Uniformity Testing for the Monomer-Dimer Model

Joy Qiping Yang, Yuichi Yoshida

arXiv:2610.36630v1cs.DScs.DM

TL;DR

The paper asks how many samples are needed to test whether a monomer-dimer distribution on a known graph is uniform. It uses conditional edge statistics to test this without learning all edge weights, achieving a square-root sample bound with a matching lower bound.

  • Problem

    How many samples distinguish a uniform monomer-dimer distribution on a known graph from one that is ε-far in total variation?

    Source: §1 · p. 4

  • Method

    Approximate entropy tensorization reduces the problem to detecting a large mean vector of one-edge conditional statistics, whose norm the tester estimates.

    Source: §1.2 · p. 6

  • Results

    Otilde_Δ(sqrt m/ε^2) samples suffice on bounded-degree graphs, while an Ω(sqrt m/ε^2) information-theoretic lower bound holds across graph densities.

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The tester estimates the norm of an expectation vector rather than learning the full edge-weight vector.

    Source: §1.2 · p. 6

    The testing analysis retains a bounded-degree restriction; using Jerrum-Sinclair to estimate matching counts does not remove it.

    Source: §1.2 · p. 5

Abstract

from arXiv · show

We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $\Delta$, uniformity can be tested with $\widetilde O_\Delta(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $\Theta(n)$ vertices and $\Theta(m)$ edges on which every tester requires $\Omega(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=\Theta(n)$, testing uniformity over the space of matchings has $\widetilde \Theta(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $\Theta(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.

1 Introduction

The introduction frames uniformity testing over matchings as a structured high-dimensional testing problem and presents matching-order upper and lower bounds. It outlines conditional edge statistics and quadratic testing, relates the work to graphical-model testing and matching algorithms, and previews the paper’s sections.

1 Introduction

  • The problem asks whether samples from an unknown weighted distribution over a known graph’s matchings are uniform or at least ε-far in total variation.The matching space may be exponentially large, and the tester has neither an explicit probability table for the uniform distribution nor a separate sampler from it.Source: §1 · pp. 3–4

1.1 Our results

  • For bounded-degree graphs, the paper gives a uniformity tester using eO_Δ(√m/ε²) samples and an information-theoretic Ω(√m/ε²) lower bound across graph densities.For bounded-degree families with m = Θ(n), the upper bound becomes eO(√n/ε²); the explicit dependence on Δ is not optimized.Source: §1.1 · p. 4

1.2 Technical overview

  • The tester uses conditional edge statistics: when no neighboring edge is selected, it tests whether an edge is selected with probability 1/2 under the uniform distribution.Screening estimates edge availability and conditional bias; a quadratic statistic detects the resulting m-dimensional mean signal with √m/ε² samples.Source: §1.2 · pp. 5–6

1.3 Related work

  • The paper joins the broad graphical-model testing program exemplified by Ising-model independence and goodness-of-fit testing, but studies the constrained matching family M(G) ⊆ {0,1}^E, not a product space.Source: §1.3 · p. 9

1.4 Organization

  • The paper proceeds from the Gibbs family and one-edge conditionals to the upper-bound tester, then proves the lower bound using checkerboard perturbations.An appendix gives an information-theoretic proper-learning bound to contrast testing with learning.Source: §1.4 · p. 9

2 Preliminaries

The paper formulates uniformity testing for weighted distributions over a graph’s matchings and identifies the uniform distribution with the all-one edge weights. It develops conditional edge statistics and degree-dependent entropy and Poincaré tools, alongside a lower bound on edge availability under the uniform distribution.

2.1 Setup

  • The testing promise is to distinguish D_w = U from dTV(D_w, U) ≥ ε, where U is uniform over all matchings, including the empty matching.The graph has m edges, and D_w is the Gibbs distribution over its matchings.Source: §2.1 · p. 10

2.2 Uniformity is rigid in the all-matchings model

  • D_w equals U if and only if every edge weight w_e equals 1, so uniformity testing in this family is equivalent to testing the all-one weight vector.The empty matching has weight 1, while singleton matching {e} has weight w_e.Source: §2.2 · p. 10

2.3 Conditioning on all other edges

  • Conditioned on the other edge indicators, an unavailable edge is forced absent; an available edge is Bernoulli(w_e/(1+w_e)) under D_w and Bernoulli(1/2) under U.The edgewise bias is parameterized by t_e = (w_e − 1)/(w_e + 1).Source: §2.3 · pp. 10–11

2.4 Entropy and Poincare tools on the line graph

  • For uniform distribution U on matchings, approximate entropy tensorization holds without bounded edge weights; separately, Gibbs distributions whose edge weights lie in [1/2, 2] satisfy a Poincaré inequality.Source: §2.4 · pp. 12–13

2.5 A lower bound on edge availability under U

  • Under U, each edge has availability bounded away from zero, established by mapping matchings where it is unavailable to matchings where it is available.The map deletes from an unavailable matching edges incident to the endpoints of the tested edge; a preimage has at most one restored edge at each endpoint.Source: §2.5 · p. 13

3 Upper Bound

The upper-bound tester calibrates edge availability under the uniform distribution, screens for large deviations, then tests using normalized conditional edge statistics and a quadratic statistic. The analysis establishes the stated sample bound for bounded-degree graphs.

3.1 Preprocessing: estimating U(Ae)

  • For fixed ∆, deterministic polynomial-time preprocessing estimates each uniform availability probability within factors 31/32 and 33/32, with estimates at least 31/(32∆^2).Source: §3.1 · p. 14

3.2 Screening to bound the weights

  • The cited result states that, with probability at least 1 −δ, under H0 the screening step does not reject.Source: §3.2 · p. 15

3.3 The vector Ψ and its mean

  • After screening, the normalized-statistic mean is zero under H0, while Lemma 3.3 gives a mean lower bound under alternatives.Source: §3.3 · p. 16

3.4 Covariance bound when weights are bounded

  • When all weights lie in [1/2, 2], Proposition 3.5 establishes a local covariance bound for the edge statistics.Source: §3.4 · p. 18

3.5 Quadratic statistic when weights are bounded

  • The quadratic statistic is formed from two independent fresh sample blocks, and Lemma 3.6 analyzes its mean and variance.Source: §3.5 · pp. 18–19

3.6 Proof of the main upper bound

  • A quadratic-block test with threshold κ∆ε^2/2 succeeds with probability at least 0.9; combining it with screening yields the stated sample bound.Source: §3.6 · p. 20

4.1 Proof setup

The lower-bound proof uses a graph family built from copies of Hq and checkerboard perturbations, then bounds the second moment of a mixture over random signs.

4.1 Proof setup

  • The construction uses disjoint copies of the dense component Hq.Source: §4.1 · p. 21
  • A finite family of checkerboard perturbations is analyzed by bounding the second moment of its random-sign mixture.Source: §4.1 · p. 21
  • Proposition 4.1 gives a sample lower bound for testing uniformity against ε-far Gibbs distributions on the constructed graph family.Source: §4.1 · p. 21

4.2 The checkerboard family on K2q,2q

The lower-bound construction assigns checkerboard perturbations to paired-vertex blocks of Hq and uses their symmetry and covariance under the uniform matching distribution.

4.2 The checkerboard family on K2q,2q

  • The left and right vertices of Hq are partitioned into pairs, with each pair-to-pair block assigned a checkerboard matrix.Source: §4.2 · pp. 21–22
  • Every row sum and column sum of each checkerboard matrix vanishes, and its score distribution is symmetric about zero under Uq.Source: §4.2 · pp. 22–23
  • The covariance lemma for uniform k-matchings on complete bipartite graphs applies to matrices with zero row and column sums.Source: §4.2 · p. 23
  • For every sign matrix σ, q^2 ≤ Var_Uq(Tσ) ≤ 4q.Source: §4.2 · p. 24

4.3 A quadratic log-MGF expansion on K2q,2q

The log-MGF argument for checkerboard scores on K2q,2q combines row-pair symmetries, occupation-probability estimates, and concentration of realized quadratic variation to obtain a local quadratic expansion.

4.3.1 Row-pair martingales and an exact log cosh representation

  • Exposing row-pairs yields bounded martingale differences, and swapping within row-pairs gives exact log-cosh identities and an MGF bound.Source: §4.3.1 · pp. 25–26

4.3.2 Occupation probabilities and a smoothness estimate

  • Matching size under the uniform measure on Ka,b is stochastically increasing in b, supporting smoothness bounds for one- and two-edge occupation probabilities.Source: §4.3.2 · p. 27

4.3.3 A reduced second-moment formula

  • The second-moment formula reduces when every column sum of the matrix vanishes.Source: §4.3.3 · p. 29

4.3.4 Concentration of the realized quadratic variation

  • The conditional range of each realized-variation contribution is O(1), yielding bounded increments for the associated Doob martingale.Source: §4.3.4 · pp. 30–31
  • The resulting log-MGF admits a local quadratic expansion with an error bounded by a constant times q s^4.Source: §4.3.4 · p. 32

4.4 The lower bound on Gt,q

The lower-bound construction uses disjoint copies of a graph H_q and sign-indexed Gibbs distributions over their matchings. Its analysis yields a tester lower bound that extends to graphs spanning every density from m=Θ(n) to m=Θ(n²).

4.4 The lower bound on Gt,q

  • The graph G_{t,q} is a disjoint union of t copies of H_q, so its uniform matching distribution factors into independent component distributions.The signs and checkerboard scores are defined across the copies.Source: §4.4 · p. 33
  • The proof controls score moments and log moment-generating functions before applying Paley–Zygmund to obtain a constant-probability tail event.The quadratic log-MGF expansion is applied to component scores and their sums.Source: §4.4 · pp. 33–35
  • The component-score distribution under the uniform matching law is symmetric about 0, with each component variance between q/2 and 4q.Independence and centering are used in the moment analysis.Source: §4.4 · p. 33
  • The testing lower bound follows by mixing over sign choices: the resulting sample mixture stays close in total variation to uniform samples, contradicting successful testing.The proof bounds χ² by 1/9 and the TV distance by 1/4.Source: §4.4 · p. 36
  • The construction gives a lower bound of Ω(√m/ε²) samples for graphs with Θ(n) vertices and Θ(m) edges.The proof applies Proposition 4.1 to G_{t,q} and uses qt=Θ(√m).Source: §4.4 · p. 37

A Learning the Matching Gibbs Family

The appendix gives an information-theoretic proper-learning bound for the matching Gibbs family using a Yatracos minimum-distance argument. It also shows that learning requires linearly many samples in m even on maximum-degree-1 graphs, unlike uniformity testing's square-root dependence on m.

A Learning the Matching Gibbs Family

  • O((m + log(1/δ))/ε²) samples suffice for proper learning, with a guarantee independent of graph maximum degree and weight magnitudes.The learner outputs a distribution in the Gibbs family.Source: A Learning the Matching Gibbs Family · pp. 39–40
  • The Yatracos class has VC dimension at most m+1 because its sets are restrictions of affine halfspaces in R^m.The argument identifies matchings with edge-incidence vectors.Source: A Learning the Matching Gibbs Family · p. 40
  • The linear dependence on m is unavoidable even for maximum-degree-1 graphs, since disjoint isolated edges realize Bernoulli product distributions.Their minimax learning sample complexity is Θ(m/ε²).Source: A Learning the Matching Gibbs Family · p. 41
  • Uniformity testing needs only order √m/ε² samples up to degree-dependent and logarithmic factors, whereas learning estimates the full distribution in total variation.The learning bound is information-theoretic; no computational efficiency is claimed.Source: A Learning the Matching Gibbs Family · pp. 39, 41
Loading 2610.36630v1…