WorksMathematics
Regular induced subgraphs in bounded independent-edge arrays
Abstract
Let be a random graph whose edges are independent and whose edge probabilities lie in for a fixed . With probability at least , contains a regular induced subgraph on at least vertices. If all expected degrees are equal, each prescribed order up to a small multiple of occurs with failure probability at most , for sufficiently large. The same probability estimate holds up to order for a Lipschitz kernel in dimension , and up to order for an array admitting a bounded symmetric completion of rank at most . A linear product array has largest regular induced order 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 , Krivelevich, Sudakov and Wormald give a high-probability upper bound of and find regular induced sets at subcritical orders. In particular 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 for the simple graph on in which distinct unordered pairs are present independently, with probabilities . Throughout, is fixed and for . Write for the event that some set of exactly vertices induces a regular graph, and put . Thus . When a domain is specified, and refer to the induced array on . 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 .
There are such that
In each of the three cases below there are constants and such that, for every integer ,
| Hypothesis on the array | |
| All expected degrees are equal | |
| Symmetric -Lipschitz kernel on | |
| Bounded symmetric matrix completion of rank at most |
Table 1.
In the kernel case for arbitrary deterministic types, takes values in , and . A completion is a matrix with the prescribed off-diagonal entries. The constants and the onset depend only on and, where applicable, the fixed parameters or , with .
For equal expected degrees, (1) gives high probability for . At it gives a success probability bounded away from zero uniformly in . For the other two classes, grows as a positive power of even at the indicated endpoint. In particular every bounded one-dimensional Lipschitz model has a regular induced subgraph of order at least 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 -vertex graph has order [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 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 lower bound with high probability for Levy’s model, with depending on the probability floor and the kernel’s Lipschitz constant. Levy also conjectures the sharp family-wide constant . The constant in our order bound depends on the model parameters.
Where the scales come from. In a domain of vertices with normalized expected degrees within of one another, many -sets can be tilted to the same integer target degree. Two independent uniform -sets share vertices in expectation. If they share vertices, averaging the tilt over the shared vertices gives a factor of order in the small-overlap range. Thus is the natural condition for a bounded second moment. Nearly coincident sets require a separate estimate, which is what permits the endpoint . 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 .
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 with probabilities , let be the degree vector, , and . A present edge adds to , so its covariance matrix is
The following two estimates are the analytic inputs. The determinant normalization is essential. Replacing it in both estimates by would cost an exponential factor even for sets sharing only two vertices.
Lemma 2.1 (Full and residual degree atoms). Fix a floor for the . If is integral with even total, then, uniformly for sufficiently large ,
For the upper bound, assume only the same floor on the edge probabilities. Fix and delete all edges inside a set of vertices and let and denote the remaining degree vector and covariance. For every sufficiently large (depending on ) and every integral target , one has
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 , obtaining requires a single residual target. We record the resulting comparison.
Corollary 2.2. Under the centering and parity hypotheses above, for every configuration on the pairs in ,
Proof. With , the trace of is . The residual covariance satisfies by (A.1) below. Consequently
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 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 , let , and suppose for . Let have entries off the diagonal and zero diagonal, and put
Then
Proof. For every ,
These identities prove the two spectral bounds and, in particular, invertibility. For the maximum norm, set . The matrix is stochastic. Two distinct rows have common mass at least
For a real vector , write . Subtracting the common mass from two probability rows leaves two nonnegative measures of equal mass at most . Their averages of differ by at most . Hence
If , the inequality implies . Let and . At a coordinate attaining the equation gives ; at a coordinate attaining it gives . Thus , and
For , take and use . This proves the asserted inverse bound.
Lemma 2.4 (A deterministic vertex tilt)
Lemma 2.4 (A deterministic vertex tilt). Fix . There are constants , , , and such that the following holds. Let , let , and let have even total sum. Put
There is a vector for which
satisfies
If and are the original and tilted product measures, respectively, their relative entropy obeys
On every graph configuration with degree vector , the likelihood ratio is the constant . Consequently
Proof. Define
The gradient of is the vector of tilted expected degrees, and has the form of Lemma 2.3, with weights . For , one may take
as a lower bound both for and for . Set . Throughout that cube,
We first construct the tilt. Since , Taylor expansion gives
The first two derivatives of the logistic function are bounded absolutely. On the cube of radius , each row has summands, each depending on a sum of two coordinates. The one-variable mean value formula therefore gives
If take . Otherwise put and . Choose so that and . On the closed cube of radius , the preceding estimates give and . The contraction theorem gives a fixed point in that cube. It solves , satisfies the stated maximum-norm bound, and preserves the floor .
For the Euclidean bound, integrate the Hessian along the segment from zero to the fixed point. Since ,
Cauchy–Schwarz yields .
For any graph configuration , let be its degree vector. The exact product-measure likelihood ratio is
Taking its logarithmic expectation under , and using and , gives
On , the logarithmic likelihood ratio equals this same . Hence . Under , the target degrees are exactly the means, they are integral with even total, and every edge probability lies in . Applying the centered degree estimate, Lemma 2.1, with floor , and enlarging and if needed, proves (2).
Sampling distinct vertices
Lemma 2.5 (Concentration for sampling without replacement). Let , let , and let be the sum of a uniformly chosen -element subset of these numbers, where . Then
and for every ,
Also .
Proof. For nonnegative , their elementary symmetric polynomial satisfies
For , 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 . 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 there is equality.
Take . The left side of (4) is . For a single uniform draw , the log moment generating function of has value and derivative zero at zero. Its second derivative is the variance under an exponential tilt, at most since . Hence
Exponential Markov at gives the two tails. Comparing the second derivatives at zero gives , 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 . Let be a symmetric array on with entries in , and let . Write
Suppose that
Uniformly along sequences with , , and , there is a legal degree , with even and , and a family of size at least , such that every has a vertex tilt satisfying
Here and depend only on . There is no restriction on in this lemma.
Proof. Choose before selecting the vertices. If is even, choose a nearest integer to ; if is odd, choose a nearest even integer. For large , uniformly for , this is a legal degree with the stated parity and error. Set , so . Choose a uniform ordered tuple of distinct labels in , and put
Conditional on , the remaining labels form a uniform -subset of . Consequently
where the variance assertion follows from Lemma 2.5. The same lemma, with , and a union bound give
with probability at least . There is no independence assertion between different row sums. Their squared norm is instead controlled directly by conditional second moments:
Markov’s inequality therefore gives
with probability at least . The two displayed drift bounds hold together with probability at least for all sufficiently large .
On their intersection uniformly. The tilt in Lemma 2.4 therefore exists, with the fixed floor . Its maximum norm is at most , its squared energy at most , and its negative log probability cost beyond the centered atom at most . Substitution of (5) and (6) gives all three asserted estimates. Both drift tests are invariant under reorderings, and every -set has orderings, so at least half of the unordered sets qualify.
Shared edges and a weighted count
Let be the event that a candidate induces a -regular graph, where the degree and the family come from Lemma 2.6. Weight a success on by , where . Then
This weighting allows different candidates to have very different probabilities. Write for the normalized joint probability.
Lemma 3.1 (Shared-edge likelihood). Let , , and . For the normalized joint probability satisfies
where depend only on . For the ratio is one.
Proof. Write for the shared-edge configuration and for its tilted likelihood relative to its original law. Constancy of the full likelihood on gives
The last ratio is bounded by Corollary 2.2. Conditional on , the two events depend on disjoint sets of remaining edges. Their normalized joint probability is therefore at most . For one shared edge with logit increments , put . Its contribution to the logarithm of the expectation is
since . Sum over edges and use . For the two sets share no edge. ▫
For fixed and a uniform -set in , write . A union bound over the -subsets of yields
Here . 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 block scale when every row is nearly balanced.
Theorem 3.2 (Mean-square drift). Let be an independent-edge array on vertices with . Write for some . Suppose and . There exists such that, uniformly when , , and ,
When the first term can be replaced by .
Proof. Write . For , . If bounds for all candidate pairs of overlap , then
Indeed, exactly ordered pairs of unrestricted -sets have intersection size . Write . For , (7) and the total tilt energy give a ratio at most . By (8) their contribution to is at most , where . Choose . This sum is , or when .
For , use with . Now (8) gives with . Since ,
after taking . Sum the geometric tail, including , and apply . ▫
Theorem 3.3 (A balanced block). Let the independent edges on have probabilities in and define for . Fix . There are depending only on such that, for all sufficiently large , if and , then . The successful candidates may all be tested at the same degree .
Proof. Apply Lemma 2.6 with . It gives one and a family occupying at least half of all -sets. For constants and depending only on , every candidate satisfies
We bound in three overlap ranges.
Small overlaps. For , symmetry in and the arithmetic–geometric mean inequality bound the sum of over candidate pairs of overlap by the corresponding sum of . More explicitly, and the two sums on the right agree after swapping . Keep fixed and extend the other sum to all . Each -subset now occurs times. Thus, for any nonnegative and any with ,
where on the right is uniform among the -subsets of . The factor in front of is at most two. Assign a zero contribution when . The elementary symmetric mean bound (4) and on give
The normalized contribution is at most . Put and . The terms through sum to at most , since gives . For , (3.2) gives and eventually.
Intermediate overlaps. For , use in (7). The resulting sum is at most since .
Large overlaps. For put . Condition on all edges of . Each vertex of needs a specified number of edges to to reach in . Those sums involve disjoint sets of fresh edges, so they are conditionally independent. For a sum of independent Bernoulli variables of floor , one-dimensional inversion gives
Use and take for . If denotes the exposed edges, is -measurable and . Multiplying by and taking expectations gives , including . Multiply by . The logarithm of the product is at most
For , concavity gives . As , the braces are at most . The constant depends only on . Choose . After accounting for the candidate fraction, the entire range contributes at most . This last estimate retains the information in the fresh vertices even when the two candidates nearly coincide.
The normalized second moment is bounded by a constant independent of . Cauchy–Schwarz gives .
Extraction with small mean-square degree variation
For a symmetric array , , of order , write
Its normalized degree variance is
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 . If , there is a set of order at least whose induced weighted density is greater than .
Proof. Put . Then
Select vertices independently with probabilities , and call the resulting set . Its expected order is . Expansion of the edge expectation gives
Since
we obtain
Also , so independence gives
Subtracting times (11) from (10) yields
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 , gives . If every set of order at least had weighted density at most , the random surplus in (12) would be nonpositive off that exceptional event. On the event it is at most . Its expectation would therefore be at most , contradicting . The resulting set has at least two vertices since .
Lemma 4.2 (Mean-square extraction). Let , and put
If , every symmetric array in on vertices has an induced subarray of order
whose degree sums and average satisfy
In particular the logarithm of the vertex loss is . If the initial entries lie in , then so do the extracted entries and their common density .
Proof. Repeatedly restrict the current array to a set supplied by Lemma 4.1 whenever its normalized degree variance exceeds . Through the first restrictions, whenever defined, the current order after steps is at least , so and the increment lemma applies. Each restriction retains at least one quarter of the vertices and increases the density by more than . There are fewer than restrictions, since such increases would raise a nonnegative initial density above one. The terminal subarray therefore has order and
Remove the set of vertices satisfying . Its size is at most . Let , , and let denote the degree sums of the remaining subarray. Then . For , write
Consequently
Centering at the new average cannot increase the sum of squares, and it increases the preceding maximum bound by at most a factor of two. Since ,
Using , we find
Similarly,
These are (4.4). The size bound follows from . The entry and density assertions follow by restriction and averaging.
Theorem 4.3 (A universal squared-logarithmic lower bound). For every fixed there are constants and such that, for all ,
Proof. Put and choose . For sufficiently large , and
Thus the onset of Lemma 4.2 holds. Applied directly to the given probability array, it supplies a deterministic induced domain of order . On this domain the normalized maximum degree-sum drift is at most , and the normalized root-mean-square drift is at most , so .
Let be the tolerance constant in Theorem 3.2, choose with , and take
Then , , and uniformly for ,
Theorem 3.2 therefore gives a regular induced -set with failure probability at most
After enlarging the onset, this is at most . Since eventually, take . 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 be a constant for which Theorem 4.3 holds. For every fixed and all sufficiently large ,
Consequently, if is any sequence of random graphs on with independent edges within each graph and all its probabilities in , then almost surely
No independence between different members of the sequence is needed.
Proof. Set and . Choose disjoint blocks of vertices. Each block fails to contain the universal witness with probability at most . The induced graphs on the blocks use disjoint sets of independent edge variables, so the probability that all blocks fail is at most
for large : use and . Since , any successful block supplies the asserted order for every fixed .
The error probabilities are summable in . The probability of any failure at an index is at most the tail of their convergent sum, which tends to zero as . 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 . To obtain (1) we need a positive success probability in order 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 be the common normalized expected degree. Use Theorem 3.3 with , and choose small enough that when . Take a uniform permutation and group its first positions into blocks of size . Conditional on a vertex occupying a specified position in a given block, the other vertices there are sampled without replacement from the other vertices. The probability that its block row mean differs from by more than is at most . The probability that a specified block contains any such row is at most for large . 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 .
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 . This proves the equal-degree assertion of Theorem 1.1.
Packing blocks from large cells
Lemma 5.1. Suppose there are fixed , and with the following property. For each induced domain of order and each with , the domain contains a set of at least vertices on which the off-diagonal probabilities lie within of a common . Then (1) holds up to , uniformly with constants depending on , , , .
Proof. Take and , with from Theorem 3.3 for . For small enough, throughout the stated range. While at least vertices remain, find such a cell, take exactly of its vertices as a block, and remove just that block. Every restriction of the cell still has all pair probabilities within of , so all block row means satisfy the same bound. This produces at least 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 cubes of maximum-norm diameter . In every domain of vertices some cube contains at least types. Symmetry of gives the Lipschitz estimate in either argument, so the range of the edge probabilities there is at most . Taking any off-diagonal entry as verifies the hypothesis of Lemma 5.1 with . No assumption on the empirical distribution of the types is required.
Rank and diagonal subdivision. Let be a bounded symmetric completion of rank at most . A direct covering of its row coordinates at resolution would give . Symmetry permits the coarser resolution in those coordinates, provided one also controls the diagonal. This improves the cell exponent to .
Lemma 5.2. Every principal submatrix of order contains a set of at least vertices on which the range of all entries is at most , for .
Proof. Write for the rank of the submatrix, still called . The case is immediate. Choose row indices and column indices for a -minor of maximum absolute determinant. Each row is a linear combination of the rows indexed by . Cramer’s rule on the columns shows that its coefficients lie in . By symmetry, with ,
Set and retain a largest coordinate cube of side . It has at least vertices. On it the diagonal values have range at most , by expanding their pairwise differences. Subdivision into intervals of length now costs at most further classes. Keep a largest class. For any two of its vertices,
The last term has absolute value at most . The first two diagonal terms each range over an interval of length , so the pair entries have range at most . The retained fraction is at least .
On a cell with at least two vertices, choose an off-diagonal entry as the common . Lemma 5.1 with gives , 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 , the two possible edge probabilities are and . The unrestricted logarithmic bounds always apply. If the base is regular, the perturbed expected degrees are equal, so the balanced bound applies as well.
A sharp square-root example
For with , take
Alon, Krivelevich and Sudakov used the choice , to obtain an upper bound of order [1 Section 3]. We determine the order for the same product model over the full fixed parameter range. The array has rank-one completion and is generated by the Lipschitz kernel on the unit interval. Given , choosing and 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 , depending only on , such that
Take and for a sufficiently small fixed . Then (1) bounds failure by , and 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 -set , , write , , and . Under the fixed floor,
With arbitrary probabilities in the bound alone still holds.
Proof. Put and tilt by . On every regular outcome . Writing , the likelihood identity therefore gives . The curvature of every one-edge log partition function is at most . As and ,
This proves the floor-free estimate, including deterministic edge coordinates. Under the fixed floor the tilt preserves a positive floor depending only on , since . Under the tilted law, fix a degree and expose the edges in rows , revealing with at step . Given the previous rows, the required number of successes in the fresh trials is fixed. By (9) its conditional probability is at most , uniformly in the history. Earlier degree constraints are measurable at this point. Iterating conditional expectations gives at most for the prescribed degree vector, as in the exposure argument of [1 Section 3]. Summing over the possible degrees, using and , gives for tilted regularity. Multiplying by the exponential penalty proves (15).
Upper bound in Theorem 6.1. For the product array . Therefore
Use and choose minimizing . The minimum is at most its average over . It follows that
For a fixed anchor , set . Comparing the decreasing Gaussian on either side of with its integral gives . The sum of over the -sets containing is at most , since . Sum (15) over the choices of anchor, using the bound just obtained for the sets assigned to each. With this yields
Choose so that . Summing this bound over all gives and hence the asserted upper tail for .
The unrestricted problem. Does every fixed floor admit a for which ? The product example forces 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 implies that some -set satisfies by the floor-free bound. To obtain the corresponding test for , one must sum over every order , 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 be the available pairs after deleting the pairs in (take for the full array), let , and set
Integration is with respect to Lebesgue measure on . Fourier inversion contributes the separate factor .
The covariance. Write . In the unweighted sum , contrasts within and within its complement have eigenvalues and respectively. On the two normalized constant vectors of those sets the matrix is
Its determinant is and its trace is at most . Taking the variance floor into account, or using the complete-pair identity of Lemma 2.3 for , gives
The two peaks. Put . Only the cubes of radius around and contribute on the scale . Here is the tail estimate, including the case of deletions. Fix and call an available pair bad when the circular distance of from zero exceeds . Since
the region with at least bad pairs has integral at most by (A.1). Otherwise there is a vertex outside incident with bad pairs. Among its good neighbors outside there are 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 of zero. All but angles are consequently within of the same .
Outside the cube of radius about , fix an exceptional angle . It has at least available neighbors in this core. Replacing by within of moves their pair sums from distances above to distances below (allowing equality at the latter endpoint). Each corresponding factor gains a fixed ratio . For the other available neighbors, exclude from the replacement interval a -neighborhood of each . This leaves length at least and bounds those factors below by , since . In particular we can take and fix a core of exactly coordinates. For fixed core, exceptional index , and all angles except , let be the surviving replacement interval with the exclusions above. For all and all bad values at distance greater than from ,
This is a product inequality and remains valid if a nonincident factor vanishes. Since , integrating in the two scalar variables bounds the bad-fiber integral by times the full fiber integral. Fubini and a union bound over at most choices of phase, core complement and index show that the mass outside the two fixed cubes is at most . The combinatorial cost has logarithm .
Inside the fixed cube about zero, is even and has Hessian at least : each scalar negative log modulus has second derivative at least near zero, and the available-pair quadratic form satisfies the lower bound above. For the probability measure proportional to on this cube, each coordinate has tail at at most . Indeed, factoring from the density leaves a log-concave function on the cube. Prékopa’s marginal theorem then gives a coordinate density proportional to , with even and log-concave (extend the cube density by zero). Thus decreases in . Its covariance with under the centered Gaussian law is nonpositive, which proves the tail comparison after normalization. A union bound at gives of the fixed-cube mass outside the small cube. Translation handles the cube at . Once the small-cube integral of is , absorption of proves the asserted tail estimate.
The local expansion. Write and . Multiply the characteristic function by the phase that centers at the mean. On its logarithm is
where the sums below run over available pairs and
The error comes from summing per edge. Let and . Its edge-coordinate variances are , giving and . On , and . In standard Gaussian coordinates therefore has Lipschitz constant . Extend it with the same Lipschitz constant and clip to . The extension has by the Gaussian tail bound. Gaussian concentration gives for . Together with Jensen’s lower bound this gives for , since . Expanding the square gives . The extension agrees with on in Gaussian coordinates, and , so . Integrating the modulus on gives , which proves the residual atom bound by inversion and the preceding tail estimate.
The centered atom. For the full array, write with standard Gaussian. For , write , , and . Put and . We show directly that . The proof uses the Gaussian Poincaré inequality twice, in the spirit of [3]. All derivatives below are with respect to .
The identity and the variance floor give . In particular for all scalar coefficients , by duality. Also by (A.1).
Since , the Gaussian fourth moment gives . Thus by Gaussian Poincaré and oddness. Let , so . For the Gaussian generator put . Since is homogeneous cubic and , one has . Gaussian integration by parts now gives
The last equality follows by taking . To bound the variance, put . Differentiating and using gives
Each is a polynomial of degree at most two. For any such polynomial and any Gaussian coordinate , , regardless of their dependence. To see this for , rotate to a standard coordinate and condition on the others. Write . Then , whereas . Another application of Poincaré, followed by , gives
Finally satisfies . Integration on gives . This estimate is uniform even when approaches zero.
Combining the cubic and quartic estimates gives the centered integral on as . For an integral mean of even total, the phase factor at is . The two peaks therefore add. The full centered probability is
The leading correction is bounded away from zero uniformly since . 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]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]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]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]P. W. Dyson and B. D. McKay, Ramsey numbers for regular induced subgraphs, preprint (2026), arXiv:2604.08215v3.arxiv.org/abs/2604.08215
- [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]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]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]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]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.