\documentclass[11pt,a4paper]{article} \usepackage[T1]{fontenc} \usepackage{lmodern} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage[a4paper,margin=27mm,headheight=14pt]{geometry} \usepackage{microtype} \usepackage{xcolor} \usepackage{hyperref} \hypersetup{colorlinks=true,linkcolor=blue!45!black,citecolor=blue!45!black, urlcolor=blue!45!black,pdftitle={Regular induced subgraphs in bounded independent-edge arrays}, pdfauthor={Arthur Freitas Ramos; David Barros Hulak; Ruy J. G. B. de Queiroz}, pdfsubject={Regular induced subgraphs under independent inhomogeneous edge sampling}} \usepackage{bookmark} \usepackage{fancyhdr} \pagestyle{fancy} \fancyhf{} \fancyhead[L]{\small Regular induced subgraphs in bounded arrays} \fancyhead[R]{\small Ramos, Hulak and de Queiroz} \fancyfoot[C]{\thepage} \renewcommand{\headrulewidth}{0.3pt} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \numberwithin{equation}{section} \allowdisplaybreaks[1] \setlength{\emergencystretch}{2em} \title{\LARGE\bfseries Regular induced subgraphs in bounded independent-edge arrays} \author{Arthur Freitas Ramos\thanks{Microsoft, USA. Corresponding author: \texttt{arfreita@microsoft.com}.} \qquad David Barros Hulak\thanks{Independent researcher.} \qquad Ruy J. G. B. de Queiroz\thanks{Centro de Inform\'atica, Universidade Federal de Pernambuco, Brazil.}} \date{19 November 2026} \begin{document} \maketitle \thispagestyle{plain} \begin{abstract} Let $G$ be a random graph whose edges are independent and whose edge probabilities lie in $[\xi,1-\xi]$ for a fixed $0<\xi<1/2$. With probability at least $1-n^{-1}$, $G$ contains a regular induced subgraph on at least $c_\xi(\log n)^2$ vertices. If all expected degrees are equal, each prescribed order $k$ up to a small multiple of $n^{2/3}$ occurs with failure probability at most $\exp(-cn/k^{3/2})$, for $k$ sufficiently large. The same probability estimate holds up to order $n^{2/(d+3)}$ for a Lipschitz kernel in dimension $d$, and up to order $n^{4/(r+7)}$ for an array admitting a bounded symmetric completion of rank at most $r$. A linear product array has largest regular induced order $\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. \end{abstract} \noindent\textbf{Keywords.} Random graphs, induced subgraphs, regular graphs, inhomogeneous edge probabilities. \noindent\textbf{2020 Mathematics Subject Classification.} 05C80, 05C07, 60F05. \section{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)$, Krivelevich, Sudakov and Wormald give a high-probability upper bound of $2n^{2/3}$ and find regular induced sets at subcritical orders. In particular $R=n^{2/3+o(1)}$ with high probability~\cite[Theorem~1.1]{KSW}. 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(\mathbf p)$ for the simple graph on $[n]$ in which distinct unordered pairs are present independently, with probabilities $p_{ij}=p_{ji}$. Throughout, $0<\xi<1/2$ is fixed and $\xi\le p_{ij}\le 1-\xi$ for $i\ne j$. Write $A_k$ for the event that some set of exactly $k$ vertices induces a regular graph, and put $R=\max\{k:A_k\text{ occurs}\}$. Thus $\{R\ge k\}=\bigcup_{\ell\ge k}A_\ell$. When a domain $U$ is specified, $A_k$ and $R$ refer to the induced array on $U$. The common degree may depend on the set. All logarithms are natural. \newpage \begin{theorem}\label{thm:main} The following bounds hold uniformly in the indicated arrays for all sufficiently large $n$. \begin{enumerate} \item There are $00$ and $k_0$ such that, for every integer $k_0\le k\le a n^\beta$, \begin{equation}\label{eq:exact} \Pr(A_k^c)\le \exp(-c n/k^{3/2}). \end{equation} \begin{center} \begin{tabular}{@{}lc@{}}\hline Hypothesis on the array & $\beta$\\ \hline All expected degrees $\sum_{j\ne i}p_{ij}$ are equal & $2/3$\\ Symmetric $L$-Lipschitz kernel on $[0,1]^d$ & $2/(d+3)$\\ Bounded symmetric matrix completion of rank at most $r$ & $4/(r+7)$\\ \hline \end{tabular} \end{center} In the kernel case $p_{ij}=W(x_i,x_j)$ for arbitrary deterministic types, $W$ takes values in $[\xi,1-\xi]$, and $|W(x,y)-W(x',y)|\le L\|x-x'\|_\infty$. A completion is a matrix $P\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)$ or $r$, with $d,r\ge1$. \end{enumerate} \end{theorem} For equal expected degrees, \eqref{eq:exact} gives high probability for $k_0\le k=o(n^{2/3})$. At $k=\lfloor a n^{2/3}\rfloor$ it gives a success probability bounded away from zero uniformly in $n$. For the other two classes, $n/k^{3/2}$ grows as a positive power of $n$ even at the indicated endpoint. In particular every bounded one-dimensional Lipschitz model has a regular induced subgraph of order at least $c\sqrt n$ with high probability. Section~\ref{sec:product} gives an example attaining this scale. \paragraph{Relation to earlier work.} Erd\H{o}s, Fajtlowicz and Staton asked whether the largest regular induced subgraph of every $n$-vertex graph has order $\omega(\log n)$~\cite{AKS,KSW}. A complementary deterministic approach studies modular witnesses and finite absorption certificates~\cite{RamosAbsorption}. 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~\cite{DM}. Levy studies a one-dimensional Lipschitz kernel with independent uniform types and obtains a conditional $n^{1/2-\varepsilon}$ lower bound under local degree and overlap hypotheses~\cite{Levy}. Our one-dimensional bound holds uniformly for every assignment of the types. Conditioning on the types therefore gives a $c\sqrt n$ lower bound with high probability for Levy's model, with $c$ depending on the probability floor and the kernel's Lipschitz constant. Levy also conjectures the sharp family-wide constant $\sqrt{2e}$. The constant in our order bound depends on the model parameters. \paragraph{Where the scales come from.} In a domain of $N$ vertices with normalized expected degrees within $O(k^{-1/2})$ of one another, many $k$-sets can be tilted to the same integer target degree. Two independent uniform $k$-sets share $k^2/N$ vertices in expectation. If they share $j$ vertices, averaging the tilt over the shared vertices gives a factor of order $\exp(O(j^2/k))$ in the small-overlap range. Thus $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\asymp 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 $k$. \paragraph{Formalization.} The Palomar Registry entry \href{https://palomar-registry.org/entry?id=PALOMAR-2026-11-19-000016&version=1}{\texttt{PALOMAR-2026-11-19-000016} (version 1)} records the two logarithmic bounds together and each of the three exact-order bounds separately~\cite{Palomar}. 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. \section{The local cost of prescribing degrees}\label{sec:degree} For independent Bernoulli edges on $[k]$ with probabilities $q_{ij}$, let $D$ be the degree vector, $w_{ij}=q_{ij}(1-q_{ij})$, and $u_{ij}=e_i+e_j$. A present edge adds $u_{ij}$ to $D$, so its covariance matrix is \[ Q=\sum_{i0$, $a_\xi\in(0,1/2)$, $C_\xi<\infty$, and $k_0(\xi)$ such that the following holds. Let $k\geq k_0(\xi)$, let $q_{ij}\in[\xi,1-\xi]$, and let $\mathbf d=(d_1,\ldots,d_k)\in\mathbb Z^k$ have even total sum. Put \[ r_i=\sum_{j\ne i}q_{ij}-d_i, \qquad \|r\|_\infty\leq\varepsilon_\xi k. \] There is a vector $\theta\in\mathbb R^k$ for which \[ q_{ij}(\theta) =\frac{q_{ij}e^{\theta_i+\theta_j}} {1-q_{ij}+q_{ij}e^{\theta_i+\theta_j}} \] satisfies \begin{align*} &\sum_{j\ne i}q_{ij}(\theta)=d_i\quad(i\in[k]), \qquad q_{ij}(\theta)\in[a_\xi,1-a_\xi],\\ &\|\theta\|_\infty\leq C_\xi\|r\|_\infty/k, \qquad \|\theta\|_2\leq C_\xi\|r\|_2/k. \end{align*} If $\mathbb P_0$ and $\mathbb P_\theta$ are the original and tilted product measures, respectively, their relative entropy obeys \[ K:=D(\mathbb P_\theta\Vert\mathbb P_0) \leq C_\xi\|r\|_2^2/k. \] On every graph configuration with degree vector $\mathbf d$, the likelihood ratio $\mathbb P_\theta/\mathbb P_0$ is the constant $e^K$. Consequently \begin{equation}\label{eq:deterministic-tilt-probability} \mathbb P_0(D=\mathbf d) \geq\exp\left\{-\frac12k\log k-C_\xi k -C_\xi\frac{\|r\|_2^2}{k}\right\}. \end{equation} \end{lemma} \begin{proof} Define \[ F_i(\theta)=\sum_{j\ne i}q_{ij}(\theta)-d_i, \qquad \Psi(\theta)=\sum_{i0 \] as a lower bound both for $q_{ij}(\theta)$ and for $1-q_{ij}(\theta)$. Set $\lambda_\xi=a_\xi(1-a_\xi)$. Throughout that cube, \begin{equation}\label{eq:vertex-tilt-hessian} \lambda_\xi(k-2)I\preceq H(\theta) \preceq\tfrac12(k-1)I, \qquad \|H(\theta)^{-1}\|_{\infty\to\infty}\leq A_\xi/k. \end{equation} We first construct the tilt. Since $F(0)=r$, Taylor expansion gives \[ 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\leq1$, each row has $k-1$ summands, each depending on a sum of two coordinates. The one-variable mean value formula therefore gives \[ \|R(\theta)\|_\infty\leq Ckb^2, \qquad \|R(\theta)-R(\phi)\|_\infty \leq Ckb\|\theta-\phi\|_\infty. \] If $r=0$ take $\theta=0$. Otherwise put $b=2A_\xi\|r\|_\infty/k$ and $T(\theta)=-H(0)^{-1}(r+R(\theta))$. Choose $\varepsilon_\xi$ so that $b\le1$ and $CA_\xi b\le1/2$. On the closed cube of radius $b$, the preceding estimates give $\|T(\theta)\|_\infty\le b/2+CA_\xi b^2\le b$ and $\operatorname{Lip}(T)\le1/2$. The contraction theorem gives a fixed point in that cube. It solves $F(\theta)=0$, satisfies the stated maximum-norm bound, and preserves the floor $a_\xi$. For the Euclidean bound, integrate the Hessian along the segment from zero to the fixed point. Since $\nabla\Psi(\theta)-\nabla\Psi(0)=-r$, \[ -r\cdot\theta =\int_0^1\theta^TH(t\theta)\theta\,dt \geq\lambda_\xi(k-2)\|\theta\|_2^2. \] Cauchy--Schwarz yields $\|\theta\|_2\leq\|r\|_2/[\lambda_\xi(k-2)]$. For any graph configuration $A$, let $D(A)$ be its degree vector. The exact product-measure likelihood ratio is \[ \frac{\mathbb P_\theta(A)}{\mathbb P_0(A)} =\exp\{\theta\cdot D(A)-\Psi(\theta)\}. \] Taking its logarithmic expectation under $\mathbb P_\theta$, and using $\nabla\Psi(\theta)=\mathbf d$ and $\Psi(0)=0$, gives \begin{align*} K&=\theta\cdot\nabla\Psi(\theta)-\Psi(\theta)\\ &=\int_0^1t\,\theta^TH(t\theta)\theta\,dt \leq\frac{k-1}{4}\|\theta\|_2^2 \leq C_\xi\|r\|_2^2/k. \end{align*} On $D(A)=\mathbf d$, the logarithmic likelihood ratio equals this same $K$. Hence $\mathbb P_0(D=\mathbf d)=e^{-K}\mathbb P_\theta(D=\mathbf d)$. Under $\mathbb P_\theta$, the target degrees are exactly the means, they are integral with even total, and every edge probability lies in $[a_\xi,1-a_\xi]$. Applying the centered degree estimate, Lemma~\ref{lem:centered}, with floor $a_\xi$, and enlarging $k_0(\xi)$ and $C_\xi$ if needed, proves \eqref{eq:deterministic-tilt-probability}. \end{proof} \subsection{Sampling distinct vertices} \begin{lemma}[Concentration for sampling without replacement] \label{lem:without-replacement} Let $a_1,\ldots,a_M\in[0,1]$, let $\bar a=M^{-1}\sum_i a_i$, and let $Y$ be the sum of a uniformly chosen $m$-element subset of these numbers, where $1\leq m\leq M$. Then \[ \mathbb E e^{t(Y-m\bar a)}\leq e^{mt^2/8} \qquad(t\in\mathbb R), \] and for every $s\ge0$, \[ \mathbb P(|Y-m\bar a|\geq s)\leq2e^{-2s^2/m}. \] Also $\operatorname{Var}Y\leq m/4$. \end{lemma} \begin{proof} For nonnegative $z_1,\ldots,z_M$, their elementary symmetric polynomial satisfies \begin{equation}\label{eq:symmetric-mean} \frac{e_m(z_1,\ldots,z_M)}{\binom Mm} \leq\left(\frac1M\sum_i z_i\right)^m. \end{equation} For $m\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 $e_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 \eqref{eq:symmetric-mean} by continuity. For $m=1$ there is equality. Take $z_i=e^{ta_i}$. The left side of \eqref{eq:symmetric-mean} is $\mathbb E e^{tY}$. For a single uniform draw $X$, the log moment generating function of $X-\bar a$ has value and derivative zero at zero. Its second derivative is the variance under an exponential tilt, at most $1/4$ since $0\le X\le1$. Hence \[ \mathbb E e^{t(Y-m\bar a)} \le(\mathbb E e^{t(X-\bar a)})^m\le e^{mt^2/8}. \] Exponential Markov at $t=\pm 4s/m$ gives the two tails. Comparing the second derivatives at zero gives $\operatorname{Var}Y\le m/4$, since both sides of the centered moment bound have value one and derivative zero there. \end{proof} \subsection{A common target degree} \begin{lemma}[Candidate family from mean-squared drift] \label{lem:mean-square-good-family} Fix $\xi\in(0,1/2)$. Let $(q_{xy})_{x\ne y}$ be a symmetric array on $[N]$ with entries in $[\xi,1-\xi]$, and let $p\in[\xi,1-\xi]$. Write \[ a_x=\frac1{N-1}\sum_{y\ne x}q_{xy}-p. \] Suppose that \[ \max_x|a_x|\leq\alpha, \qquad \frac1N\sum_xa_x^2\leq\eta^2. \] Uniformly along sequences with $k\to\infty$, $\alpha\to0$, and $k\leq N$, there is a legal degree $d$, with $kd$ even and $|d-p(k-1)|\leq2$, and a family $\mathcal F\subseteq\binom{[N]}k$ of size at least $\tfrac12\binom Nk$, such that every $S\in\mathcal F$ has a vertex tilt $\theta^S$ satisfying \begin{align*} &\mathbb E_{\theta^S}\deg_{G[S]}(v)=d\quad(v\in S), \qquad q_{uv}(\theta^S)\in[a_\xi,1-a_\xi],\\ &\|\theta^S\|_\infty \leq C_\xi\left(\alpha+\sqrt{\frac{\log k}{k}}\right), \qquad \|\theta^S\|_2^2\leq C_\xi(1+\eta^2k),\\ &p_S:=\mathbb P(G[S]\text{ is }d\text{-regular}) \geq p_*:=\exp\{-\tfrac12k\log k-C_\xi(k+\eta^2k^2)\}. \end{align*} Here $a_\xi>0$ and $C_\xi$ depend only on $\xi$. There is no restriction on $k^2/N$ in this lemma. \end{lemma} \begin{proof} Choose $d$ before selecting the vertices. If $k$ is even, choose a nearest integer to $p(k-1)$; if $k$ is odd, choose a nearest even integer. For large $k$, uniformly for $p\in[\xi,1-\xi]$, this is a legal degree $0\leq d\leq k-1$ with the stated parity and error. Set $b=p(k-1)-d$, so $|b|\leq2$. Choose a uniform ordered tuple $(X_1,\ldots,X_k)$ of distinct labels in $[N]$, and put \[ r_i=\sum_{j\ne i}q_{X_iX_j}-d. \] Conditional on $X_i=x$, the remaining labels form a uniform $(k-1)$-subset of $[N]\setminus\{x\}$. Consequently \[ \mathbb E(r_i\mid X_i=x)=(k-1)a_x+b, \qquad \operatorname{Var}(r_i\mid X_i=x)\leq(k-1)/4, \] where the variance assertion follows from Lemma~\ref{lem:without-replacement}. The same lemma, with $t=\sqrt{2k\log k}$, and a union bound give \begin{equation}\label{eq:mean-square-maxdrift} \|r\|_\infty \leq\alpha(k-1)+2+\sqrt{2k\log k} \end{equation} with probability at least $1-2k^{-3}$. There is no independence assertion between different row sums. Their squared norm is instead controlled directly by conditional second moments: \begin{align*} \mathbb E\|r\|_2^2 &\leq k\left\{\frac{k-1}{4} +2(k-1)^2\frac1N\sum_xa_x^2+8\right\}\\ &\leq C(k^2+\eta^2k^3). \end{align*} Markov's inequality therefore gives \begin{equation}\label{eq:mean-square-totaldrift} \|r\|_2^2\leq4C(k^2+\eta^2k^3) \end{equation} with probability at least $3/4$. The two displayed drift bounds hold together with probability at least $1/2$ for all sufficiently large $k$. On their intersection $\|r\|_\infty/k=o(1)$ uniformly. The tilt in Lemma~\ref{lem:vertex-tilt} therefore exists, with the fixed floor $a_\xi$. Its maximum norm is at most $C_\xi\|r\|_\infty/k$, its squared energy at most $C_\xi\|r\|_2^2/k^2$, and its negative log probability cost beyond the centered atom at most $C_\xi\|r\|_2^2/k$. Substitution of \eqref{eq:mean-square-maxdrift} and \eqref{eq:mean-square-totaldrift} gives all three asserted estimates. Both drift tests are invariant under reorderings, and every $k$-set has $k!$ orderings, so at least half of the unordered sets qualify. \end{proof} \section{Shared edges and a weighted count}\label{sec:overlap} Let $E_S$ be the event that a candidate $S$ induces a $d$-regular graph, where the degree $d$ and the family $\mathcal F$ come from Lemma~\ref{lem:mean-square-good-family}. Weight a success on $S$ by $1/p_S$, where $p_S=\Pr(E_S)$. Then \[ Z=\sum_{S\in\mathcal F}\frac{\mathbf1_{E_S}}{p_S}, \qquad \mathbb EZ=|\mathcal F|. \] This weighting allows different candidates to have very different probabilities. Write $H_{ST}=\Pr(E_S\cap E_T)/(p_Sp_T)$ for the normalized joint probability. \begin{lemma}[Shared-edge likelihood]\label{lem:sharp-overlap} Let $J=S\cap T$, $j=|J|$, and $X_S(J)=\sum_{v\in J}(\theta_v^S)^2$. For $j\le3k/4$ the normalized joint probability satisfies \begin{equation}\label{eq:ratio} \frac{\Pr(E_S\cap E_T)}{p_Sp_T} \le K\exp\{D j^2/k+(j/4)[X_S(J)+X_T(J)]\}, \end{equation} where $K,D$ depend only on $\xi$. For $j=0,1$ the ratio is one. \end{lemma} \begin{proof} Write $H$ for the shared-edge configuration and $L_S(H)$ for its tilted likelihood relative to its original law. Constancy of the full likelihood on $E_S$ gives \[ \frac{\Pr(E_S\mid H)}{p_S} =L_S(H)\frac{\Pr_{\theta^S}(E_S\mid H)}{\Pr_{\theta^S}(E_S)}. \] The last ratio is bounded by Corollary~\ref{lem:conditional-degree-ratio}. Conditional on $H$, the two events depend on disjoint sets of remaining edges. Their normalized joint probability is therefore at most $Ke^{Dj^2/k}\mathbb E[L_S(H)L_T(H)]$. For one shared edge with logit increments $s,t$, put $\psi(u)=\log(1-q+qe^u)$. Its contribution to the logarithm of the expectation is \[ \psi(s+t)-\psi(s)-\psi(t) =\int_0^s\int_0^t\psi''(u+v)\,dv\,du \le (s^2+t^2)/8 \] since $0\le\psi''\le1/4$. Sum over edges and use $\sum_{a0$ such that, uniformly when $k\to\infty$, $\alpha\to0$, $k^2/N\to0$ and $\eta^2k\le c_\xi^*\log(N/k^2)$, \[ \Pr(A_k^c)\le C_\xi(k^2/N)^{3/2}+C_\xi e^{-k\log k/8}. \] When $\eta=0$ the first term can be replaced by $C_\xi k^4/N^2$. \end{theorem} \begin{proof} Write $H_{ST}=\Pr(E_S\cap E_T)/(p_Sp_T)$. For $j=0,1$, $H_{ST}-1=0$. If $U_j$ bounds $H_{ST}$ for all candidate pairs of overlap $j\ge2$, then \[ \frac{\operatorname{Var} Z}{(\mathbb EZ)^2} =\frac{1}{|\mathcal F|^2}\sum_{S,T\in\mathcal F}(H_{ST}-1) \le \frac{\binom Nk^2}{|\mathcal F|^2}\sum_{j=2}^k P_j U_j \le 4\sum_{j=2}^k P_j U_j . \] Indeed, exactly $\binom Nk^2 P_j$ ordered pairs of unrestricted $k$-sets have intersection size $j$. Write $H_0=\log(N/k^2)$. For $2\le j\le3k/4$, \eqref{eq:ratio} and the total tilt energy give a ratio at most $K\exp(D_0j+D_1\eta^2kj)$. By \eqref{eq:hyper} their contribution to $\operatorname{Var}Z/(\mathbb EZ)^2$ is at most $4K\sum_{j\ge2}u^j$, where $u=\exp(-H_0+D_0+D_1\eta^2k)$. Choose $D_1c_\xi^*\le1/4$. This sum is $O(e^{-3H_0/2})$, or $O(e^{-2H_0})$ when $\eta=0$. For $j>3k/4$, use $\Pr(E_S\cap E_T)/(p_Sp_T)\le1/\max(p_S,p_T)\le e^{B}$ with $B=\frac12 k\log k+C_0(k+\eta^2k^2)$. Now \eqref{eq:hyper} gives $P_j\le g^j$ with $g=4ek/(3N)$. Since $\log(N/k)=\log k+H_0$, \[ B+(3k/4)\log g \le k\{-\tfrac14\log k-\tfrac34H_0+C_0\eta^2k+O_\xi(1)\} \le-\tfrac18k\log k \] after taking $C_0c_\xi^*\le1/4$. Sum the geometric tail, including $j=k$, and apply $\Pr(Z=0)\le\operatorname{Var}Z/(\mathbb EZ)^2$. \end{proof} \begin{theorem}[A balanced block]\label{thm:block} Let the independent edges on $[N]$ have probabilities in $[\xi,1-\xi]$ and define $a_i=(N-1)^{-1}\sum_{j\ne i}q_{ij}-p$ for $p\in[\xi,1-\xi]$. Fix $M\ge0$. There are $L_0,p_0>0$ depending only on $M,\xi$ such that, for all sufficiently large $k$, if $N\ge L_0k^{3/2}$ and $\max_i|a_i|\le\sqrt{M/k}$, then $\Pr(A_k)\ge p_0$. The successful candidates may all be tested at the same degree $d$. \end{theorem} \begin{proof} Apply Lemma~\ref{lem:mean-square-good-family} with $\alpha=\eta=\sqrt{M/k}$. It gives one $d$ and a family occupying at least half of all $k$-sets. For constants $A\ge1$ and $C$ depending only on $M,\xi$, every candidate satisfies \[ \|\theta^S\|_2^2\le A,\qquad \|\theta^S\|_\infty^2\le A\log k/k, \qquad p_S^{-1}\le \exp(\tfrac12 k\log k+Ck). \] We bound $\mathbb EZ^2/(\mathbb EZ)^2$ in three overlap ranges. \emph{Small overlaps.} For $j\le t=\lfloor k/(A\log k)\rfloor$, symmetry in $(S,T)$ and the arithmetic--geometric mean inequality bound the sum of $\exp((j/4)(X_S+X_T))$ over candidate pairs of overlap $j$ by the corresponding sum of $\exp(j X_S/2)$. More explicitly, $2e^{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,T$. Keep $S\in\mathcal F$ fixed and extend the other sum to all $T$. Each $j$-subset $J\subseteq S$ now occurs $\binom{N-k}{k-j}$ times. Thus, for any nonnegative $g_S$ and any $j$ with $P_j>0$, \[ \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 Nk}{|\mathcal F|}\,P_j\, \frac1{|\mathcal F|}\sum_{S\in\mathcal F}\mathbb E_J g_S(J), \] where $J$ on the right is uniform among the $j$-subsets of $S$. The factor in front of $P_j$ is at most two. Assign a zero contribution when $P_j=0$. The elementary symmetric mean bound \eqref{eq:symmetric-mean} and $e^u\le1+2u$ on $[0,1]$ give \[ \mathbb E_J e^{j X_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\sum_{j\le t}P_j e^{(D+A)j^2/k}$. Put $\mu=k^2/N$ and $s=\lceil\max(e^2\mu,\log k)\rceil$. The terms through $\min(s,t)$ sum to at most $\exp((D+A)s^2/k)\sum_j P_j=O(1)$, since $N\ge L_0k^{3/2}$ gives $s=O(\sqrt{k}+\log k)$. For $st}(C_1\mu/j)^j=o(1)$ since $\mu/t=O((\log k)/\sqrt k)$. \emph{Large overlaps.} For $j>3k/4$ put $m=k-j$. Condition on all edges of $S$. Each vertex of $J$ needs a specified number of edges to $T\setminus S$ to reach $d$ in $T$. Those $j$ sums involve disjoint sets of fresh edges, so they are conditionally independent. For a sum $Y$ of $m$ independent Bernoulli variables of floor $\delta$, one-dimensional inversion gives \begin{equation}\label{eq:one-row} \sup_{\ell\in\mathbb Z}\Pr(Y=\ell) \le\frac1{2\pi}\int_{-\pi}^{\pi}e^{-2m\delta(1-\delta)\sin^2(t/2)}\,dt \le \frac{C_\delta}{\sqrt{m+1}} . \end{equation} Use $\sin(|t|/2)\ge |t|/\pi$ and take $C_\delta\ge1$ for $m=0$. If $\mathcal G_S$ denotes the exposed edges, $E_S$ is $\mathcal G_S$-measurable and $\Pr(E_T\mid\mathcal G_S)\le(C_\xi/\sqrt{m+1})^j$. Multiplying by $\mathbf1_{E_S}$ and taking expectations gives $H_{ST}\le p_T^{-1}(C_\xi/\sqrt{m+1})^j$, including $S=T$. Multiply by $P_j\le(4ek/(3N))^j$. The logarithm of the product is at most \[ \tfrac12\{m\log k-j\log(m+1)\}+C_2k-j\log L_0. \] For $0\le m\le k/4$, concavity gives $\log(m+1)\ge(4m/k)\log(1+k/4)$. As $4j/k\ge1$, the braces are at most $m\log[k/(1+k/4)]\le k\log4$. The constant $C_2$ depends only on $M,\xi$. Choose $\tfrac34\log L_0\ge C_2+1+\tfrac12\log4$. After accounting for the candidate fraction, the entire range contributes at most $4(k+1)e^{-k}$. This last estimate retains the information in the $m$ fresh vertices even when the two candidates nearly coincide. The normalized second moment is bounded by a constant independent of $k,N$. Cauchy--Schwarz gives $\Pr(Z>0)\ge(\mathbb EZ)^2/\mathbb EZ^2$. \end{proof} \section{Extraction with small mean-square degree variation} \label{sec:variance-extraction} For a symmetric array $q_{ij}\in[0,1]$, $i\ne j\in V$, of order $M\ge2$, write \[ 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 M2},\qquad \bar d=p(M-1). \] Its normalized degree variance is \[ v=\frac1{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. \begin{lemma}[A variance-driven density increment]\label{lem:variance-increment} Suppose $M\ge32$. If $v>16e^{-M/8}$, there is a set $S\subseteq V$ of order at least $M/4$ whose induced weighted density is greater than $p+v/2$. \end{lemma} \begin{proof} Put $a_i=(d_i-\bar d)/M$. Then \[ \sum_i a_i=0,\qquad |a_i|\le1,\qquad \sum_i a_i^2=Mv,\qquad \sum_i a_id_i=M^2v. \] Select vertices independently with probabilities $w_i=1/2+a_i/4\in[1/4,3/4]$, and call the resulting set $S$. Its expected order is $M/2$. Expansion of the edge expectation gives \[ \mathbb E e_q(S) =\frac{pM(M-1)}8+\frac18\sum_i a_id_i +\frac1{16}\sum_{i16e^{-M/8}$. The resulting set has at least two vertices since $M\ge32$. \end{proof} \begin{lemma}[Mean-square extraction]\label{lem:variance-extraction} Let $0<\eta\le1/16$, and put \[ J=\left\lceil\frac2{\eta^2}\right\rceil, \qquad M_0=\max\left\{32,\;8\log\frac{16}{\eta^2}\right\}. \] If $n\ge4^JM_0$, every symmetric array in $[0,1]$ on $n$ vertices has an induced subarray of order \[ N\ge\tfrac12\,4^{-J}n \] whose degree sums $d_i'$ and average $\bar d'$ satisfy \begin{equation}\label{eq:variance-extracted-controls} \max_i|d_i'-\bar d'|\le3\sqrt\eta\,(N-1), \qquad \frac1N\sum_i(d_i'-\bar d')^2\le6\eta^2(N-1)^2. \end{equation} In particular the logarithm of the vertex loss is $O(\eta^{-2})$. If the initial entries lie in $[\xi,1-\xi]$, then so do the extracted entries and their common density $\bar d'/(N-1)$. \end{lemma} \begin{proof} Repeatedly restrict the current array to a set supplied by Lemma~\ref{lem:variance-increment} whenever its normalized degree variance exceeds $\eta^2$. Through the first $J$ restrictions, whenever defined, the current order after $t\le J$ steps is at least $4^{-t}n\ge M_0$, so $16e^{-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 $\eta^2/2$. There are fewer than $J$ restrictions, since $J$ such increases would raise a nonnegative initial density above one. The terminal subarray therefore has order $M\ge4^{-J}n$ and \[ \sum_i(d_i-\bar d)^2\le\eta^2M^3. \] Remove the set $B$ of vertices satisfying $|d_i-\bar d|>\sqrt\eta\,M$. Its size is at most $\eta M$. Let $U=V\setminus B$, $N=|U|$, and let $d_i'$ denote the degree sums of the remaining subarray. Then $N\ge(1-\eta)M\ge15M/16$. For $i\in U$, write \[ 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\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 $\bar d'$ cannot increase the sum of squares, and it increases the preceding maximum bound by at most a factor of two. Since $M\ge32$, \[ N-1\ge\frac{15M}{16}-1\ge\frac{7M}{8}. \] Using $\eta\le\sqrt\eta/4$, we find \[ \max_i|d_i'-\bar d'| \le\frac52\sqrt\eta M \le\frac{20}{7}\sqrt\eta(N-1) <3\sqrt\eta(N-1). \] Similarly, \[ \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(\frac87\right)^2 <6\eta^2. \] These are \eqref{eq:variance-extracted-controls}. The size bound follows from $N\ge15M/16\ge M/2$. The entry and density assertions follow by restriction and averaging. \end{proof} \begin{theorem}[A universal squared-logarithmic lower bound] \label{thm:universal-log-square} For every fixed $\xi\in(0,1/2)$ there are constants $c_\xi>0$ and $n_0(\xi)$ such that, for all $n\ge n_0(\xi)$, \[ \sup_{\mathbf p\in[\xi,1-\xi]^{\binom n2}} \Pr\{R(G(\mathbf p))0$ with $192a0$ and $B\ge0$ with the following property. For each induced domain of order $u$ and each $00$ with $a+b<1$, take \[ z_i=a+b\,i/n,\qquad p_{ij}=z_i z_j,\quad 1\le i0$, depending only on $a,b$, such that \[ \Pr\{c\sqrt n\le R\le C\sqrt n\}\longrightarrow1. \] \end{theorem} Take $\xi<\min\{a^2,1-(a+b)^2,1/2\}$ and $k=\lfloor\kappa\sqrt n\rfloor$ for a sufficiently small fixed $\kappa>0$. Then \eqref{eq:exact} bounds failure by $\exp(-c_1 n^{1/4})$, and $k\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. \begin{proposition}\label{prop:penalty} For a fixed $k$-set $S$, $k\ge3$, write $\mu_i=\sum_{j\in S\setminus\{i\}}p_{ij}$, $\bar\mu=k^{-1}\sum_i\mu_i$, and $V(S)=\sum_i(\mu_i-\bar\mu)^2$. Under the fixed floor, \begin{equation}\label{eq:upper} \Pr(G[S]\text{ is regular})\le (C_\xi/\sqrt k)^k\exp[-2V(S)/(k-2)] . \end{equation} With arbitrary probabilities in $[0,1]$ the bound $\exp[-2V(S)/(k-2)]$ alone still holds. \end{proposition} \begin{proof} Put $v_i=\mu_i-\bar\mu$ and tilt by $\theta_i=-4v_i/(k-2)$. On every regular outcome $\theta\cdot D=0$. Writing $\Psi(\theta)=\sum_{ii$ at step $i$. Given the previous rows, the required number of successes in the $k-i$ fresh trials is fixed. By \eqref{eq:one-row} its conditional probability is at most $C/\sqrt{k-i+1}$, uniformly in the history. Earlier degree constraints are measurable at this point. Iterating conditional expectations gives at most $C^k/\sqrt{k!}$ for the prescribed degree vector, as in the exposure argument of~\cite[Section~3]{AKS}. Summing over the $k$ possible degrees, using $k!\ge(k/e)^k$ and $k\le2^k$, gives $(C_\xi/\sqrt k)^k$ for tilted regularity. Multiplying by the exponential penalty proves \eqref{eq:upper}. \end{proof} \begin{proof}[Upper bound in Theorem~\ref{thm:product}] For the product array $\mu_i=z_i(\sum_{\ell\in S}z_\ell-z_i)$. Therefore \[ |\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}\sum_{i,j\in S}(\mu_i-\mu_j)^2$ and choose $v\in S$ minimizing $\sum_{i\in S}(i-v)^2$. The minimum is at most its average over $v$. It follows that \[ \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=(ab)^2/3 . \] For a fixed anchor $v$, set $w_i=\exp[-\lambda k(i-v)^2/n^2]$. Comparing the decreasing Gaussian on either side of $v$ with its integral gives $\sum_i w_i\le C_{a,b}n/\sqrt k$. The sum of $\prod_{i\in S} w_i$ over the $k$-sets containing $v$ is at most $(\sum_i w_i)^{k-1}/(k-1)!$, since $w_v=1$. Sum \eqref{eq:upper} over the $n$ choices of anchor, using the bound just obtained for the sets assigned to each. With $k!\ge(k/e)^k$ this yields \[ \Pr(A_k)\le k^{3/2}(D_{a,b} n/k^2)^k . \] Choose $C$ so that $D_{a,b}/C^2<1/2$. Summing this bound over \emph{all} $k\ge C\sqrt n$ gives $o(1)$ and hence the asserted upper tail for $R$. \end{proof} \paragraph{The unrestricted problem.} Does every fixed floor $\xi$ admit a $\beta_\xi>0$ for which $\inf_{\mathbf p}\Pr(R\ge n^{\beta_\xi})\to1$? The product example forces $\beta_\xi\le1/2$ at the exponent level. The density increment in Section~\ref{sec:variance-extraction} yields a logarithmic power for general arrays. Proposition~\ref{prop:penalty} indicates what obstructs a larger witness: for instance $\Pr(A_k)\ge\gamma$ implies that some $k$-set satisfies $V(S)\le\frac{k-2}{2}\log(\binom nk/\gamma)$ by the floor-free bound. To obtain the corresponding test for $R\ge k$, one must sum over every order $\ell\ge k$, as in the proof above. \appendix \section{Fourier estimates for the degree vector}\label{sec:fourier} We give the proof of Lemma~\ref{lem:centered} in a form that treats the complete and deleted arrays together. The saddle-point calculation follows the degree-enumeration method of Barvinok and Hartigan~\cite{BH}; see also Isaev and McKay~\cite{IM}. Here the edge logits are arbitrary and the residual upper bound holds at any integral target. Let $\mathcal E$ be the available pairs after deleting the pairs in $J$ (take $J=\varnothing$ for the full array), let $Q_{\mathcal E}=\sum_{e\in\mathcal E}w_e u_eu_e^T$, and set \[ \Xi_{\mathcal E}=(2\pi)^{k/2}(\det Q_{\mathcal E})^{-1/2}, \qquad M(t)=\prod_{ab\in\mathcal E}|1-q_{ab}+q_{ab}e^{i(t_a+t_b)}|. \] Integration is with respect to Lebesgue measure on $\mathbb T^k=[-\pi,\pi)^k$. Fourier inversion contributes the separate factor $(2\pi)^{-k}$. \paragraph{The covariance.} Write $m=k-|J|\ge(1-\rho)k$. In the unweighted sum $\sum_{e\in\mathcal E}u_eu_e^T$, contrasts within $J$ and within its complement have eigenvalues $m$ and $k-2$ respectively. On the two normalized constant vectors of those sets the matrix is \[ \begin{pmatrix}m&\sqrt{|J|m}\\ \sqrt{|J|m}&k+m-2\end{pmatrix}. \] Its determinant is $2m(m-1)$ and its trace is at most $3k$. Taking the variance floor into account, or using the complete-pair identity of Lemma~\ref{lem:inverse-infinity} for $J=\varnothing$, gives \begin{equation}\label{eq:spectrum} c_{\delta,\rho}k I\preceq Q_{\mathcal E}\preceq (k-1)I/2. \end{equation} \paragraph{The two peaks.} Put $r_k=(\log k)/\sqrt k$. Only the cubes of radius $r_k$ around $0$ and $\pi\mathbf1$ contribute on the scale $\Xi_{\mathcal E}$. Here is the tail estimate, including the case of deletions. Fix $0<\varepsilon<\pi/1000$ and call an available pair bad when the circular distance of $t_i+t_j$ from zero exceeds $\varepsilon$. Since \[ |1-q+qe^{iu}|^2=1-4q(1-q)\sin^2(u/2), \] the region with at least $k(\log k)^2$ bad pairs has integral at most $(2\pi)^k e^{-ck(\log k)^2}=o(\Xi_{\mathcal E})$ by \eqref{eq:spectrum}. Otherwise there is a vertex outside $J$ incident with $O_\rho((\log k)^2)$ bad pairs. Among its good neighbors outside $J$ there are $\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\varepsilon$ of zero. All but $R_0=O_\rho((\log k)^2)$ angles are consequently within $3\varepsilon$ of the same $b\in\{0,\pi\}$. Outside the cube of radius $10\varepsilon$ about $b$, fix an exceptional angle $t_i$. It has at least $(1-\rho)k-R_0-1$ available neighbors in this core. Replacing $t_i$ by $s$ within $\varepsilon$ of $b$ moves their pair sums from distances above $7\varepsilon$ to distances below $4\varepsilon$ (allowing equality at the latter endpoint). Each corresponding factor gains a fixed ratio $e^\gamma>1$. For the other available neighbors, exclude from the replacement interval a $k^{-2}$-neighborhood of each $\pi-t_j$. This leaves length at least $\varepsilon$ and bounds those factors below by $k^{-2}/\pi$, since $|1-q+qe^{iu}|\ge|\cos(u/2)|$. In particular we can take $R_0=\lceil 4(1-\rho)^{-1}\log^2 k\rceil+2$ and fix a core of exactly $k-R_0$ coordinates. For fixed core, exceptional index $i$, and all angles except $t_i$, let $I^*$ be the surviving replacement interval with the exclusions above. For all $s\in I^*$ and all bad values $t_i$ at distance greater than $10\varepsilon$ from $b$, \[ M(t)\le e^{-\gamma((1-\rho)k-R_0-1)}(\pi k^2)^{R_0} M(t_{-i},s)\le e^{-c k} M(t_{-i},s). \] This is a product inequality and remains valid if a nonincident factor vanishes. Since $|I^*|\ge\varepsilon$, integrating in the two scalar variables bounds the bad-fiber integral by $(2\pi/\varepsilon)e^{-ck}$ times the full fiber integral. Fubini and a union bound over at most $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(\Xi_{\mathcal E})+e^{-c'k}\int M$. The combinatorial cost has logarithm $O_\rho(\log^3 k)$. Inside the fixed cube about zero, $-\log M$ is even and has Hessian at least $c_{\delta,\rho}k I$: each scalar negative log modulus has second derivative at least $\delta(1-\delta)/2$ near zero, and the available-pair quadratic form satisfies the lower bound above. For the probability measure proportional to $M$ on this cube, each coordinate has tail at $r$ at most $2e^{-c_{\delta,\rho}kr^2/2}$. Indeed, factoring $e^{-c_{\delta,\rho}k\|t\|^2/2}$ from the density leaves a log-concave function on the cube. Pr\'ekopa's marginal theorem then gives a coordinate density proportional to $e^{-c_{\delta,\rho}kx^2/2}h_0(x)$, with $h_0$ even and log-concave (extend the cube density by zero). Thus $h_0$ decreases in $|x|$. Its covariance with $\mathbf1_{\{|x|\ge r\}}$ under the centered Gaussian law is nonpositive, which proves the tail comparison after normalization. A union bound at $r_k$ gives $o(1)$ of the fixed-cube mass outside the small cube. Translation handles the cube at $\pi\mathbf1$. Once the small-cube integral of $M$ is $O(\Xi_{\mathcal E})$, absorption of $e^{-c'k}\int M$ proves the asserted tail estimate. \paragraph{The local expansion.} Write $U=[-r_k,r_k]^k$ and $s_{ij}=t_i+t_j$. Multiply the characteristic function by the phase that centers at the mean. On $U$ its logarithm is \[ -\tfrac12 t^TQ_{\mathcal E}t+if(t)+h(t)+O_\delta(k^{-1/2}\log^5 k), \] where the sums below run over available pairs and \[ f=\tfrac16\sum_{ij} w_{ij}(2q_{ij}-1)s_{ij}^3,\qquad h=\tfrac1{24}\sum_{ij}w_{ij}(1-6w_{ij})s_{ij}^4 . \] The error comes from summing $O_\delta(|s_{ij}|^5)$ per edge. Let $T\sim N(0,Q_{\mathcal E}^{-1})$ and $\nu=\mathbb Eh(T)$. Its edge-coordinate variances are $O(k^{-1})$, giving $\|h(T)\|_{L^2}=O(1)$ and $\Pr(T\notin U)\le 2k e^{-c\log^2 k}$. On $U$, $|h|\le C\log^4 k$ and $\|\nabla h\|_2=O(\log^3 k)$. In standard Gaussian coordinates $h$ therefore has Lipschitz constant $K=O(k^{-1/2}\log^3 k)$. Extend it with the same Lipschitz constant and clip to $[-C\log^4 k,C\log^4 k]$. The extension $H$ has $\mathbb EH=\nu+o(1)$ by the Gaussian tail bound. Gaussian concentration gives $\mathbb E e^{s(H-\mathbb EH)}\le e^{s^2K^2/2}$ for $s=1,2$. Together with Jensen's lower bound this gives $\mathbb Ee^{sH}=e^{s\nu}+o(1)$ for $s=1,2$, since $|\nu|=O(1)$. Expanding the square gives $\mathbb E(e^H-e^\nu)^2=o(1)$. The extension agrees with $h$ on $U$ in Gaussian coordinates, and $\Pr(T\notin U)=o(1)$, so $e^{h(T)}\mathbf1_U(T)=e^\nu+o_{L^1}(1)$. Integrating the modulus on $U$ gives $\Xi_{\mathcal E}(e^\nu+o(1))$, which proves the residual atom bound by inversion and the preceding tail estimate. \paragraph{The centered atom.} For the full array, write $T=Q^{-1/2}Z$ with $Z$ standard Gaussian. For $e=\{i,j\}$, write $q_e=q_{ij}$, $v_e=Q^{-1/2}u_e$, $Y_e=\langle v_e,Z\rangle$ and $a_e=w_e(2q_e-1)/6$. Put $F=f(T)=\sum_e a_eY_e^3$ and $\mu=\mathbb EF^2$. We show directly that $\mathbb E e^{iF}=e^{-\mu/2}+O_\delta(k^{-1/2})$. The proof uses the Gaussian Poincar\'e inequality twice, in the spirit of~\cite{Chatterjee}. All derivatives below are with respect to $Z$. The identity $\sum_e w_e v_e v_e^T=I$ and the variance floor give $\sum_e v_e v_e^T\preceq C I$. In particular $\|\sum_e t_e v_e\|^2\le C\sum_e t_e^2$ for all scalar coefficients $t_e$, by duality. Also $\|v_e\|^2\le C/k$ by \eqref{eq:spectrum}. Since $\nabla F=3\sum_e a_eY_e^2v_e$, the Gaussian fourth moment gives $\mathbb E\|\nabla F\|^2\le C\sum_e\mathbb E Y_e^4=O(1)$. Thus $\mu=O(1)$ by Gaussian Poincar\'e and oddness. Let $\ell=\mathbb E\nabla F$, so $\|\ell\|=O(1)$. For the Gaussian generator $\mathcal L=\Delta-z\cdot\nabla$ put $u(z)=(F(z)+2\langle\ell,z\rangle)/3$. Since $F$ is homogeneous cubic and $\Delta F(z)=2\langle\ell,z\rangle$, one has $-\mathcal Lu=F$. Gaussian integration by parts now gives \[ \mathbb E[Fg(F)]=\mathbb E[g'(F)\Gamma],\qquad \Gamma=\tfrac13(\|\nabla F\|^2+2\langle\ell,\nabla F\rangle),\qquad \mathbb E\Gamma=\mu . \] The last equality follows by taking $g(x)=x$. To bound the variance, put $b_e=\langle v_e,\nabla F+\ell\rangle$. Differentiating $\Gamma$ and using $\nabla^2 F=6\sum_e a_eY_e v_e v_e^T$ gives \[ \|\nabla\Gamma\|^2 =16\Big\|\sum_e a_e Y_e b_e v_e\Big\|^2 \le C\sum_e Y_e^2b_e^2 . \] Each $b_e$ is a polynomial of degree at most two. For any such polynomial $q$ and any Gaussian coordinate $Y=\langle v,Z\rangle$, $\mathbb E[Y^2 q^2]\le6\|v\|^2\mathbb E q^2$, regardless of their dependence. To see this for $v\ne0$, rotate $Y/\|v\|$ to a standard coordinate $x$ and condition on the others. Write $q=A(x^2-1)+Bx+D$. Then $\mathbb E_x q^2=2A^2+B^2+D^2$, whereas $\mathbb E_x x^2q^2=10A^2+3B^2+D^2+4AD\le6\mathbb E_x q^2$. Another application of Poincar\'e, followed by $\sum_e v_ev_e^T\preceq C I$, gives \[ \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 $\phi(s)=\mathbb E e^{isF}$ satisfies $\phi'(s)+\mu s\phi(s)=-s\,\mathbb E[(\Gamma-\mu)e^{isF}]$. Integration on $[0,1]$ gives $|\phi(1)-e^{-\mu/2}|\le\tfrac12\sqrt{\operatorname{Var}\Gamma}$. This estimate is uniform even when $\mu$ approaches zero. Combining the cubic and quartic estimates gives the centered integral on $U$ as $\Xi_{\mathcal E}(e^{-\mu/2+\nu}+o(1))$. For an integral mean $b$ of even total, the phase factor at $\pi\mathbf1$ is $e^{-i\pi\sum b_i}=1$. The two peaks therefore add. The full centered probability is \[ \frac{2}{(2\pi)^{k/2}\sqrt{\det Q}}\big(e^{-\mu/2+\nu}+o(1)\big). \] The leading correction is bounded away from zero uniformly since $\mu+|\nu|=O_\delta(1)$. The upper spectral bound in \eqref{eq:spectrum} now gives the elementary exponential lower bound in Lemma~\ref{lem:centered}. \paragraph{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. \begin{thebibliography}{9} \bibitem{AKS} N.~Alon, M.~Krivelevich and B.~Sudakov, \emph{Large nearly regular induced subgraphs}, SIAM Journal on Discrete Mathematics \textbf{22} (2008), 1325--1337. \href{https://doi.org/10.1137/070704927}{doi:10.1137/070704927}. \bibitem{BH} A.~Barvinok and J.~A.~Hartigan, \emph{The number of graphs and a random graph with a given degree sequence}, Random Structures \& Algorithms \textbf{42} (2013), 301--348. \href{https://doi.org/10.1002/rsa.20409}{doi:10.1002/rsa.20409}. Preprint: \href{https://arxiv.org/abs/1003.0356v3}{arXiv:1003.0356v3}. \bibitem{Chatterjee} S.~Chatterjee, \emph{Fluctuations of eigenvalues and second order Poincar\'e inequalities}, Probability Theory and Related Fields \textbf{143} (2009), 1--40. \href{https://doi.org/10.1007/s00440-007-0118-6}{doi:10.1007/s00440-007-0118-6}. \bibitem{DM} P.~W.~Dyson and B.~D.~McKay, \emph{Ramsey numbers for regular induced subgraphs}, preprint (2026), \href{https://arxiv.org/abs/2604.08215v3}{arXiv:2604.08215v3}. \bibitem{IM} M.~Isaev and B.~D.~McKay, \emph{Complex martingales and asymptotic enumeration}, Random Structures \& Algorithms \textbf{52} (2018), 617--661. \href{https://doi.org/10.1002/rsa.20754}{doi:10.1002/rsa.20754}. \bibitem{KSW} M.~Krivelevich, B.~Sudakov and N.~Wormald, \emph{Regular induced subgraphs of a random graph}, Random Structures \& Algorithms \textbf{38} (2011), 235--250. \href{https://doi.org/10.1002/rsa.20324}{doi:10.1002/rsa.20324}. \bibitem{Levy} A.~E.~Levy, \emph{The lower-bound problem for regular induced subgraphs of type-based random graphs}, preprint (2026), \href{https://arxiv.org/abs/2608.08169v2}{arXiv:2608.08169v2}. \bibitem{RamosAbsorption} A.~F.~Ramos, D.~B.~Hulak and R.~J.~G.~B.~de Queiroz, \emph{Pair-trace absorption certificates for regular induced subgraphs}, preprint (2026), \href{https://arxiv.org/abs/2604.23882v1}{arXiv:2604.23882v1}. \bibitem{Palomar} A.~F.~Ramos, D.~B.~Hulak and R.~J.~G.~B.~de Queiroz, \emph{Regular induced subgraphs in bounded independent-edge arrays}, Palomar Registry, 19 November 2026, version 1. \href{https://palomar-registry.org/entry?id=PALOMAR-2026-11-19-000016&version=1}{Registry entry}; \href{https://github.com/Arthur742Ramos/Math-Formalization/tree/251dd555eb636ac0eddb2387b348bad7f5539894/combinatorics/bounded-independent-edge-regular-subgraphs}{Lean source at commit \texttt{251dd555}}; \href{https://github.com/Arthur742Ramos/Math-Formalization/blob/251dd555eb636ac0eddb2387b348bad7f5539894/combinatorics/bounded-independent-edge-regular-subgraphs/COVERAGE.md}{coverage map}. \end{thebibliography} \end{document}