betaFeedback

WorksMathematics

Regular induced subgraphs in bounded independent-edge arrays

Abstract

Let GG be a random graph whose edges are independent and whose edge probabilities lie in [ξ,1−ξ][\xi,1-\xi] for a fixed 0<ξ<1/20<\xi<1/2. With probability at least 1−n−11-n^{-1}, GG contains a regular induced subgraph on at least cξ(log⁡n)2c_\xi(\log n)^2 vertices. If all expected degrees are equal, each prescribed order kk up to a small multiple of n2/3n^{2/3} occurs with failure probability at most exp⁡(−cn/k3/2)\exp(-cn/k^{3/2}), for kk sufficiently large. The same probability estimate holds up to order n2/(d+3)n^{2/(d+3)} for a Lipschitz kernel in dimension dd, and up to order n4/(r+7)n^{4/(r+7)} for an array admitting a bounded symmetric completion of rank at most rr. A linear product array has largest regular induced order Θ(n)\Theta(\sqrt n) with high probability, attaining the scale for dimension one and rank one. The proof weights each candidate set by the reciprocal of its success probability and controls the dependence due to shared edges.

Introduction

How large a regular induced subgraph must a random graph contain if the edge probabilities can be chosen separately? For G(n,1/2)G(n,1/2), Krivelevich, Sudakov and Wormald give a high-probability upper bound of 2n2/32n^{2/3} and find regular induced sets at subcritical orders. In particular R=n2/3+o(1)R=n^{2/3+o(1)} with high probability [6 Theorem 1.1]. For unequal edge probabilities there is a second obstruction to regularity. Even before the graph is sampled, the expected degrees on a candidate vertex set may differ by much more than a typical degree fluctuation. We give lower bounds that depend on how much of this variation can be removed by choosing the vertex set.

Write G(p)G(\mathbf p) for the simple graph on [n][n] in which distinct unordered pairs are present independently, with probabilities pij=pjip_{ij}=p_{ji}. Throughout, 0<ξ<1/20<\xi<1/2 is fixed and ξ≤pij≤1−ξ\xi\le p_{ij}\le1-\xi for i≠ji\ne j. Write AkA_k for the event that some set of exactly kk vertices induces a regular graph, and put R=max⁡{k:Ak occurs}R=\max\{k:A_k\text{ occurs}\}. Thus {R≥k}=⋃ℓ≥kAℓ\{R\ge k\}=\bigcup_{\ell\ge k}A_\ell. When a domain UU is specified, AkA_k and RR refer to the induced array on UU. The common degree may depend on the set. All logarithms are natural.

Theorem 1.1. The following bounds hold uniformly in the indicated arrays for all sufficiently large nn.

  1. There are 0<cξ′≤cξ0<c'_{\xi}\le c_{\xi} such that

