Let \(C_n\) be the minimum cost of a perfect matching in an \(n\times n\) matrix of independent uniform random variables. We prove that \[ \sqrt n\{C_n-\zeta(2)\} \ \Longrightarrow\ \mathcal N\bigl(0,4\zeta(2)-4\zeta(3)\bigr). \] The proof begins with an exact change of variables based on a uniformly rooted shortest-path selection of an optimal dual potential. After the unused reduced costs are integrated out, a reference law separates the rows conditionally on the potential field, while the ordered potential gaps become independent exponentials. The only residual dependence is a directed-tree factor. Ordering the potentials turns its zero--one support into a Ferrers matrix, whose matrix-tree determinant is triangular. A singular inverse-degree estimate and exact normalization then yield total-variation convergence to the reference law. Finally, a conditional triangular-array central limit theorem accounts for row noise, and a second triangular array accounts for the linear response of the potential field. The strategy used here is likely to be applicable to other problems.
Consider $n$ independent, non-negative, mean at most one random variables, $X_1,X_2,\ldots$. We show the following bound on the probability of their sum exceeding a threshold $t$: \[ \mathbb{P}\left[\sum_{i=1}^n X_i\ge t\right] \leq 1-\left(1-\frac{1}{t}\right)^n \text{ for all } t\ge 2n+1 \,. \] To prove this, we cons...
Let \(X_{1,n},\ldots,X_{d,n}\) be \(n\times n\) random matrices built from independent i.i.d. entry arrays, with centered entries, normalized by \(n^{-1/2}\). We prove that, if every entry law has finite fourth moment, then this tuple converges almost surely strongly in \(*\)-distribution to a free circular family with...
For a prime \(p\), let \(A_p=\{k!\pmod p:1\leq k<p\}\). We prove \(|A_p|\gg p^{8/15}\), improving the general lower bound \((\sqrt{2}-o(1))p^{1/2}\). The proof begins with the identity \((n+2)!=(n+1)!+((n+1)!)^2/n!\) in \(\mathbb{F}_p\), which produces many incidences for a family of fractional-linear maps. After Cauch...
We prove a quantitative central limit theorem for linear functionals of regularized empirical-risk minimizers in the proportional-dimensional regime \(p=O(n)\). The data columns are independent, not necessarily identically distributed, and satisfy a uniform columnwise Poincar\'e inequality. Under uniform curvature and...
For the $n\times n$ lower-triangular all-ones matrix $Q$, we prove a near-optimal lower bound \[ \gamma_{2,1}(Q) := \inf_{Q=AB} \|A\|_{2\to\infty}\|B\|_{1\to1} = \Omega\!\left( \frac{\log^{3/2}n}{(\log\log n)^{3/2}} \right), \] where the infimum ranges over real factorizations of arbitrary finite inner dimension. This...
Hong-Hao Lin, V. Mirrokni, David P. Woodruff· 2 citations
Let $A_1,\ldots,A_n$ be independent $d \times d$ real symmetric Gaussian random matrices, and consider the linear operator $A(x) = n^{-1/2}\sum_{i=1}^n x_i A_i$, $x\in \mathbb{R}^n$. We construct an iterative algorithm in the Approximate Message Passing family which iterates over $A$ and its adjoint $A^*$, and establis...
August Y. Chen, A. El Alaoui· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