Pr⁡{R<cξ(log⁡n)2}≤n−1,Pr⁡{R<cξ′(log⁡n)2}≤exp⁡(−nlog⁡n/8).\Pr\{R<c_{\xi}(\log n)^2\}\le n^{-1},\qquad\Pr\{R<c'_{\xi}(\log n)^2\}\le\exp(-\sqrt{n}\log n/8).
  1. In each of the three cases below there are constants a,c>0a,c>0 and k0k_0 such that, for every integer k0≤k≤anβk_0\le k\le an^{\beta},

Pr⁡(Akc)≤exp⁡(−cn/k3/2).(1)\Pr(A_k^c)\le\exp(-cn/k^{3/2}). \tag*{(1)}
Hypothesis on the arrayβ\beta
All expected degrees ∑j≠ipij\sum_{j\ne i}p_{ij} are equal2/32/3
Symmetric LL-Lipschitz kernel on [0,1]d[0,1]^d2/(d+3)2/(d+3)
Bounded symmetric matrix completion of rank at most rr4/(r+7)4/(r+7)

Table 1.

In the kernel case pij=W(xi,xj)p_{ij}=W(x_i,x_j) for arbitrary deterministic types, WW takes values in [ξ,1−ξ][\xi,1-\xi], and ∣W(x,y)−W(x′,y)∣≤L∥x−x′∥∞|W(x,y)-W(x',y)|\le L\|x-x'\|_{\infty}. A completion is a matrix P∈[0,1]n×nP\in[0,1]^{n\times n} with the prescribed off-diagonal entries. The constants and the onset depend only on ξ\xi and, where applicable, the fixed parameters (d,L)(d,L) or rr, with d,r≥1d,r\ge1.

For equal expected degrees, (1) gives high probability for k0≤k=o(n2/3)k_0\le k=o(n^{2/3}). At k=⌊an2/3⌋k=\lfloor an^{2/3}\rfloor it gives a success probability bounded away from zero uniformly in nn. For the other two classes, n/k3/2n/k^{3/2} grows as a positive power of nn even at the indicated endpoint. In particular every bounded one-dimensional Lipschitz model has a regular induced subgraph of order at least cnc\sqrt{n} with high probability. § 6 gives an example attaining this scale.

Relation to earlier work. Erdős, Fajtlowicz and Staton asked whether the largest regular induced subgraph of every nn-vertex graph has order ω(log⁡n)\omega(\log n) [1, 6]. A complementary deterministic approach studies modular witnesses and finite absorption certificates [8]. Our first bound concerns a random graph with a fixed probability floor. For instance it applies after independently toggling the adjacency of each pair in a prescribed graph. The resulting induced subgraph is regular in the perturbed graph. In the other direction, Dyson and McKay use inhomogeneous random graphs to give a square-root upper bound for the extremal problem [4].

Levy studies a one-dimensional Lipschitz kernel with independent uniform types and obtains a conditional n1/2−εn^{1/2-\varepsilon} lower bound under local degree and overlap hypotheses [7]. Our one-dimensional bound holds uniformly for every assignment of the types. Conditioning on the types therefore gives a cnc\sqrt{n} lower bound with high probability for Levy’s model, with cc depending on the probability floor and the kernel’s Lipschitz constant. Levy also conjectures the sharp family-wide constant 2e\sqrt{2e}. The constant in our order bound depends on the model parameters.

Where the scales come from. In a domain of NN vertices with normalized expected degrees within O(k−1/2)O(k^{-1/2}) of one another, many kk-sets can be tilted to the same integer target degree. Two independent uniform kk-sets share k2/Nk^2/N vertices in expectation. If they share jj vertices, averaging the tilt over the shared vertices gives a factor of order exp⁡(O(j2/k))\exp(O(j^2/k)) in the small-overlap range. Thus k3/N2=O(1)k^3/N^2=O(1) is the natural condition for a bounded second moment. Nearly coincident sets require a separate estimate, which is what permits the endpoint N≲k3/2N\lesssim k^{3/2}. Equal row sums supply many such domains by sampling. Kernel and rank assumptions supply them by grouping vertices. With no structural assumption we instead increase the edge density until the mean-square degree variation is small enough for a logarithmic choice of kk.

Formalization. The Palomar Registry entry PALOMAR-2026-11-19-000016 (version 1) records the two logarithmic bounds together and each of the three exact-order bounds separately [9]. Its Lean statement file defines the exact-order and at-least-order events for the finite Bernoulli product law. The proof library also contains counterparts of the Fourier estimates and the two-sided product example. The repository’s coverage map refers to an earlier 17-page version of this manuscript and uses that version’s numbering.

The local cost of prescribing degrees

For independent Bernoulli edges on [k][k] with probabilities qijq_{ij}, let DD be the degree vector, wij=qij(1−qij)w_{ij}=q_{ij}(1-q_{ij}), and uij=ei+eju_{ij}=e_i+e_j. A present edge adds uiju_{ij} to DD, so its covariance matrix is

Q=∑i<jwijuijuijT.Q=\sum_{i<j}w_{ij}u_{ij}u_{ij}^{T}.

The following two estimates are the analytic inputs. The determinant normalization is essential. Replacing it in both estimates by k−k/2exp⁡(O(k))k^{-k/2}\exp(O(k)) would cost an exponential factor even for sets sharing only two vertices.

Lemma 2.1 (Full and residual degree atoms). Fix a floor δ∈(0,1/2)\delta\in(0,1/2) for the qijq_{ij}. If b=EDb=\mathbb{E}D is integral with even total, then, uniformly for sufficiently large kk,

Pr⁡(D=b)≥cδ(2π)−k/2(det⁡Q)−1/2≥exp⁡(−12klog⁡k−Cδk).\Pr(D=b)\ge c_{\delta}(2\pi)^{-k/2}(\det Q)^{-1/2}\ge\exp\left(-\frac{1}{2}k\log k-C_{\delta}k\right).

For the upper bound, assume only the same floor on the edge probabilities. Fix 0<ρ<10<\rho<1 and delete all edges inside a set JJ of j≤ρkj\le\rho k vertices and let D′D' and Q′Q' denote the remaining degree vector and covariance. For every sufficiently large kk (depending on δ,ρ\delta,\rho) and every integral target b′b', one has

Pr⁡(D′=b′)≤Cδ,ρ(2π)−k/2(det⁡Q′)−1/2.\Pr(D'=b')\le C_{\delta,\rho}(2\pi)^{-k/2}(\det Q')^{-1/2}.

The Fourier argument for these estimates is given in Appendix § 7. In particular the residual target may be far from its mean. Given a realization of the edges internal to JJ, obtaining D=bD=b requires a single residual target. We record the resulting comparison.

Corollary 2.2. Under the centering and parity hypotheses above, for every configuration HH on the pairs in JJ,

Pr⁡(D=b∣H)Pr⁡(D=b)≤Cδ,ρexp⁡(Cδ,ρj2/k).\frac{\Pr(D=b\mid H)}{\Pr(D=b)}\le C_{\delta,\rho}\exp(C_{\delta,\rho}j^2/k).

Proof. With QJ=Q−Q′⪰0Q_J=Q-Q'\succeq0, the trace of QJQ_J is 2∑a<b∈Jwab=O(j2)2\sum_{a<b\in J}w_{ab}=O(j^2). The residual covariance satisfies Q′⪰cδ,ρkIQ'\succeq c_{\delta,\rho}kI by (A.1) below. Consequently

log⁡(det⁡Q/det⁡Q′)≤tr⁡((Q′)−1QJ)≤Cδ,ρj2/k.\log(\det Q/\det Q')\le\operatorname{tr}((Q')^{-1}Q_J)\le C_{\delta,\rho}j^2/k.

Apply Lemma 2.1 and take the square root of the determinant ratio.

Tilting to a common degree

A tilt of the edge logits by θi+θj\theta_i+\theta_j has a useful exact property. Its likelihood relative to the original law is constant on each degree vector. The following estimates quantify the price of matching the means to that vector.

Lemma 2.3 (Inverse in the maximum norm). Let k≥4k\ge4, let 0<λ≤1/40<\lambda\le1/4, and suppose λ≤wij=wji≤1/4\lambda\le w_{ij}=w_{ji}\le1/4 for i≠ji\ne j. Let WW have entries wijw_{ij} off the diagonal and zero diagonal, and put

D=diag⁡(∑j≠iwij)i=1k,H=D+W.D=\operatorname{diag}\left(\sum_{j\ne i}w_{ij}\right)_{i=1}^{k},\qquad H=D+W.

Then

λ(k−2)I⪯H⪯12(k−1)I,∥H−1∥∞→∞≤Cλ/k.\lambda(k-2)I \preceq H \preceq\frac{1}{2}(k-1)I,\qquad\lVert H^{-1}\rVert_{\infty\to\infty} \le C_{\lambda}/k.

Proof. For every x∈Rkx \in\mathbb{R}^{k},

xTHx=∑i<jwij(xi+xj)2,∑i<j(xi+xj)2=(k−2)∥x∥22+(∑ixi)2.x^{T}Hx=\sum_{i<j}w_{ij}(x_i+x_j)^2,\qquad\sum_{i<j}(x_i+x_j)^2=(k-2)\lVert x\rVert_2^2+\left(\sum_i x_i\right)^2.

These identities prove the two spectral bounds and, in particular, invertibility. For the maximum norm, set P=D−1WP=D^{-1}W. The matrix PP is stochastic. Two distinct rows have common mass at least

∑amin⁡(Pia,Pja)≥4λ(k−2)k−1≥2λ=:β.\sum_a\min(P_{ia},P_{ja})\ge\frac{4\lambda(k-2)}{k-1}\ge2\lambda=:\beta.

For a real vector xx, write osc⁡(x)=max⁡ixi−min⁡ixi\operatorname{osc}(x)=\max_i x_i-\min_i x_i. Subtracting the common mass from two probability rows leaves two nonnegative measures of equal mass at most 1−β1-\beta. Their averages of xx differ by at most (1−β)osc⁡(x)(1-\beta)\operatorname{osc}(x). Hence

osc⁡(Px)≤(1−β)osc⁡(x).\operatorname{osc}(Px)\le(1-\beta)\operatorname{osc}(x).

If (I+P)x=y(I+P)x=y, the inequality osc⁡(x)≤osc⁡(y)+osc⁡(Px)\operatorname{osc}(x)\le\operatorname{osc}(y)+\operatorname{osc}(Px) implies βosc⁡(x)≤2∥y∥∞\beta\operatorname{osc}(x)\le2\lVert y\rVert_{\infty}. Let m=min⁡ixim=\min_i x_i and M=max⁡ixiM=\max_i x_i. At a coordinate attaining MM the equation gives yi≥M+my_i\ge M+m; at a coordinate attaining mm it gives yi≤m+My_i\le m+M. Thus ∣M+m∣≤∥y∥∞\lvert M+m\rvert\le\lVert y\rVert_{\infty}, and

∥x∥∞=∣M+m∣+M−m2≤(12+1β)∥y∥∞.\lVert x\rVert_{\infty}=\frac{\lvert M+m\rvert+M-m}{2}\le\left(\frac{1}{2}+\frac{1}{\beta}\right)\lVert y\rVert_{\infty}.

For Hx=zHx=z, take y=D−1zy=D^{-1}z and use Dii≥λ(k−1)D_{ii}\ge\lambda(k-1). This proves the asserted inverse bound.

Lemma 2.4 (A deterministic vertex tilt)

Lemma 2.4 (A deterministic vertex tilt). Fix ξ∈(0,1/2)\xi\in(0,1/2). There are constants εξ>0\varepsilon_{\xi}>0, aξ∈(0,1/2)a_{\xi}\in(0,1/2), Cξ<∞C_{\xi}<\infty, and k0(ξ)k_0(\xi) such that the following holds. Let k≥k0(ξ)k\ge k_0(\xi), let qij∈[ξ,1−ξ]q_{ij}\in[\xi,1-\xi], and let d=(d1,…,dk)∈Zk\mathbf{d}=(d_1,\ldots,d_k)\in\mathbb{Z}^k have even total sum. Put

ri=∑j≠iqij−di,∥r∥∞≤εξk.r_i=\sum_{j\ne i}q_{ij}-d_i,\qquad\lVert r\rVert_{\infty}\le\varepsilon_{\xi}k.

There is a vector θ∈Rk\theta\in\mathbb{R}^k for which

qij(θ)=qijeθi+θj1−qij+qijeθi+θjq_{ij}(\theta)=\frac{q_{ij}e^{\theta_i+\theta_j}}{1-q_{ij}+q_{ij}e^{\theta_i+\theta_j}}

satisfies

∑j≠iqij(θ)=di(i∈[k]),qij(θ)∈[aξ,1−aξ],\sum_{j\ne i}q_{ij}(\theta)=d_i\quad(i\in[k]),\qquad q_{ij}(\theta)\in[a_{\xi},1-a_{\xi}],
∥θ∥∞≤Cξ∥r∥∞/k,∥θ∥2≤Cξ∥r∥2/k.\lVert\theta\rVert_{\infty}\le C_{\xi}\lVert r\rVert_{\infty}/k,\qquad\lVert\theta\rVert_2\le C_{\xi}\lVert r\rVert_2/k.

If P0\mathbb{P}_0 and Pθ\mathbb{P}_{\theta} are the original and tilted product measures, respectively, their relative entropy obeys

K:=D(Pθ∥P0)≤Cξ∥r∥22/k.K:=D(\mathbb{P}_{\theta}\Vert\mathbb{P}_0)\le C_{\xi}\lVert r\rVert_2^2/k.

On every graph configuration with degree vector d\mathbf{d}, the likelihood ratio Pθ/P0\mathbb{P}_{\theta}/\mathbb{P}_0 is the constant eKe^K. Consequently

P0(D=d)≥exp⁡{−12klog⁡k−Cξk−Cξ∥r∥22k}.(2)\mathbb{P}_0(D=\mathbf{d})\ge\exp\left\{-\frac{1}{2}k\log k-C_{\xi}k-C_{\xi}\frac{\lVert r\rVert_2^2}{k}\right\}. \tag*{(2)}

Proof. Define

Fi(θ)=∑j≠iqij(θ)−di,Ψ(θ)=∑i<jlog⁡(1−qij+qijeθi+θj).F_i(\theta)=\sum_{j\ne i}q_{ij}(\theta)-d_i,\qquad\Psi(\theta)=\sum_{i<j}\log(1-q_{ij}+q_{ij}e^{\theta_i+\theta_j}).

The gradient of Ψ\Psi is the vector of tilted expected degrees, and H(θ):=DF(θ)=∇2Ψ(θ)H(\theta):=DF(\theta)=\nabla^2\Psi(\theta) has the form of Lemma 2.3, with weights qij(θ)(1−qij(θ))q_{ij}(\theta)(1-q_{ij}(\theta)). For ∥θ∥∞≤1\|\theta\|_\infty\le1, one may take

aξ=ξe−21−ξ+ξe−2>0a_\xi=\frac{\xi e^{-2}}{1-\xi+\xi e^{-2}}>0

as a lower bound both for qij(θ)q_{ij}(\theta) and for 1−qij(θ)1-q_{ij}(\theta). Set λξ=aξ(1−aξ)\lambda_\xi=a_\xi(1-a_\xi). Throughout that cube,

λξ(k−2)I⪯H(θ)⪯12(k−1)I,∥H(θ)−1∥∞→∞≤Aξ/k.(3)\lambda_\xi(k-2)I\preceq H(\theta)\preceq\frac{1}{2}(k-1)I,\qquad\|H(\theta)^{-1}\|_{\infty\to\infty}\le A_\xi/k. \tag*{(3)}

We first construct the tilt. Since F(0)=rF(0)=r, Taylor expansion gives

F(θ)=r+H(0)θ+R(θ).F(\theta)=r+H(0)\theta+R(\theta).

The first two derivatives of the logistic function are bounded absolutely. On the cube of radius b≤1b\le1, each row has k−1k-1 summands, each depending on a sum of two coordinates. The one-variable mean value formula therefore gives

∥R(θ)∥∞≤Ckb2,∥R(θ)−R(ϕ)∥∞≤Ckb∥θ−ϕ∥∞.\|R(\theta)\|_\infty\le Ckb^2,\qquad\|R(\theta)-R(\phi)\|_\infty\le Ckb\|\theta-\phi\|_\infty.

If r=0r=0 take θ=0\theta=0. Otherwise put b=2Aξ∥r∥∞/kb=2A_\xi\|r\|_\infty/k and T(θ)=−H(0)−1(r+R(θ))T(\theta)=-H(0)^{-1}(r+R(\theta)). Choose εξ\varepsilon_\xi so that b≤1b\le1 and CAξb≤1/2CA_\xi b\le1/2. On the closed cube of radius bb, the preceding estimates give ∥T(θ)∥∞≤b/2+CAξb2≤b\|T(\theta)\|_\infty\le b/2+CA_\xi b^2\le b and Lip⁡(T)≤1/2\operatorname{Lip}(T)\le1/2. The contraction theorem gives a fixed point in that cube. It solves F(θ)=0F(\theta)=0, satisfies the stated maximum-norm bound, and preserves the floor aξa_\xi.

For the Euclidean bound, integrate the Hessian along the segment from zero to the fixed point. Since ∇Ψ(θ)−∇Ψ(0)=−r\nabla\Psi(\theta)-\nabla\Psi(0)=-r,

−r⋅θ=∫01θTH(tθ)θ dt≥λξ(k−2)∥θ∥22.-r\cdot\theta=\int_0^1\theta^T H(t\theta)\theta\,dt\ge\lambda_\xi(k-2)\|\theta\|_2^2.

Cauchy–Schwarz yields ∥θ∥2≤∥r∥2/[λξ(k−2)]\|\theta\|_2\le\|r\|_2/[\lambda_\xi(k-2)].

For any graph configuration AA, let D(A)D(A) be its degree vector. The exact product-measure likelihood ratio is

Pθ(A)P0(A)=exp⁡{θ⋅D(A)−Ψ(θ)}.\frac{\mathbb{P}_\theta(A)}{\mathbb{P}_0(A)}=\exp\{\theta\cdot D(A)-\Psi(\theta)\}.

Taking its logarithmic expectation under Pθ\mathbb{P}_\theta, and using ∇Ψ(θ)=d\nabla\Psi(\theta)=d and Ψ(0)=0\Psi(0)=0, gives

K=θ⋅∇Ψ(θ)−Ψ(θ)=∫01tθTH(tθ)θ dt≤k−14∥θ∥22≤Cξ∥r∥22/k.\begin{aligned} K=\theta\cdot\nabla\Psi(\theta)-\Psi(\theta) \\ &=\int_0^1t\theta^T H(t\theta)\theta\,dt\le\frac{k-1}{4}\|\theta\|_2^2\le C_\xi\|r\|_2^2/k. \end{aligned}

On D(A)=dD(A)=d, the logarithmic likelihood ratio equals this same KK. Hence P0(D=d)=e−KPθ(D=d)\mathbb{P}_0(D=d)=e^{-K}\mathbb{P}_\theta(D=d). Under Pθ\mathbb{P}_\theta, the target degrees are exactly the means, they are integral with even total, and every edge probability lies in [aξ,1−aξ][a_\xi,1-a_\xi]. Applying the centered degree estimate, Lemma 2.1, with floor aξa_\xi, and enlarging k0(ξ)k_0(\xi) and CξC_\xi if needed, proves (2).

Sampling distinct vertices

Lemma 2.5 (Concentration for sampling without replacement). Let a1,…,aM∈[0,1]a_1,\ldots,a_M\in[0,1], let aˉ=M−1∑iai\bar{a}=M^{-1}\sum_i a_i, and let YY be the sum of a uniformly chosen mm-element subset of these numbers, where 1≤m≤M1\le m\le M. Then

Eet(Y−maˉ)≤emt2/8(t∈R),\mathbb{E}e^{t(Y-m\bar{a})}\le e^{mt^2/8}\qquad(t\in\mathbb{R}),

and for every s≥0s\ge0,

P(∣Y−maˉ∣≥s)≤2e−2s2/m.\mathbb{P}(|Y-m\bar{a}|\ge s)\le2e^{-2s^2/m}.

Also Var⁡Y≤m/4\operatorname{Var}Y\le m/4.

Proof. For nonnegative z1,…,zMz_1,\ldots,z_M, their elementary symmetric polynomial satisfies

em(z1,…,zM)(Mm)≤(1M∑izi)m.(4)\frac{e_m(z_1,\ldots,z_M)}{\binom{M}{m}}\le\left(\frac{1}{M}\sum_i z_i\right)^m. \tag*{(4)}

For m≥2m\ge2, averaging two coordinates at fixed sum increases their product and leaves all terms involving just one coordinate unchanged in aggregate. Thus this operation cannot decrease eme_m. Repeatedly averaging the largest and smallest coordinates decreases the sum of squared deviations by half the squared range. The range tends to zero, giving (4) by continuity. For m=1m=1 there is equality.

Take zi=etaiz_i=e^{ta_i}. The left side of (4) is EetY\mathbb{E}e^{tY}. For a single uniform draw XX, the log moment generating function of X−aˉX-\bar{a} has value and derivative zero at zero. Its second derivative is the variance under an exponential tilt, at most 1/41/4 since 0≤X≤10\le X\le1. Hence

Eet(Y−maˉ)≤(Eet(X−aˉ))m≤emt2/8.\mathbb{E}e^{t(Y-m\bar{a})}\le\left(\mathbb{E}e^{t(X-\bar{a})}\right)^m\le e^{mt^2/8}.

Exponential Markov at t=±4s/mt=\pm4s/m gives the two tails. Comparing the second derivatives at zero gives Var⁡Y≤m/4\operatorname{Var}Y\le m/4, since both sides of the centered moment bound have value one and derivative zero there.

A common target degree

Lemma 2.6 (Candidate family from mean-squared drift). Fix ξ∈(0,1/2)\xi\in(0,1/2). Let (qxy)x≠y(q_{xy})_{x\ne y} be a symmetric array on [N][N] with entries in [ξ,1−ξ][\xi,1-\xi], and let p∈[ξ,1−ξ]p\in[\xi,1-\xi]. Write

ax=1N−1∑y≠xqxy−p.a_x=\frac{1}{N-1}\sum_{y\ne x}q_{xy}-p.

Suppose that

max⁡x∣ax∣≤α,1N∑xax2≤η2.\max_x|a_x|\le\alpha,\qquad\frac{1}{N}\sum_xa_x^2\le\eta^2.

Uniformly along sequences with k→∞k\to\infty, α→0\alpha\to0, and k≤Nk\le N, there is a legal degree dd, with kdkd even and ∣d−p(k−1)∣≤2|d-p(k-1)|\le2, and a family F⊆([N]k)\mathcal{F}\subseteq\binom{[N]}{k} of size at least 12(Nk)\frac12\binom{N}{k}, such that every S∈FS\in\mathcal{F} has a vertex tilt θS\theta^S satisfying

EθSdeg⁡G[S](v)=d(v∈S),quv(θS)∈[aξ,1−aξ],\mathbb{E}_{\theta^S}\deg_{G[S]}(v)=d\quad(v\in S),\qquad q_{uv}(\theta^S)\in[a_\xi,1-a_\xi],
∥θS∥∞≤Cξ(α+log⁡kk),∥θS∥22≤Cξ(1+η2k),\|\theta^S\|_\infty\le C_\xi\left(\alpha+\sqrt{\frac{\log k}{k}}\right),\qquad\|\theta^S\|_2^2\le C_\xi(1+\eta^2k),
pS:=P(G[S] is d-regular)≥p∗:=exp⁡{−12klog⁡k−Cξ(k+η2k2)}.p_S:=\mathbb{P}(G[S]\text{ is }d\text{-regular})\ge p_*:=\exp\left\{-\frac12 k\log k-C_\xi(k+\eta^2k^2)\right\}.

Here aξ>0a_\xi>0 and CξC_\xi depend only on ξ\xi. There is no restriction on k2/Nk^2/N in this lemma.

Proof. Choose dd before selecting the vertices. If kk is even, choose a nearest integer to p(k−1)p(k-1); if kk is odd, choose a nearest even integer. For large kk, uniformly for p∈[ξ,1−ξ]p \in[\xi,1-\xi], this is a legal degree 0≤d≤k−10 \le d \le k-1 with the stated parity and error. Set b=p(k−1)−db=p(k-1)-d, so ∣b∣≤2|b| \le2. Choose a uniform ordered tuple (X1,…,Xk)(X_1,\ldots,X_k) of distinct labels in [N][N], and put

ri=∑j≠iqXiXj−d.r_i=\sum_{j\ne i}q_{X_iX_j}-d.

Conditional on Xi=xX_i=x, the remaining labels form a uniform (k−1)(k-1)-subset of [N]∖{x}[N]\setminus\{x\}. Consequently

E(ri∣Xi=x)=(k−1)ax+b,Var⁡(ri∣Xi=x)≤(k−1)/4.\mathbb{E}(r_i\mid X_i=x)=(k-1)a_x+b,\qquad\operatorname{Var}(r_i\mid X_i=x)\le(k-1)/4.

where the variance assertion follows from Lemma 2.5. The same lemma, with t=2klog⁡kt=\sqrt{2k\log k}, and a union bound give

∥r∥∞≤α(k−1)+2+2klog⁡k(5)\lVert r\rVert_\infty\le\alpha(k-1)+2+\sqrt{2k\log k} \tag*{(5)}

with probability at least 1−2k−31-2k^{-3}. There is no independence assertion between different row sums. Their squared norm is instead controlled directly by conditional second moments:

E∥r∥22≤k{k−14+2(k−1)21N∑xax2+8}≤C(k2+η2k3).\mathbb{E}\lVert r\rVert_2^2\le k\left\{\frac{k-1}{4}+2(k-1)^2\frac{1}{N}\sum_x a_x^2+8\right\} \le C(k^2+\eta^2 k^3).

Markov’s inequality therefore gives

∥r∥22≤4C(k2+η2k3)(6)\lVert r\rVert_2^2\le4C(k^2+\eta^2 k^3) \tag*{(6)}

with probability at least 3/43/4. The two displayed drift bounds hold together with probability at least 1/21/2 for all sufficiently large kk.

On their intersection ∥r∥∞/k=o(1)\lVert r\rVert_\infty/k=o(1) uniformly. The tilt in Lemma 2.4 therefore exists, with the fixed floor aξa_\xi. Its maximum norm is at most Cξ∥r∥∞/kC_\xi\lVert r\rVert_\infty/k, its squared energy at most Cξ∥r∥22/k2C_\xi\lVert r\rVert_2^2/k^2, and its negative log probability cost beyond the centered atom at most Cξ∥r∥22/kC_\xi\lVert r\rVert_2^2/k. Substitution of (5) and (6) gives all three asserted estimates. Both drift tests are invariant under reorderings, and every kk-set has k!k! orderings, so at least half of the unordered sets qualify. □\square

Shared edges and a weighted count

Let ESE_S be the event that a candidate SS induces a dd-regular graph, where the degree dd and the family F\mathcal{F} come from Lemma 2.6. Weight a success on SS by 1/pS1/p_S, where pS=Pr⁡(ES)p_S=\Pr(E_S). Then

Z=∑S∈F1ESpS,EZ=∣F∣.Z=\sum_{S\in\mathcal{F}}\frac{\mathbf{1}_{E_S}}{p_S},\qquad\mathbb{E}Z=|\mathcal{F}|.

This weighting allows different candidates to have very different probabilities. Write HST=Pr⁡(ES∩ET)/(pSpT)H_{ST}=\Pr(E_S\cap E_T)/(p_Sp_T) for the normalized joint probability.

Lemma 3.1 (Shared-edge likelihood). Let J=S∩TJ=S\cap T, j=∣J∣j=|J|, and XS(J)=∑v∈J(θvS)2X_S(J)=\sum_{v\in J}(\theta_v^S)^2. For j≤3k/4j\le3k/4 the normalized joint probability satisfies

Pr⁡(ES∩ET)pSpT≤Kexp⁡{Dj2k+j4[XS(J)+XT(J)]},(7)\frac{\Pr(E_S\cap E_T)}{p_Sp_T}\le K\exp\left\{\frac{Dj^2}{k}+\frac{j}{4}\left[X_S(J)+X_T(J)\right]\right\}, \tag*{(7)}

where K,DK,D depend only on ξ\xi. For j=0,1j=0,1 the ratio is one.

Proof. Write HH for the shared-edge configuration and LS(H)L_S(H) for its tilted likelihood relative to its original law. Constancy of the full likelihood on ESE_S gives

Pr⁡(ES∣H)pS=LS(H)Pr⁡θ(ES∣H)Pr⁡θ(ES).\frac{\Pr(E_S \mid H)}{p_S}=L_S(H)\frac{\Pr_{\theta}(E_S \mid H)}{\Pr_{\theta}(E_S)}.

The last ratio is bounded by Corollary 2.2. Conditional on HH, the two events depend on disjoint sets of remaining edges. Their normalized joint probability is therefore at most KeDj2/kE[LS(H)LT(H)]K e^{D j^2/k}\mathbb{E}[L_S(H)L_T(H)]. For one shared edge with logit increments s,ts,t, put ψ(u)=log⁡(1−q+qeu)\psi(u)=\log(1-q+q e^u). Its contribution to the logarithm of the expectation is

ψ(s+t)−ψ(s)−ψ(t)=∫0s∫0tψ′′(u+v) dv du≤s2+t28.\psi(s+t)-\psi(s)-\psi(t)=\int_0^s\int_0^t\psi''(u+v)\,dv\,du\leq\frac{s^2+t^2}{8}.

since 0≤ψ′′≤1/40\leq\psi''\leq1/4. Sum over edges and use ∑a<b∈J(θa+θb)2≤2j∑a∈Jθa2\sum_{a<b\in J}(\theta_a+\theta_b)^2\leq2j\sum_{a\in J}\theta_a^2. For j≤1j\leq1 the two sets share no edge. ▫

For fixed SS and a uniform kk-set TT in [N][N], write Pj=Pr⁡(∣S∩T∣=j)P_j=\Pr(|S\cap T|=j). A union bound over the jj-subsets of SS yields

Pj≤(kj)(k)j(N)j≤min⁡{(k2N)j,(ek2jN)j},j≥1.(8)P_j\leq\binom{k}{j}\frac{(k)_j}{(N)_j}\leq\min\left\{\left(\frac{k^2}{N}\right)^j,\left(\frac{e k^2}{jN}\right)^j\right\},\qquad j\geq1. \tag*{(8)}

Here (k)j=k(k−1)⋯(k−j+1)(k)_j=k(k-1)\cdots(k-j+1). The next two results use different parts of this estimate. The first tolerates appreciable mean-square drift when typical overlaps are small. The second reaches the k3/2k^{3/2} block scale when every row is nearly balanced.

Theorem 3.2 (Mean-square drift). Let qq be an independent-edge array on NN vertices with qij∈[ξ,1−ξ]q_{ij}\in[\xi,1-\xi]. Write ai=(N−1)−1∑j≠iqij−pa_i=(N-1)^{-1}\sum_{j\neq i}q_{ij}-p for some p∈[ξ,1−ξ]p\in[\xi,1-\xi]. Suppose max⁡i∣ai∣≤α\max_i|a_i|\leq\alpha and N−1∑iai2≤η2N^{-1}\sum_i a_i^2\leq\eta^2. There exists cξ∗>0c_\xi^*>0 such that, uniformly when k→∞k\to\infty, α→0\alpha\to0, k2/N→0k^2/N\to0 and η2k≤cξ∗log⁡(N/k2)\eta^2k\leq c_\xi^*\log(N/k^2),

Pr⁡(Akc)≤Cξ(k2/N)3/2+Cξe−klog⁡k/8.\Pr(A_k^c)\leq C_\xi(k^2/N)^{3/2}+C_\xi e^{-k\log k/8}.

When η=0\eta=0 the first term can be replaced by Cξk4/N2C_\xi k^4/N^2.

Proof. Write HST=Pr⁡(ES∩ET)/(pSpT)H_{ST}=\Pr(E_S\cap E_T)/(p_Sp_T). For j=0,1j=0,1, HST−1=0H_{ST}-1=0. If UjU_j bounds HSTH_{ST} for all candidate pairs of overlap j≥2j\geq2, then

Var⁡Z(EZ)2=1∣F∣2∑S,T∈F(HST−1)≤(Nk)2∣F∣2∑j=2kPjUj≤4∑j=2kPjUj.\frac{\operatorname{Var} Z}{(\mathbb{E}Z)^2} =\frac{1}{|\mathcal{F}|^2}\sum_{S,T\in\mathcal{F}}(H_{ST}-1) \leq\frac{\binom{N}{k}^2}{|\mathcal{F}|^2}\sum_{j=2}^k P_jU_j \leq4\sum_{j=2}^k P_jU_j.

Indeed, exactly (Nk)2Pj\binom{N}{k}^2P_j ordered pairs of unrestricted kk-sets have intersection size jj. Write H0=log⁡(N/k2)H_0=\log(N/k^2). For 2≤j≤3k/42\leq j\leq3k/4, (7) and the total tilt energy give a ratio at most Kexp⁡(D0j+D1η2kj)K\exp(D_0j+D_1\eta^2kj). By (8) their contribution to Var⁡Z/(EZ)2\operatorname{Var}Z/(\mathbb{E}Z)^2 is at most 4K∑j≥2uj4K\sum_{j\geq2}u^j, where u=exp⁡(−H0+D0+D1η2k)u=\exp(-H_0+D_0+D_1\eta^2k). Choose D1cξ∗≤1/4D_1c_\xi^*\leq1/4. This sum is O(e−3H0/2)O(e^{-3H_0/2}), or O(e−2H0)O(e^{-2H_0}) when η=0\eta=0.

For j>3k/4j>3k/4, use Pr⁡(ES∩ET)/(pSpT)≤1/max⁡(pS,pT)≤eB\Pr(E_S\cap E_T)/(p_Sp_T)\leq1/\max(p_S,p_T)\leq e^B with B=12klog⁡k+C0(k+η2k2)B=\frac{1}{2}k\log k+C_0(k+\eta^2k^2). Now (8) gives Pj≤gjP_j\leq g^j with g=4ek/(3N)g=4ek/(3N). Since log⁡(N/k)=log⁡k+H0\log(N/k)=\log k+H_0,

B+(3k/4)log⁡g≤k{−14log⁡k−34H0+C0η2k+Oξ(1)}≤−18klog⁡kB+(3k/4)\log g\leq k\left\{-\frac{1}{4}\log k-\frac{3}{4}H_0+C_0\eta^2k+O_\xi(1)\right\}\leq-\frac{1}{8}k\log k

after taking C0cξ∗≤1/4C_0c_\xi^*\leq1/4. Sum the geometric tail, including j=kj=k, and apply Pr⁡(Z=0)≤Var⁡Z/(EZ)2\Pr(Z=0)\leq\operatorname{Var}Z/(\mathbb{E}Z)^2. ▫

Theorem 3.3 (A balanced block). Let the independent edges on [N][N] have probabilities in [ξ,1−ξ][\xi,1-\xi] and define ai=(N−1)−1∑j≠iqij−pa_i=(N-1)^{-1}\sum_{j\ne i}q_{ij}-p for p∈[ξ,1−ξ]p\in[\xi,1-\xi]. Fix M≥0M\ge0. There are L0,p0>0L_0,p_0>0 depending only on M,ξM,\xi such that, for all sufficiently large kk, if N≥L0k3/2N\ge L_0k^{3/2} and max⁡i∣ai∣≤M/k\max_i|a_i|\le\sqrt{M/k}, then Pr⁡(Ak)≥p0\Pr(A_k)\ge p_0. The successful candidates may all be tested at the same degree dd.

Proof. Apply Lemma 2.6 with α=η=M/k\alpha=\eta=\sqrt{M/k}. It gives one dd and a family occupying at least half of all kk-sets. For constants A≥1A\ge1 and CC depending only on M,ξM,\xi, every candidate satisfies

∥θS∥22≤A,∥θS∥∞2≤Alog⁡k/k,pS−1≤exp⁡(12klog⁡k+Ck).\|\theta^S\|_2^2\le A,\qquad\|\theta^S\|_\infty^2\le A\log k/k,\qquad p_S^{-1}\le\exp\left(\tfrac12 k\log k+Ck\right).

We bound EZ2/(EZ)2\mathbb{E}Z^2/(\mathbb{E}Z)^2 in three overlap ranges.

Small overlaps. For j≤t=⌊k/(Alog⁡k)⌋j\le t=\lfloor k/(A\log k)\rfloor, symmetry in (S,T)(S,T) and the arithmetic–geometric mean inequality bound the sum of exp⁡((j/4)(XS+XT))\exp((j/4)(X_S+X_T)) over candidate pairs of overlap jj by the corresponding sum of exp⁡(jXS/2)\exp(jX_S/2). More explicitly, 2ej(XS+XT)/4≤ejXS/2+ejXT/22e^{j(X_S+X_T)/4}\le e^{jX_S/2}+e^{jX_T/2} and the two sums on the right agree after swapping S,TS,T. Keep S∈FS\in\mathcal{F} fixed and extend the other sum to all TT. Each jj-subset J⊆SJ\subseteq S now occurs (N−kk−j)\binom{N-k}{k-j} times. Thus, for any nonnegative gSg_S and any jj with Pj>0P_j>0,

1∣F∣2∑S∈F∑∣T∣=k∣S∩T∣=jgS(S∩T)=(Nk)∣F∣Pj1∣F∣∑S∈FEJgS(J),\frac{1}{|\mathcal{F}|^2}\sum_{S\in\mathcal{F}}\sum_{\substack{|T|=k\\|S\cap T|=j}}g_S(S\cap T) =\frac{\binom{N}{k}}{|\mathcal{F}|}P_j\frac{1}{|\mathcal{F}|}\sum_{S\in\mathcal{F}}\mathbb{E}_Jg_S(J),

where JJ on the right is uniform among the jj-subsets of SS. The factor in front of PjP_j is at most two. Assign a zero contribution when Pj=0P_j=0. The elementary symmetric mean bound (4) and eu≤1+2ue^u\le1+2u on [0,1][0,1] give

EJejXS(J)/2≤(k−1∑v∈Sej(θvS)2/2)j≤(1+Aj/k)j≤eAj2/k.\mathbb{E}_J e^{jX_S(J)/2}\le\left(k^{-1}\sum_{v\in S}e^{j(\theta_v^S)^2/2}\right)^j\le(1+Aj/k)^j\le e^{Aj^2/k}.

The normalized contribution is at most 2K∑j≤tPje(D+A)j2/k2K\sum_{j\le t}P_je^{(D+A)j^2/k}. Put μ=k2/N\mu=k^2/N and s=⌈max⁡(e2μ,log⁡k)⌉s=\lceil\max(e^2\mu,\log k)\rceil. The terms through min⁡(s,t)\min(s,t) sum to at most exp⁡((D+A)s2/k)∑jPj=O(1)\exp((D+A)s^2/k)\sum_jP_j=O(1), since N≥L0k3/2N\ge L_0k^{3/2} gives s=O(k+log⁡k)s=O(\sqrt{k}+\log k). For s<j≤ts<j\le t, (3.2) gives Pj≤e−jP_j\le e^{-j} and (D+A)j2/k≤j/2(D+A)j^2/k\le j/2 eventually.

Intermediate overlaps. For t<j≤3k/4t<j\le3k/4, use XS,XT≤AX_S,X_T\le A in (7). The resulting sum is at most 4K∑j>t(C1μ/j)j=o(1)4K\sum_{j>t}(C_1\mu/j)^j=o(1) since μ/t=O((log⁡k)/k)\mu/t=O((\log k)/\sqrt{k}).

Large overlaps. For j>3k/4j>3k/4 put m=k−jm=k-j. Condition on all edges of SS. Each vertex of JJ needs a specified number of edges to T∖ST\setminus S to reach dd in TT. Those jj sums involve disjoint sets of fresh edges, so they are conditionally independent. For a sum YY of mm independent Bernoulli variables of floor δ\delta, one-dimensional inversion gives

sup⁡ℓ∈ZPr⁡(Y=ℓ)≤12π∫−ππe−2mδ(1−δ)sin⁡2(t/2) dt≤Cδm+1.(9)\sup_{\ell\in\mathbb{Z}}\Pr(Y=\ell)\le\frac{1}{2\pi}\int_{-\pi}^{\pi}e^{-2m\delta(1-\delta)\sin^2(t/2)}\,dt\le\frac{C_\delta}{\sqrt{m+1}}. \tag*{(9)}

Use sin⁡(∣t∣/2)≥∣t∣/π\sin(|t|/2)\ge|t|/\pi and take Cδ≥1C_\delta\ge1 for m=0m=0. If GSG_S denotes the exposed edges, ESE_S is GSG_S-measurable and Pr⁡(ET∣GS)≤(Cξ/m+1)j\Pr(E_T\mid G_S)\le(C_\xi/\sqrt{m+1})^j. Multiplying by 1ES\mathbf{1}_{E_S} and taking expectations gives HST≤pT−1(Cξ/m+1)jH_{ST}\le p_T^{-1}(C_\xi/\sqrt{m+1})^j, including S=TS=T. Multiply by Pj≤(4ek/(3N))jP_j\le(4ek/(3N))^j. The logarithm of the product is at most

12{mlog⁡k−jlog⁡(m+1)}+C2k−jlog⁡L0.\tfrac12\{m\log k-j\log(m+1)\}+C_2k-j\log L_0.

For 0≤m≤k/40\le m\le k/4, concavity gives log⁡(m+1)≥(4m/k)log⁡(1+k/4)\log(m+1)\ge(4m/k)\log(1+k/4). As 4j/k≥14j/k\ge1, the braces are at most mlog⁡[k/(1+k/4)]≤klog⁡4m\log[k/(1+k/4)]\le k\log4. The constant C2C_2 depends only on M,ξM,\xi. Choose 34log⁡L0≥C2+1+12log⁡4\frac{3}{4}\log L_0 \ge C_2 + 1 + \frac{1}{2}\log4. After accounting for the candidate fraction, the entire range contributes at most 4(k+1)e−k4(k+1)e^{-k}. This last estimate retains the information in the mm fresh vertices even when the two candidates nearly coincide.

The normalized second moment is bounded by a constant independent of k,Nk,N. Cauchy–Schwarz gives Pr⁡(Z>0)≥(EZ)2/EZ2\Pr(Z>0) \ge(\mathbb{E}Z)^2/\mathbb{E}Z^2.

Extraction with small mean-square degree variation

For a symmetric array qij∈[0,1]q_{ij} \in[0,1], i≠j∈Vi \ne j \in V, of order M≥2M \ge2, write

eq(S)=∑{i,j}⊆Sqij,di=∑j≠iqij,p=eq(V)(M2),dˉ=p(M−1).e_q(S)=\sum_{\{i,j\}\subseteq S}q_{ij},\qquad d_i=\sum_{j\ne i}q_{ij},\qquad p=\frac{e_q(V)}{\binom{M}{2}},\qquad\bar d=p(M-1).

Its normalized degree variance is

v=1M3∑i∈V(di−dˉ)2.v=\frac{1}{M^3}\sum_{i\in V}(d_i-\bar d)^2.

The next argument uses a nonuniform random vertex sample only to establish the existence of a deterministic induced subarray.

Lemma 4.1 (A variance-driven density increment). Suppose M≥32M \ge32. If v>16e−M/8v>16e^{-M/8}, there is a set S⊆VS\subseteq V of order at least M/4M/4 whose induced weighted density is greater than p+v/2p+v/2.

Proof. Put ai=(di−dˉ)/Ma_i=(d_i-\bar d)/M. Then

∑iai=0,∣ai∣≤1,∑iai2=Mv,∑iaidi=M2v.\sum_i a_i=0,\qquad|a_i|\le1,\qquad\sum_i a_i^2=Mv,\qquad\sum_i a_i d_i=M^2v.

Select vertices independently with probabilities wi=1/2+ai/4∈[1/4,3/4]w_i=1/2+a_i/4\in[1/4,3/4], and call the resulting set SS. Its expected order is M/2M/2. Expansion of the edge expectation gives

Eeq(S)=pM(M−1)8+18∑iaidi+116∑i<jqijaiaj.\mathbb{E}e_q(S)=\frac{pM(M-1)}{8}+\frac{1}{8}\sum_i a_i d_i+\frac{1}{16}\sum_{i<j}q_{ij}a_i a_j.

Since

∣∑i<jqijaiaj∣≤12(∑i∣ai∣)2≤M2∑iai2=12M2v,\left|\sum_{i<j}q_{ij}a_i a_j\right|\le\frac{1}{2}\left(\sum_i|a_i|\right)^2\le\frac{M}{2}\sum_i a_i^2=\frac{1}{2}M^2v,

we obtain

Eeq(S)≥pM(M−1)8+3M2v32.(10)\mathbb{E}e_q(S)\ge\frac{pM(M-1)}{8}+\frac{3M^2v}{32}. \tag*{(10)}

Also ∑iwi2=M/4+Mv/16\sum_i w_i^2=M/4+Mv/16, so independence gives

E(∣S∣2)=M(M−1)8−Mv32.(11)\mathbb{E}\binom{|S|}{2}=\frac{M(M-1)}{8}-\frac{Mv}{32}. \tag*{(11)}

Subtracting (p+v/2)(p+v/2) times (11) from (10) yields

E[eq(S)−(p+v/2)(∣S∣2)]≥M2v32.(12)\mathbb{E}\left[e_q(S)-(p+v/2)\binom{|S|}{2}\right]\ge\frac{M^2v}{32}. \tag*{(12)}

Here all discarded terms are nonnegative, since $p,v\ge 0.

The bounded-summand exponential estimate, applied to the independent vertex indicators of total mean M/2M/2, gives Pr⁡(∣S∣<M/4)≤e−M/8\Pr(|S| < M/4) \le e^{-M/8}. If every set of order at least M/4M/4 had weighted density at most p+v/2p+v/2, the random surplus in (12) would be nonpositive off that exceptional event. On the event it is at most eq(S)≤M2/2e_q(S) \le M^2/2. Its expectation would therefore be at most M2e−M/8/2M^2e^{-M/8}/2, contradicting v>16e−M/8v > 16e^{-M/8}. The resulting set has at least two vertices since M≥32M \ge32.

Lemma 4.2 (Mean-square extraction). Let 0<η≤1/160 < \eta\le1/16, and put

J=⌈2η2⌉,M0=max⁡{32,8log⁡16η2}.J=\left\lceil\frac{2}{\eta^2}\right\rceil,\qquad M_0=\max\left\{32,8\log\frac{16}{\eta^2}\right\}.

If n≥4JM0n \ge4^J M_0, every symmetric array in [0,1][0,1] on nn vertices has an induced subarray of order

N≥124−JnN \ge\frac{1}{2}4^{-J}n

whose degree sums di′d'_i and average dˉ′\bar d' satisfy

max⁡i∣di′−dˉ′∣≤3η(N−1),1N∑i(di′−dˉ′)2≤6η2(N−1)2.(13)\max_i |d'_i-\bar d'|\le3\sqrt{\eta}(N-1),\qquad\frac{1}{N}\sum_i(d'_i-\bar d')^2\le6\eta^2(N-1)^2. \tag*{(13)}

In particular the logarithm of the vertex loss is O(η−2)O(\eta^{-2}). If the initial entries lie in [ξ,1−ξ][\xi,1-\xi], then so do the extracted entries and their common density dˉ′/(N−1)\bar d'/(N-1).

Proof. Repeatedly restrict the current array to a set supplied by Lemma 4.1 whenever its normalized degree variance exceeds η2\eta^2. Through the first JJ restrictions, whenever defined, the current order after t≤Jt\le J steps is at least 4−tn≥M04^{-t}n\ge M_0, so 16e−M/8≤η216e^{-M/8}\le\eta^2 and the increment lemma applies. Each restriction retains at least one quarter of the vertices and increases the density by more than η2/2\eta^2/2. There are fewer than JJ restrictions, since JJ such increases would raise a nonnegative initial density above one. The terminal subarray therefore has order M≥4−JnM\ge4^{-J}n and

∑i(di−dˉ)2≤η2M3.\sum_i(d_i-\bar d)^2\le\eta^2M^3.

Remove the set BB of vertices satisfying ∣di−dˉ∣>ηM|d_i-\bar d|>\sqrt{\eta}M. Its size is at most ηM\eta M. Let U=V∖BU=V\setminus B, N=∣U∣N=|U|, and let di′d'_i denote the degree sums of the remaining subarray. Then N≥(1−η)M≥15M/16N\ge(1-\eta)M\ge15M/16. For i∈Ui\in U, write

di′−dˉ=(di−dˉ)−si,si=∑b∈Bqib∈[0,ηM].d'_i-\bar d=(d_i-\bar d)-s_i,\qquad s_i=\sum_{b\in B}q_{ib}\in[0,\eta M].

Consequently

max⁡i∈U∣di′−dˉ∣≤(η+η)M,∑i∈U(di′−dˉ)2≤2η2M3+2Nη2M2≤4η2M3.\max_{i\in U}|d'_i-\bar d|\le(\sqrt{\eta}+\eta)M,\qquad\sum_{i\in U}(d'_i-\bar d)^2\le2\eta^2M^3+2N\eta^2M^2\le4\eta^2M^3.

Centering at the new average dˉ′\bar d' cannot increase the sum of squares, and it increases the preceding maximum bound by at most a factor of two. Since M≥32M\ge32,

N−1≥15M16−1≥7M8.N-1\ge\frac{15M}{16}-1\ge\frac{7M}{8}.

Using η≤η/4\eta\le\sqrt{\eta}/4, we find

max⁡i∣di′−dˉ′∣≤52ηM≤207η(N−1)<3η(N−1).\max_i|d'_i-\bar d'|\le\frac{5}{2}\sqrt{\eta}M\le\frac{20}{7}\sqrt{\eta}(N-1)<3\sqrt{\eta}(N-1).

Similarly,

∑i(di′−dˉ′)2N(N−1)2≤4η2MN(MN−1)2≤4η21615(87)2<6η2.(14)\frac{\sum_i (d'_i-\bar d')^2}{N(N-1)^2}\le4\eta^2\frac{M}{N}\left(\frac{M}{N-1}\right)^2\le4\eta^2\frac{16}{15}\left(\frac{8}{7}\right)^2<6\eta^2. \tag*{(14)}

These are (4.4). The size bound follows from N≥15M/16≥M/2N\ge15M/16\ge M/2. The entry and density assertions follow by restriction and averaging.

Theorem 4.3 (A universal squared-logarithmic lower bound). For every fixed ξ∈(0,1/2)\xi\in(0,1/2) there are constants cξ>0c_\xi>0 and n0(ξ)n_0(\xi) such that, for all n≥n0(ξ)n\ge n_0(\xi),

sup⁡p∈[ξ,1−ξ](n)Pr⁡{R(G(p))<cξ(log⁡n)2}≤n−1.\sup_{p\in[\xi,1-\xi]}^{(n)} \Pr\{R(G(\mathbf{p}))<c_\xi(\log n)^2\}\le n^{-1}.

Proof. Put L=log⁡nL=\log n and choose η2=32/L\eta^2=32/L. For sufficiently large nn, η≤1/16\eta\le1/16 and

Jlog⁡4≤(L16+1)log⁡4≤L/4,log⁡M0=O(log⁡log⁡L).J\log4\le\left(\frac{L}{16}+1\right)\log4\le L/4,\qquad\log M_0=O(\log\log L).

Thus the onset of Lemma 4.2 holds. Applied directly to the given probability array, it supplies a deterministic induced domain of order N≥n3/4/2N\ge n^{3/4}/2. On this domain the normalized maximum degree-sum drift is at most 3η=o(1)3\sqrt{\eta}=o(1), and the normalized root-mean-square drift is at most ζ=6η\zeta=\sqrt{6\eta}, so ζ2=192/L\zeta^2=192/L.

Let cξ∗c_\xi^* be the tolerance constant in Theorem 3.2, choose a>0a>0 with 192a<cξ∗/2192a<c_\xi^*/2, and take

k=2⌊a2L2⌋.k=2\left\lfloor\frac{a}{2}L^2\right\rfloor.

Then k→∞k\to\infty, k2/N→0k^2/N\to0, and uniformly for N∈[n3/4/2,n]N\in[n^{3/4}/2,n],

log⁡(N/k2)≥L/2,ζ2k≤192aL<cξ∗log⁡(N/k2).\log(N/k^2)\ge L/2,\qquad\zeta^2k\le192aL<c_\xi^*\log(N/k^2).

Theorem 3.2 therefore gives a regular induced kk-set with failure probability at most

Cξ(k2/N)3/2+Cξe−klog⁡k/8=Oξ(L6n−9/8)+e−Ωξ(L2log⁡L)=o(n−1).C_\xi(k^2/N)^{3/2}+C_\xi e^{-k\log k/8}=O_\xi(L^6n^{-9/8})+e^{-\Omega_\xi(L^2\log L)}=o(n^{-1}).

After enlarging the onset, this is at most n−1n^{-1}. Since k≥(a/2)L2k\ge(a/2)L^2 eventually, take cξ=a/2c_\xi=a/2. All selections and estimates used only the deterministic probability array, and every constant is independent of its individual entries.

Corollary 4.4 (Amplified probability and almost-sure form). Let cξc_\xi be a constant for which Theorem 4.3 holds. For every fixed 0<cξ′<cξ/40<c'_\xi<c_\xi/4 and all sufficiently large nn,

sup⁡p∈[ξ,1−ξ](n)Pr⁡{R(G(p))<cξ′(log⁡n)2}≤exp⁡{−18nlog⁡n}.\sup_{p\in[\xi,1-\xi]}^{(n)}\Pr\{R(G(\mathbf{p}))<c'_\xi(\log n)^2\}\le\exp\{-\tfrac{1}{8}\sqrt{n}\log n\}.

Consequently, if (Gn)(G_n) is any sequence of random graphs on [n][n] with independent edges within each graph and all its probabilities in [ξ,1−ξ][\xi,1-\xi], then almost surely

R(Gn)≥cξ′(log⁡n)2for all sufficiently large n.R(G_n)\ge c'_\xi(\log n)^2\qquad\text{for all sufficiently large }n.

No independence between different members of the sequence is needed.

Proof. Set m=⌊n⌋m=\lfloor\sqrt n\rfloor and r=⌊n/m⌋r=\lfloor n/m\rfloor. Choose rr disjoint blocks of mm vertices. Each block fails to contain the universal witness with probability at most m−1m^{-1}. The induced graphs on the blocks use disjoint sets of independent edge variables, so the probability that all blocks fail is at most

m−r=e−rlog⁡m≤e−nlog⁡n/8m^{-r}=e^{-r\log m}\le e^{-\sqrt n\log n/8}

for large nn: use r≥n/2r \ge\sqrt{n}/2 and log⁡m≥(log⁡n)/4\log m \ge(\log n)/4. Since (log⁡m)2/(log⁡n)2→1/4(\log m)^2/(\log n)^2 \to1/4, any successful block supplies the asserted order for every fixed cξ′<cξ/4c'_{\xi} < c_{\xi}/4.

The error probabilities are summable in nn. The probability of any failure at an index n≥Nn \ge N is at most the tail of their convergent sum, which tends to zero as N→∞N \to\infty. Thus almost surely only finitely many failures occur, without a condition on the dependence across indices.

Amplification and structured arrays

The block size in Theorem 3.3 is m=⌈L0k3/2⌉m = \lceil L_0 k^{3/2}\rceil. To obtain (1) we need a positive success probability in order n/mn/m disjoint blocks of this size. The blocks must be chosen before revealing any edges. Equal expected degrees allow a random partition argument, while the kernel and rank assumptions allow a deterministic choice.

Equal expected degrees

Let pp be the common normalized expected degree. Use Theorem 3.3 with M=1M = 1, and choose aa small enough that n≥2mn \ge2m when k≤an2/3k \le an^{2/3}. Take a uniform permutation and group its first m⌊n/m⌋m\lfloor n/m\rfloor positions into blocks of size mm. Conditional on a vertex occupying a specified position in a given block, the other m−1m-1 vertices there are sampled without replacement from the other n−1n-1 vertices. The probability that its block row mean differs from pp by more than 1/k1/\sqrt{k} is at most 2exp⁡[−2(m−1)/k]2\exp[-2(m-1)/k]. The probability that a specified block contains any such row is at most 2mexp⁡[−2(m−1)/k]<1/22m\exp[-2(m-1)/k] < 1/2 for large kk. Taking expectations, some partition has at least half its blocks good. This argument only requires a bound on the fraction of bad blocks, so its onset is independent of nn.

Fix that partition. Every good block meets the hypotheses of Theorem 3.3. Since their induced graphs use disjoint edge coordinates, the probability that they all fail is at most (1−p0)⌊n/m⌋/2≤exp⁡(−cn/k3/2)(1-p_0)^{\lfloor n/m\rfloor/2} \le\exp(-cn/k^{3/2}). This proves the equal-degree assertion of Theorem 1.1.

Packing blocks from large cells

Lemma 5.1. Suppose there are fixed s≥0s \ge0, b>0b > 0 and B≥0B \ge0 with the following property. For each induced domain of order uu and each 0<h≤10 < h \le1 with buhs≥2buh^s \ge2, the domain contains a set of at least buhsbuh^s vertices on which the off-diagonal probabilities lie within BhBh of a common p∈[ξ,1−ξ]p \in[\xi,1-\xi]. Then (1) holds up to k≤an2/(s+3)k \le an^{2/(s+3)}, uniformly with constants depending on ss, bb, BB, ξ\xi.

Proof. Take h=k−1/2h = k^{-1/2} and m=⌈L0k3/2⌉m = \lceil L_0 k^{3/2}\rceil, with L0L_0 from Theorem 3.3 for M=B2M = B^2. For aa small enough, b(n/2)k−s/2≥mb(n/2)k^{-s/2} \ge m throughout the stated range. While at least n/2n/2 vertices remain, find such a cell, take exactly mm of its vertices as a block, and remove just that block. Every restriction of the cell still has all pair probabilities within B/kB/\sqrt{k} of pp, so all block row means satisfy the same bound. This produces at least n/(2m)n/(2m) disjoint blocks, independently of the graph realization. Apply Theorem 3.3 in each and multiply their failure probabilities.

Lipschitz types. Partition the type cube into at most (2/h)d(2/h)^d cubes of maximum-norm diameter hh. In every domain of uu vertices some cube contains at least u(h/2)du(h/2)^d types. Symmetry of WW gives the Lipschitz estimate in either argument, so the range of the edge probabilities there is at most 2Lh2Lh. Taking any off-diagonal entry as pp verifies the hypothesis of Lemma 5.1 with s=ds=d. No assumption on the empirical distribution of the types is required.

Rank and diagonal subdivision. Let PP be a bounded symmetric completion of rank at most rr. A direct covering of its row coordinates at resolution hh would give s=rs=r. Symmetry permits the coarser resolution h\sqrt{h} in those coordinates, provided one also controls the diagonal. This improves the cell exponent to (r+1)/2(r+1)/2.

Lemma 5.2. Every principal submatrix of order uu contains a set of at least cruh(r+1)/2c_ruh^{(r+1)/2} vertices on which the range of all entries is at most (1+r2)h(1+r^2)h, for 0<h≤10<h\le1.

Proof. Write t≤rt\le r for the rank of the submatrix, still called PP. The case t=0t=0 is immediate. Choose row indices II and column indices JJ for a tt-minor of maximum absolute determinant. Each row is a linear combination of the rows indexed by II. Cramer’s rule on the columns JJ shows that its coefficients xi∈Rtx_i\in\mathbb{R}^t lie in [−1,1]t[-1,1]^t. By symmetry, with B=PI,IB=P_{I,I},

Pij=xiTBxj,∣Bℓm∣≤1.P_{ij}=x_i^T Bx_j,\qquad|B_{\ell m}|\le1.

Set w=hw=\sqrt{h} and retain a largest coordinate cube of side ww. It has at least u(w/3)ru(w/3)^r vertices. On it the diagonal values xiTBxix_i^T Bx_i have range at most 2r2w2r^2w, by expanding their pairwise differences. Subdivision into intervals of length hh now costs at most (2r2+1)/w(2r^2+1)/w further classes. Keep a largest class. For any two of its vertices,

2Pij=Pii+Pjj−(xi−xj)TB(xi−xj).2P_{ij}=P_{ii}+P_{jj}-(x_i-x_j)^T B(x_i-x_j).

The last term has absolute value at most r2w2=r2hr^2w^2=r^2h. The first two diagonal terms each range over an interval of length hh, so the pair entries have range at most (1+r2)h(1+r^2)h. The retained fraction is at least wr+1/[3r(2r2+1)]w^{r+1}/[3^r(2r^2+1)].

On a cell with at least two vertices, choose an off-diagonal entry as the common pp. Lemma 5.1 with s=(r+1)/2s=(r+1)/2 gives β=2/(s+3)=4/(r+7)\beta=2/(s+3)=4/(r+7), completing the proof of Theorem 1.1.

Conditional environments. The upper bounds on failure are uniform in the array. They therefore remain valid after averaging over a random environment, whenever the hypotheses hold almost surely with the same parameters and the conditional edge law is the indicated product law. For independent toggling of an arbitrary base graph with probability ξ\xi, the two possible edge probabilities are ξ\xi and 1−ξ1-\xi. The unrestricted logarithmic bounds always apply. If the base is regular, the perturbed expected degrees ξ(n−1)+(1−2ξ)dbase(i)\xi(n-1)+(1-2\xi)d_{\mathrm{base}}(i) are equal, so the balanced bound applies as well.

A sharp square-root example

For a,b>0a,b>0 with a+b<1a+b<1, take

zi=a+bi/n,pij=zizj,1≤i<j≤n.z_i=a+bi/n,\qquad p_{ij}=z_i z_j,\qquad1\le i<j\le n.

Alon, Krivelevich and Sudakov used the choice a=1/4a=1/4, b=1/2b=1/2 to obtain an upper bound of order n(log⁡n)3/4\sqrt{n}(\log n)^{3/4} [1 Section 3]. We determine the order for the same product model over the full fixed parameter range. The array has rank-one completion zzTzz^T and is generated by the Lipschitz kernel W(x,y)=(a+bx)(a+by)W(x,y)=(a+bx)(a+by) on the unit interval. Given ξ\xi, choosing a=ξa=\sqrt{\xi} and a+b=1−ξa+b=\sqrt{1-\xi} realizes that floor. The lower bounds for rank one and dimension one coincide. An upper bound for the very same array shows that neither class admits a larger uniform order of growth.

Theorem 6.1. There are constants c,C>0c,C>0, depending only on a,ba,b, such that

Pr⁡{cn≤R≤Cn}⟶1.\Pr\{c\sqrt{n}\le R\le C\sqrt{n}\}\longrightarrow1.

Take ξ<min⁡{a2,1−(a+b)2,1/2}\xi< \min\{a^2, 1-(a+b)^2, 1/2\} and k=⌊κn⌋k=\lfloor\kappa\sqrt{n}\rfloor for a sufficiently small fixed κ>0\kappa>0. Then (1) bounds failure by exp⁡(−c1n1/4)\exp(-c_1n^{1/4}), and k≥(κ/2)nk\ge(\kappa/2)\sqrt{n} eventually. For the upper bound, two effects must be retained at once. A set with little variation in its vertex weights still pays the local probability cost of making all its degrees equal. A set with widely dispersed weights pays an additional cost for the variation in its expected degrees.

Proposition 6.2. For a fixed kk-set SS, k≥3k\ge3, write μi=∑j∈S∖{i}pij\mu_i=\sum_{j\in S\setminus\{i\}}p_{ij}, μˉ=k−1∑iμi\bar{\mu}=k^{-1}\sum_i\mu_i, and V(S)=∑i(μi−μˉ)2V(S)=\sum_i(\mu_i-\bar{\mu})^2. Under the fixed floor,

Pr⁡(G[S] is regular)≤(Cξk)kexp⁡[−2V(S)k−2].(15)\Pr(G[S]\text{ is regular})\le\left(\frac{C_\xi}{\sqrt{k}}\right)^k\exp\left[-\frac{2V(S)}{k-2}\right]. \tag*{(15)}

With arbitrary probabilities in [0,1][0,1] the bound exp⁡[−2V(S)/(k−2)]\exp[-2V(S)/(k-2)] alone still holds.

Proof. Put vi=μi−μˉv_i=\mu_i-\bar{\mu} and tilt by θi=−4vi/(k−2)\theta_i=-4v_i/(k-2). On every regular outcome θ⋅D=0\theta\cdot D=0. Writing Ψ(θ)=∑i<jlog⁡(1−pij+pijeθi+θj)\Psi(\theta)=\sum_{i<j}\log(1-p_{ij}+p_{ij}e^{\theta_i+\theta_j}), the likelihood identity therefore gives Pr⁡0(regular)=eΨ(θ)Pr⁡θ(regular)\Pr_0(\mathrm{regular})=e^{\Psi(\theta)}\Pr_\theta(\mathrm{regular}). The curvature of every one-edge log partition function is at most 1/41/4. As ∑ivi=0\sum_i v_i=0 and ∑i<j(vi+vj)2=(k−2)V(S)\sum_{i<j}(v_i+v_j)^2=(k-2)V(S),

Ψ(θ)≤∑iθiμi+18∑i<j(θi+θj)2=−2V(S)k−2.\Psi(\theta)\le\sum_i\theta_i\mu_i+\frac18\sum_{i<j}(\theta_i+\theta_j)^2=-\frac{2V(S)}{k-2}.

This proves the floor-free estimate, including deterministic edge coordinates. Under the fixed floor the tilt preserves a positive floor depending only on ξ\xi, since ∣θi∣≤4(k−1)/(k−2)≤8|\theta_i|\le4(k-1)/(k-2)\le8. Under the tilted law, fix a degree dd and expose the edges in rows i=1,…,ki=1,\ldots,k, revealing ijij with j>ij>i at step ii. Given the previous rows, the required number of successes in the k−ik-i fresh trials is fixed. By (9) its conditional probability is at most C/k−i+1C/\sqrt{k-i+1}, uniformly in the history. Earlier degree constraints are measurable at this point. Iterating conditional expectations gives at most Ck/k!C^k/\sqrt{k!} for the prescribed degree vector, as in the exposure argument of [1 Section 3]. Summing over the kk possible degrees, using k!≥(k/e)kk!\ge(k/e)^k and k≤2kk\le2^k, gives (Cξ/k)k(C_\xi/\sqrt{k})^k for tilted regularity. Multiplying by the exponential penalty proves (15).

Upper bound in Theorem 6.1. For the product array μi=zi(∑ℓ∈Szℓ−zi)\mu_i=z_i(\sum_{\ell\in S}z_\ell-z_i). Therefore

∣μi−μj∣=∣zi−zj∣∑ℓ∈S∖{i,j}zℓ≥(ab/n)(k−2)∣i−j∣.|\mu_i-\mu_j|=|z_i-z_j|\sum_{\ell\in S\setminus\{i,j\}}z_\ell\ge(ab/n)(k-2)|i-j|.

Use V(S)=(2k)−1∑i,j∈S(μi−μj)2V(S)=(2k)^{-1}\sum_{i,j\in S}(\mu_i-\mu_j)^2 and choose v∈Sv\in S minimizing ∑i∈S(i−v)2\sum_{i\in S}(i-v)^2. The minimum is at most its average over vv. It follows that

2V(S)k−2≥(ab)2(k−2)n2∑i∈S(i−v)2≥λkn2∑i∈S(i−v)2,λ=(ab)23.\frac{2V(S)}{k-2}\ge\frac{(ab)^2(k-2)}{n^2}\sum_{i\in S}(i-v)^2\ge\frac{\lambda k}{n^2}\sum_{i\in S}(i-v)^2,\qquad\lambda=\frac{(ab)^2}{3}.

For a fixed anchor vv, set wi=exp⁡[−λk(i−v)2/n2]w_i=\exp[-\lambda k(i-v)^2/n^2]. Comparing the decreasing Gaussian on either side of vv with its integral gives ∑iwi≤Ca,bn/k\sum_iw_i\le C_{a,b}n/\sqrt{k}. The sum of ∏i∈Swi\prod_{i\in S}w_i over the kk-sets containing vv is at most (∑iwi)k−1/(k−1)!(\sum_iw_i)^{k-1}/(k-1)!, since wv=1w_v=1. Sum (15) over the nn choices of anchor, using the bound just obtained for the sets assigned to each. With k!≥(k/e)kk!\ge(k/e)^k this yields

Pr⁡(Ak)≤k3/2(Da,bn/k2)k.\Pr(A_k)\le k^{3/2}(D_{a,b}n/k^2)^k.

Choose CC so that Da,b/C2<1/2D_{a,b}/C^2<1/2. Summing this bound over all k≥Cnk\ge C\sqrt{n} gives o(1)o(1) and hence the asserted upper tail for RR.

The unrestricted problem. Does every fixed floor ξ\xi admit a βξ>0\beta_{\xi}>0 for which inf⁡pPr⁡(R≥nβξ)→1\inf_p \Pr(R \ge n^{\beta_{\xi}}) \to1? The product example forces βξ≤1/2\beta_{\xi} \le1/2 at the exponent level. The density increment in Section 4 yields a logarithmic power for general arrays. Proposition 6.2 indicates what obstructs a larger witness: for instance Pr⁡(Ak)≥γ\Pr(A_k) \ge\gamma implies that some kk-set satisfies V(S)≤k−22log⁡(k/γ)V(S) \le\frac{k-2}{2}\log(k/\gamma) by the floor-free bound. To obtain the corresponding test for R≥kR \ge k, one must sum over every order ℓ≥k\ell\ge k, as in the proof above.

Fourier estimates for the degree vector

We give the proof of Lemma 2.1 in a form that treats the complete and deleted arrays together. The saddle-point calculation follows the degree-enumeration method of Barvinok and Hartigan [2]; see also Isaev and McKay [5]. Here the edge logits are arbitrary and the residual upper bound holds at any integral target.

Let E\mathcal{E} be the available pairs after deleting the pairs in JJ (take J=∅J=\varnothing for the full array), let QE=∑e∈EweueueTQ_{\mathcal{E}}=\sum_{e\in\mathcal{E}} w_eu_eu_e^{T}, and set

ΞE=(2π)k/2(det⁡QE)−1/2,M(t)=∏ab∈E∣1−qab+qabei(ta+tb)∣.\Xi_{\mathcal{E}}=(2\pi)^{k/2}(\det Q_{\mathcal{E}})^{-1/2}, \qquad M(t)=\prod_{ab\in\mathcal{E}}\left|1-q_{ab}+q_{ab}e^{i(t_a+t_b)}\right|.

Integration is with respect to Lebesgue measure on Tk=[−π,π)k\mathbb{T}^k=[-\pi,\pi)^k. Fourier inversion contributes the separate factor (2π)−k(2\pi)^{-k}.

The covariance. Write m=k−∣J∣≥(1−ρ)km=k-|J|\ge(1-\rho)k. In the unweighted sum ∑e∈EueueT\sum_{e\in\mathcal{E}}u_eu_e^{T}, contrasts within JJ and within its complement have eigenvalues mm and k−2k-2 respectively. On the two normalized constant vectors of those sets the matrix is

(m∣J∣m∣J∣mk+m−2)\begin{pmatrix} m & \sqrt{|J|m}\\ \sqrt{|J|m} & k+m-2 \end{pmatrix}

Its determinant is 2m(m−1)2m(m-1) and its trace is at most 3k3k. Taking the variance floor into account, or using the complete-pair identity of Lemma 2.3 for J=∅J=\varnothing, gives

cδ,ρkI⪯QE⪯(k−1)I/2.(16)c_{\delta,\rho}kI \preceq Q_{\mathcal{E}} \preceq(k-1)I/2. \tag*{(16)}

The two peaks. Put rk=(log⁡k)/kr_k=(\log k)/\sqrt{k}. Only the cubes of radius rkr_k around 00 and π1\pi\mathbf{1} contribute on the scale ΞE\Xi_{\mathcal{E}}. Here is the tail estimate, including the case of deletions. Fix 0<ε<π/10000<\varepsilon<\pi/1000 and call an available pair bad when the circular distance of ti+tjt_i+t_j from zero exceeds ε\varepsilon. Since

∣1−q+qeiu∣2=1−4q(1−q)sin⁡2(u/2),\left|1-q+qe^{iu}\right|^2=1-4q(1-q)\sin^2(u/2),

the region with at least k(log⁡k)2k(\log k)^2 bad pairs has integral at most (2π)ke−ck(log⁡k)2=o(ΞE)(2\pi)^k e^{-ck(\log k)^2}=o(\Xi_{\mathcal{E}}) by (A.1). Otherwise there is a vertex outside JJ incident with Oρ((log⁡k)2)O_{\rho}((\log k)^2) bad pairs. Among its good neighbors outside JJ there are Ωρ(k2)\Omega_{\rho}(k^2) available pairs, so at least one of them is good. The three pair sums in this triangle put twice the angle of the chosen vertex within 3ε3\varepsilon of zero. All but R0=Oρ((log⁡k)2)R_0=O_{\rho}((\log k)^2) angles are consequently within 3ε3\varepsilon of the same b∈{0,π}b\in\{0,\pi\}.

Outside the cube of radius 10ε10\varepsilon about bb, fix an exceptional angle tit_i. It has at least (1−ρ)k−R0−1(1-\rho)k-R_0-1 available neighbors in this core. Replacing tit_i by ss within ε\varepsilon of bb moves their pair sums from distances above 7ε7\varepsilon to distances below 4ε4\varepsilon (allowing equality at the latter endpoint). Each corresponding factor gains a fixed ratio eγ>1e^\gamma>1. For the other available neighbors, exclude from the replacement interval a k−2k^{-2}-neighborhood of each π−tj\pi-t_j. This leaves length at least ε\varepsilon and bounds those factors below by k−2/πk^{-2}/\pi, since ∣1−q+qeiu∣≤∣cos⁡(u/2)∣\left|1-q+qe^{iu}\right|\le|\cos(u/2)|. In particular we can take R0=⌈4(1−ρ)−1log⁡2k⌉+2R_0=\lceil4(1-\rho)^{-1}\log^2 k\rceil+2 and fix a core of exactly k−R0k-R_0 coordinates. For fixed core, exceptional index ii, and all angles except tit_i, let I∗I^* be the surviving replacement interval with the exclusions above. For all s∈I∗s \in I^* and all bad values tit_i at distance greater than 10ε10\varepsilon from bb,

M(t)≤e−γ((1−ρ)k−R0−1)(πk2)R0M(t−i,s)≤e−ckM(t−i,s).M(t) \le e^{-\gamma((1-\rho)k-R_0-1)(\pi k^2)^{R_0}}M(t_{-i},s) \le e^{-ck}M(t_{-i},s).

This is a product inequality and remains valid if a nonincident factor vanishes. Since ∣I∗∣≥ε|I^*| \ge\varepsilon, integrating in the two scalar variables bounds the bad-fiber integral by (2π/ε)e−ck(2\pi/\varepsilon)e^{-ck} times the full fiber integral. Fubini and a union bound over at most 2k(kR0)2k\binom{k}{R_0} choices of phase, core complement and index show that the mass outside the two fixed cubes is at most o(Ξε)+e−c′k∫Mo(\Xi_\varepsilon)+e^{-c'k}\int M. The combinatorial cost has logarithm Oρ(log⁡3k)O_\rho(\log^3 k).

Inside the fixed cube about zero, −log⁡M-\log M is even and has Hessian at least cδ,ρkIc_{\delta,\rho}kI: each scalar negative log modulus has second derivative at least δ(1−δ)/2\delta(1-\delta)/2 near zero, and the available-pair quadratic form satisfies the lower bound above. For the probability measure proportional to MM on this cube, each coordinate has tail at rr at most 2e−cδ,ρkr2/22e^{-c_{\delta,\rho}kr^2/2}. Indeed, factoring e−cδ,ρk∥t∥2/2e^{-c_{\delta,\rho}k\|t\|^2/2} from the density leaves a log-concave function on the cube. Prékopa’s marginal theorem then gives a coordinate density proportional to e−cδ,ρkx2/2h0(x)e^{-c_{\delta,\rho}kx^2/2}h_0(x), with h0h_0 even and log-concave (extend the cube density by zero). Thus h0h_0 decreases in ∣x∣|x|. Its covariance with 1{∣x∣≥r}1_{\{|x|\ge r\}} under the centered Gaussian law is nonpositive, which proves the tail comparison after normalization. A union bound at rkr_k gives o(1)o(1) of the fixed-cube mass outside the small cube. Translation handles the cube at π1\pi\mathbf{1}. Once the small-cube integral of MM is O(Ξε)O(\Xi_\varepsilon), absorption of e−c′k∫Me^{-c'k}\int M proves the asserted tail estimate.

The local expansion. Write U=[−rk,rk]kU=[-r_k,r_k]^k and sij=ti+tjs_{ij}=t_i+t_j. Multiply the characteristic function by the phase that centers at the mean. On UU its logarithm is

−12tTQεt+if(t)+h(t)+Oδ(k−1/2log⁡5k).-\frac{1}{2}t^TQ_\varepsilon t+if(t)+h(t)+O_\delta(k^{-1/2}\log^5 k).

where the sums below run over available pairs and

f=16∑ijwij(2qij−1)sij3,h=124∑ijwij(1−6wij)sij4.f=\frac{1}{6}\sum_{ij}w_{ij}(2q_{ij}-1)s_{ij}^3,\qquad h=\frac{1}{24}\sum_{ij}w_{ij}(1-6w_{ij})s_{ij}^4.

The error comes from summing Oδ(∣sij∣5)O_\delta(|s_{ij}|^5) per edge. Let T∼N(0,Qε−1)T\sim N(0,Q_\varepsilon^{-1}) and ν=Eh(T)\nu=\mathbb{E}h(T). Its edge-coordinate variances are O(k−1)O(k^{-1}), giving ∥h(T)∥L2=O(1)\|h(T)\|_{L2}=O(1) and Pr⁡(T∉U)≤2ke−clog⁡2k\Pr(T\notin U)\le2ke^{-c\log^2 k}. On UU, ∣h∣≤Clog⁡4k|h|\le C\log^4 k and ∥∇h∥2=O(log⁡3k)\|\nabla h\|_2=O(\log^3 k). In standard Gaussian coordinates hh therefore has Lipschitz constant K=O(k−1/2log⁡3k)K=O(k^{-1/2}\log^3 k). Extend it with the same Lipschitz constant and clip to [−Clog⁡4k,Clog⁡4k][-C\log^4 k,C\log^4 k]. The extension HH has EH=ν+o(1)\mathbb{E}H=\nu+o(1) by the Gaussian tail bound. Gaussian concentration gives Ees(H−EH)≤es2K2/2\mathbb{E}e^{s(H-\mathbb{E}H)}\le e^{s^2K^2/2} for s=1,2s=1,2. Together with Jensen’s lower bound this gives EesH=esν+o(1)\mathbb{E}e^{sH}=e^{s\nu}+o(1) for s=1,2s=1,2, since ∣ν∣=O(1)|\nu|=O(1). Expanding the square gives E(eH−eν)2=o(1)\mathbb{E}(e^H-e^\nu)^2=o(1). The extension agrees with hh on UU in Gaussian coordinates, and Pr⁡(T∉U)=o(1)\Pr(T\notin U)=o(1), so eh(T)1U(T)=eν+oL1(1)e^{h(T)}1_U(T)=e^\nu+o_{L_1}(1). Integrating the modulus on UU gives Ξε(eν+o(1))\Xi_\varepsilon(e^\nu+o(1)), which proves the residual atom bound by inversion and the preceding tail estimate.

The centered atom. For the full array, write T=Q−1/2ZT=Q^{-1/2}Z with ZZ standard Gaussian. For e={i,j}e=\{i,j\}, write qe=qijq_e=q_{ij}, ve=Q−1/2uev_e=Q^{-1/2}u_e, Ye=⟨ve,Z⟩Y_e=\langle v_e,Z\rangle and ae=we(2qe−1)/6a_e=w_e(2q_e-1)/6. Put F=f(T)=∑eaeYe3F=f(T)=\sum_ea_eY_e^3 and μ=EF2\mu=\mathbb{E}F^2. We show directly that EeiF=e−μ/2+Oδ(k−1/2)\mathbb{E}e^{iF}=e^{-\mu/2}+O_\delta(k^{-1/2}). The proof uses the Gaussian Poincaré inequality twice, in the spirit of [3]. All derivatives below are with respect to ZZ.

The identity ∑eweveveT=I\sum_e w_ev_ev_e^T=I and the variance floor give ∑eveveT⪯CI\sum_e v_ev_e^T\preceq CI. In particular ∥∑eteve∥2≤C∑ete2\|\sum_e t_ev_e\|^2\le C\sum_e t_e^2 for all scalar coefficients tet_e, by duality. Also ∥ve∥2≤C/k\|v_e\|^2\le C/k by (A.1).

Since ∇F=3∑eaeYe2ve\nabla F = 3\sum_e a_eY_e^2v_e, the Gaussian fourth moment gives E∥∇F∥2≤C∑eEYe4=O(1)\mathbb{E}\|\nabla F\|^2 \le C\sum_e\mathbb{E}Y_e^4 = O(1). Thus μ=O(1)\mu= O(1) by Gaussian Poincaré and oddness. Let ℓ=E∇F\ell= \mathbb{E}\nabla F, so ∥ℓ∥=O(1)\|\ell\| = O(1). For the Gaussian generator L=Δ−z⋅∇\mathcal{L} = \Delta- z\cdot\nabla put u(z)=(F(z)+2⟨ℓ,z⟩)/3u(z) = (F(z) + 2\langle\ell,z\rangle)/3. Since FF is homogeneous cubic and ΔF(z)=2⟨ℓ,z⟩\Delta F(z) = 2\langle\ell,z\rangle, one has −Lu=F-\mathcal{L}u = F. Gaussian integration by parts now gives

E[Fg(F)]=E[g′(F)Γ],Γ=13(∥∇F∥2+2⟨ℓ,∇F⟩),EΓ=μ.\mathbb{E}[Fg(F)] = \mathbb{E}[g'(F)\Gamma], \qquad\Gamma= \frac{1}{3}(\|\nabla F\|^2 + 2\langle\ell,\nabla F\rangle), \qquad\mathbb{E}\Gamma= \mu.

The last equality follows by taking g(x)=xg(x) = x. To bound the variance, put be=⟨ve,∇F+ℓ⟩b_e = \langle v_e,\nabla F+\ell\rangle. Differentiating Γ\Gamma and using ∇2F=6∑eaeYeveveT\nabla^2F = 6\sum_e a_eY_ev_ev_e^{T} gives

∥∇Γ∥2=16∥∑eaeYebeve∥2≤C∑eYe2be2.\|\nabla\Gamma\|^2 = 16\left\|\sum_e a_eY_eb_ev_e\right\|^2 \le C\sum_eY_e^2b_e^2.

Each beb_e is a polynomial of degree at most two. For any such polynomial qq and any Gaussian coordinate Y=⟨v,Z⟩Y = \langle v,Z\rangle, E[Y2q2]≤6∥v∥2Eq2\mathbb{E}[Y^2q^2] \le6\|v\|^2\mathbb{E}q^2, regardless of their dependence. To see this for v≠0v\ne0, rotate Y/∥v∥Y/\|v\| to a standard coordinate xx and condition on the others. Write q=A(x2−1)+Bx+Dq = A(x^2-1)+Bx+D. Then Exq2=2A2+B2+D2\mathbb{E}_xq^2 = 2A^2+B^2+D^2, whereas Exx2q2=10A2+3B2+D2+4AD≤6Exq2\mathbb{E}_xx^2q^2 = 10A^2+3B^2+D^2+4AD \le6\mathbb{E}_xq^2. Another application of Poincaré, followed by ∑eveveT⪯CI\sum_ev_ev_e^{T}\preceq CI, gives

Var⁡Γ≤E∥∇Γ∥2≤(C/k)∑eEbe2≤(C′/k)E∥∇F+ℓ∥2=O(k−1).\operatorname{Var}\Gamma\le\mathbb{E}\|\nabla\Gamma\|^2 \le(C/k)\sum_e\mathbb{E}b_e^2 \le(C'/k)\mathbb{E}\|\nabla F+\ell\|^2 = O(k^{-1}).

Finally ϕ(s)=EeisF\phi(s) = \mathbb{E}e^{isF} satisfies ϕ′(s)+μsϕ(s)=−sE[(Γ−μ)eisF]\phi'(s) + \mu s\phi(s) = -s\mathbb{E}[(\Gamma-\mu)e^{isF}]. Integration on [0,1][0,1] gives ∣ϕ(1)−e−μ/2∣≤12Var⁡Γ|\phi(1)-e^{-\mu/2}| \le\frac{1}{2}\sqrt{\operatorname{Var}\Gamma}. This estimate is uniform even when μ\mu approaches zero.

Combining the cubic and quartic estimates gives the centered integral on UU as ΞE(e−μ/2+ν+o(1))\Xi\mathbb{E}(e^{-\mu/2+\nu}+o(1)). For an integral mean bb of even total, the phase factor at π1\pi\mathbf{1} is e−iπ∑bi=1e^{-i\pi\sum b_i}=1. The two peaks therefore add. The full centered probability is

2(2π)k/2det⁡Q(e−μ/2+ν+o(1)).\frac{2}{(2\pi)^{k/2}\sqrt{\det Q}}\left(e^{-\mu/2+\nu}+o(1)\right).

The leading correction is bounded away from zero uniformly since μ+∣ν∣=Oδ(1)\mu+|\nu|=O_\delta(1). The upper spectral bound in (A.1) now gives the elementary exponential lower bound in Lemma 2.1.

AI assistance. OpenAI’s Codex assisted with revising the manuscript and reviewing its proofs, including the Fourier and overlap arguments. Codex also assisted in developing the accompanying Lean formalization. A human contributor has checked and understood most of the results stated in the abstract.

References

  1. [1]N. Alon, M. Krivelevich and B. Sudakov, Large nearly regular induced subgraphs, SIAM Journal on Discrete Mathematics 22 (2008), 1325–1337. doi:10.1137/070704927.DOI
  2. [2]A. Barvinok and J. A. Hartigan, The number of graphs and a random graph with a given degree sequence, Random Structures & Algorithms 42 (2013), 301–348. doi:10.1002/rsa.20409. Preprint: arXiv:1003.0356v3.DOI
  3. [3]S. Chatterjee, Fluctuations of eigenvalues and second order Poincaré inequalities, Probability Theory and Related Fields 143 (2009), 1–40. doi:10.1007/s00440-007-0118-6.
  4. [4]P. W. Dyson and B. D. McKay, Ramsey numbers for regular induced subgraphs, preprint (2026), arXiv:2604.08215v3.arxiv.org/abs/2604.08215
  5. [5]M. Isaev and B. D. McKay, Complex martingales and asymptotic enumeration, Random Structures & Algorithms 52 (2018), 617–661. doi:10.1002/rsa.20754.DOI
  6. [6]M. Krivelevich, B. Sudakov and N. Wormald, Regular induced subgraphs of a random graph, Random Structures & Algorithms 38 (2011), 235–250. doi:10.1002/rsa.20324.DOI
  7. [7]A. E. Levy, The lower-bound problem for regular induced subgraphs of type-based random graphs, preprint (2026), arXiv:2608.08169v2.arxiv.org/abs/2608.08169
  8. [8]A. F. Ramos, D. B. Hulak and R. J. G. B. de Queiroz, Pair-trace absorption certificates for regular induced subgraphs, preprint (2026), arXiv:2604.23882v1.arxiv.org/abs/2604.23882
  9. [9]A. F. Ramos, D. B. Hulak and R. J. G. B. de Queiroz, Regular induced subgraphs in bounded independent-edge arrays, Palomar Registry, 19 November 2026, version 1. Registry entry; Lean source at commit 251dd555; coverage map.

Paper details

vlnc:W_6eunpkmz
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI Codex

View statement
Looking for related papers…
Contents