betaFeedback

WorksMathematics

The constant Steiner kernel is not optimal at large girth

Abstract

In the paper "nonlinear lower-tail large deviations at criticality", we bound the number of order-nn Steiner triple systems with no Pasch configuration. In doing so, we show that a certain variational problem is minimised by a constant kernel. Using ChatGPT 6 Pro, we also discovered that the analogous variational problems for Steiner triple systems of girth at least gg, for large gg, are not minimised by the constant kernel, and we included a brief remark to this effect. In this note (not intended for publication), we present the details of this proof.

Note: This proof was discovered with ChatGPT 6 Pro, and we are not attempting to claim any kind of credit for it; this note only exists to share information that may be of interest to the community. Much of the text in this note was produced by ChatGPT 6 Pro and Claude Opus 5.5 (at maximum effort).

Introduction

A Steiner triple system (STS) of order nn is a collection of triples from [n][n] such that every pair of points lies in exactly one triple; it has (n2)/3\binom{n}{2}/3 triples. For k≥4k \ge4, an Erdős kk-configuration is a set of kk triples spanning only k+2k+2 points, such that every subset of ss of its triples with 2≤s<k2 \le s < k spans at least s+3s+3 points. (For s=2s = 2 this says that two triples share at most one point, as they must in an STS.) The smallest one is the Pasch configuration, four triples on six points. Erdős configurations play a role for triple systems similar to that of cycles for graphs, and an STS has girth at least gg if it contains no Erdős kk-configuration with 4≤k<g4 \le k < g. We write EkE_k for the set of isomorphism classes of Erdős kk-configurations.

Glock, Kühn, Lo and Osthus [2] conjectured an asymptotic formula for the number of STS of order nn with girth at least gg, and Kwan, Sah, Sawhney and Simkin [4] proved the corresponding lower bound. In [3 Theorem 1.17], we proved the matching upper bound for g=5g = 5. Our proof reduces the count to a variational problem over “profiles” of triples, and then shows [3 Lemma 8.10] that the uniform profile is optimal. In [3 Remark 1.19] we report that for large gg the uniform profile is not optimal for the corresponding variational problems, so that our method, in this form, gives upper bounds weaker than conjectured. This note proves a precise version of that statement. As remarked in [3], we suspect that this provides evidence that the conjecture is false.

Theorem statement

A Steiner kernel on a probability space (Ω,μ)(\Omega,\mu) is a symmetric measurable function W:Ω3→[0,∞)W:\Omega^3 \to[0,\infty) such that, for almost every (x,y)∈Ω2(x,y) \in\Omega^2, we have ∫W(x,y,z) dμ(z)=1\int W(x,y,z)\,\mathrm{d}\mu(z)=1; we call this the pair constraint.

For a Steiner kernel WW, we define the entropy cost

D(W)=∫Ω3Wlog⁡W dμ3.D(W)=\int_{\Omega^3}W\log W\,\mathrm{d}\mu^3.

This quantity is nonnegative because ∫W=1\int W=1, and it vanishes only for the constant kernel W≡1W\equiv1. Also, for a 33-graph FF, define the homomorphism density

tF(W)=∫ΩV(F)∏e∈E(F)W(xe) dμV(F)(x).t_F(W)=\int_{\Omega^{V(F)}}\prod_{e\in E(F)}W(x_e)\,\mathrm{d}\mu^{V(F)}(x).

and let Aut⁡(F)\operatorname{Aut}(F) be the automorphism group of FF. For F∈EkF\in E_k, let

aF=6∣Aut⁡(F)∣.a_F=\frac{6}{|\operatorname{Aut}(F)|}.

and define the girth-gg functional

Ig(W)=D(W)+∑4≤k<g∑F∈EkaFtF(W).(1)I_g(W)=D(W)+\sum_{4\le k<g}\sum_{F\in E_k}a_Ft_F(W). \tag*{(1)}

At the constant kernel, this functional equals

Cg:=Ig(1)=∑4≤k≤g∑F∈EkaF,C_g := I_g(\mathbf{1}) = \sum_{4 \le k \le g} \sum_{F \in\mathcal{E}_k} a_F,

the predicted number of forbidden configurations per triple in a uniformly random STS. For g=5g=5 the only forbidden configuration is the Pasch configuration, so C5=1/4C_5 = 1/4. In [3 Lemma 8.10] we prove the inequality I5(W)≥1/4I_5(W) \ge1/4 for kernels on finite uniform spaces, even without the pair constraint (only ∫W=1\int W = 1 is needed). For general gg the analogous statement would be

Ig(W)≥Cgfor every Steiner kernel W,(2)I_g(W) \ge C_g \qquad\text{for every Steiner kernel } W, \tag*{(2)}

that is, the constant kernel would minimise IgI_g. It does not.

Theorem 1.1. There is a symmetric measurable function UU with ∣U∣≤1|U| \le1 on a probability space, with zero pair marginals, ∫U(x,y,z) dμ(z)=0\int U(x,y,z)\,\mathrm{d}\mu(z) = 0 for all x,yx,y, such that for all sufficiently large gg the Steiner kernel

Wg=1+g−g/5UW_g = 1 + g^{-g/5} U

satisfies Ig(Wg)<CgI_g(W_g) < C_g.

To comment on the connection to the Glock–Kühn–Lo–Osthus conjecture: we would conjecture that for a random order-nn Steiner triple system SS,

log⁡P[S has girth at least g]=−(n2)3⋅min⁡WIg(W)+o(n2).\log\mathbb{P}[S\text{ has girth at least }g] = -\frac{\binom{n}{2}}{3}\cdot\min_W I_g(W) + o(n^2).

If this conjecture were true, then Theorem 1.1 would contradict the conjectured formula in [2] for the number of STS with girth at least gg. It would be a very significant undertaking to actually prove this conjecture (in addition to the ideas in [3], presumably one would need some version of the techniques in [4] or [1]), but we nonetheless view Theorem 1.1 as strong evidence that the Glock–Kühn–Lo–Osthus conjecture is false.

To prove Theorem 1.1, the approach is to consider a slight perturbation 1+εU1+\varepsilon U. This perturbation costs about ε2\varepsilon^2 in entropy, whereas the configuration terms only respond at order ε4\varepsilon^4. What changes with gg is the number of configuration terms, which grows like ggg^g. We look for a sub-configuration that has negative density in some admissible direction UU, and that is contained in so many Erdős configurations that the resulting negative terms add up to more than the entropy cost, even though ε\varepsilon is tiny.

§ 2 shows that the pair constraint severely limits which sub-configurations can play this role: the first ones whose contributions get multiplied by the number of configurations have six edges, and there are only two of them, the 3×33 \times3 grid and one other. § 3 builds UU from a theorem of Sidorenko, which provides a signed kernel with negative grid density, together with a three-colour lift that enforces the pair constraint and switches the other six-edge configuration off. § 4 proves Theorem 1.1 assuming that grids are abundant inside Erdős configurations, and § 5 proves this by completing a grid at random.

What a perturbation of the constant kernel sees

Let U:Ω3→[−1,1]U:\Omega^3 \to[-1,1] be symmetric with zero pair marginals. Then W=1+εUW=1+\varepsilon U is a Steiner kernel for 0≤ε≤10 \le\varepsilon\le1. To compare Ig(1+εU)I_g(1+\varepsilon U) with CgC_g, expand each density by multiplying out ∏e∈E(F)(1+εU(xe))\prod_{e \in E(F)}(1+\varepsilon U(x_e)):

tF(1+εU)=∑A⊆E(F)ε∣A∣tA(U).(3)t_F(1+\varepsilon U)=\sum_{A\subseteq E(F)}\varepsilon^{|A|}t_A(U). \tag*{(3)}

where tA(U)t_A(U) is the density of the 3-graph formed by the edges in AA (vertices of FF covered by no edge of AA simply integrate to 1).

The pair constraint now does most of the work. If some vertex vv lies in exactly one edge e∈Ae\in A, then integrating over xvx_v first replaces U(xe)U(x_e) by its pair marginal, which is zero, so tA(U)=0t_A(U)=0. Call AA leafless if every vertex covered by AA lies in at least two edges of AA. Only leafless sets contribute to (3): the empty set contributes 1, and single edges contribute nothing.

Which leafless edge sets does an Erdős configuration contain? The whole configuration is one. Indeed, if a vertex of F∈EkF\in\mathcal{E}_k lay in only one edge ee, then the other k−1k-1 edges would span at most k+1k+1 vertices, contrary to the definition. So A=E(F)A=E(F) contributes εktF(U)\varepsilon^k t_F(U). Proper subsets are far more restricted, because the definition of Ek\mathcal{E}_k forces them to be sparse while leaflessness forces them to be dense.

Lemma 2.1. Let F∈EkF \in\mathcal{E}_k, and let A⊊E(F)A \subsetneq E(F) be nonempty and leafless. Then ∣A∣≥6|A| \ge6. If ∣A∣=6|A| = 6, then AA covers exactly nine vertices, each lying in exactly two edges of AA, and AA is isomorphic either to the 3×33 \times3 grid GG or to the configuration PP dual to the triangular prism.

Here the grid GG has the nine cells of a 3×33 \times3 array as its vertices, and its three rows and three columns as its edges. The configuration PP is described in the proof.

Proof. Let j=∣A∣j = |A|, and let vv be the number of vertices covered by AA. A single edge has leaves, so j≥2j \ge2, and then the definition of Ek\mathcal{E}_k gives v≥j+3v \ge j + 3. Since each covered vertex lies in at least two of the jj edges, 3j≥2v3j \ge2v. Together these give 3j≥2j+63j \ge2j + 6, so j≥6j \ge6; and if j=6j = 6 both inequalities are equalities, so v=9v = 9 and every vertex lies in exactly two edges of AA.

Such an AA is determined by a graph. Let A∗A^* be the graph whose vertices are the six edges of AA, with one edge for each vertex of AA, joining the two edges of AA that contain it. Each edge of AA has three vertices, so A∗A^* is 3-regular; it has no loops, and no parallel edges because two edges of FF share at most one vertex. Conversely, AA is recovered from A∗A^*: its vertices are the edges of A∗A^*, and its edges are the stars of the vertices of A∗A^*. There are exactly two simple 3-regular graphs on six vertices, K3,3K_{3,3} and the triangular prism. If A∗=K3,3A^* = K_{3,3} with parts {r1,r2,r3}\{r_1,r_2,r_3\} and {c1,c2,c3}\{c_1,c_2,c_3\}, then the vertices of AA are the nine edges ricjr_i c_j, and its edges are the stars of the rir_i and of the cjc_j. These are the rows and columns of a 3×33 \times3 array, so A≅GA \cong G. The prism gives the other configuration, which we call PP. □

Summing (3) over configurations, Ig(1+εU)−CgI_g(1+\varepsilon U)-C_g consists of the entropy term D(1+εU)D(1+\varepsilon U) together with one term aFε∣A∣tA(U)a_F \varepsilon^{|A|}t_A(U) for each F∈EkF \in\mathcal{E}_k (4≤k<g4 \le k < g) and each nonempty leafless A⊆E(F)A \subseteq E(F). By Theorem 2.1 these terms come in three kinds:

  • whole configurations with at most six edges, a fixed finite family contributing O(ε4)O(\varepsilon^4) independently of gg;

  • proper six-edge subsets, which are copies of GG or of PP and contribute ε6tG(U)\varepsilon^6t_G(U) or ε6tP(U)\varepsilon^6t_P(U) each;

  • sets with at least seven edges.

The entropy term is of order ε2\varepsilon^2, with a constant independent of gg. The six-edge terms are therefore the first ones whose total coefficient grows with gg, since the numbers of copies of GG and PP grow with the number of configurations. This tells us what to ask of UU:

(U1) UU is symmetric, ∣U∣≤1|U| \le1, and UU has zero pair marginals;

(U2) tG(U)<0t_G(U) < 0;

(U3) tP(U)=0t_P(U) = 0.

Condition (U3) spares us from comparing the number of copies of PP with the number of copies of GG. Under (U1)–(U3), the six-edge terms add up to −∣tG(U)∣bgε6-|t_G(U)|b_g\varepsilon^6, where

bg=∑4≤k<g∑F∈EkaFNG(F),b_g = \sum_{4 \le k < g} \sum_{F \in\mathcal{E}_k} a_F N_G(F),

and NG(F)N_G(F) denotes the number of copies of GG in FF. We will see that bgb_g, like CgC_g, is g(1+o(1))gg^{(1+o(1))g}. The grid terms then beat the entropy cost as soon as bgε4→∞b_g\varepsilon^4 \to\infty, i.e. for ε\varepsilon somewhat larger than g−g/4g^{-g/4}. They also beat the terms with at least seven edges, whose total weight is at most 2gCg2^g C_g and which are each O(ε7)O(\varepsilon^7), provided ε≤e−Cg\varepsilon\le e^{-C_g} for a suitable constant CC. The choice ε=g−g/5\varepsilon= g^{-g/5} lies comfortably inside this window.

An admissible direction with negative grid density

Condition (U2) asks for a direction in which the grid has negative density, and this is provided by a theorem of Sidorenko. In his terminology it says that the grid is not positive; this is the failure of positivity mentioned in [3 Remark 1.19].

Theorem 3.1 (Sidorenko). There are a probability space (Ω0,μ0)(\Omega_0,\mu_0) and a bounded symmetric measurable function V ⁣:Ω03→RV \colon\Omega_0^3 \to\mathbb{R} with tG(V)<0t_G(V) < 0.

For a proof, see [5 Proposition 1.5]. Dividing VV by ∥V∥∞\lVert V \rVert_\infty, we may assume ∣V∣≤1|V| \le1. Nothing else about VV will matter: it may be nonzero when two of its arguments coincide, and its pair marginals may be arbitrary.

Such a VV is not yet an admissible direction. Nothing forces its pair marginals to vanish, and without that 1+εV1+\varepsilon V is not a Steiner kernel, and the expansion of § 2 would no longer discard edge sets with leaves. We repair this by tensoring with a kernel whose pair marginals do vanish. Given a symmetric function KK on Λ3\Lambda^3 for a probability space (Λ,ν)(\Lambda,\nu), set

U((x,α),(y,β),(z,γ))=V(x,y,z)K(α,β,γ)on (Ω0×Λ)3.U\bigl((x,\alpha),(y,\beta),(z,\gamma)\bigr) = V(x,y,z)K(\alpha,\beta,\gamma) \quad\text{on }(\Omega_0 \times\Lambda)^3.

Integrating over the third argument factorises, so UU has zero pair marginals as soon as KK does, whatever VV is; and tA(U)=tA(V)tA(K)t_A(U)=t_A(V)t_A(K) for every 3-graph AA. Thus (U2) and (U3) become conditions on KK: we need tG(K)>0t_G(K)>0, to keep the sign of tG(V)t_G(V), and tP(K)=0t_P(K)=0.

Both GG and PP are 2-regular: each vertex lies in exactly two edges. This makes the most obvious choice useless. On Λ=Z/2Z\Lambda=\mathbb{Z}/2\mathbb{Z}, the kernel K(α,β,γ)=(−1)α+β+γK(\alpha,\beta,\gamma)=(-1)^{\alpha+\beta+\gamma} has zero pair marginals, but in ∏e∈AK(xe)\prod_{e\in A}K(x_e) each colour of a 2-regular AA appears twice, so tA(K)=1t_A(K)=1: this KK cannot tell GG from PP. And PP does have to be switched off: we know nothing about tP(V)t_P(V), and if it were positive, copies of PP would contribute with the wrong sign.

It turns out that three colours suffice. On Λ=Z/3Z\Lambda=\mathbb{Z}/3\mathbb{Z} with the uniform measure, let ω=e2πi/3\omega=e^{2\pi i/3} and

K(α,β,γ)=Re⁡ωα+β+γ={1if α+β+γ≡0(mod3),−12otherwise.K(\alpha,\beta,\gamma)=\operatorname{Re}\omega^{\alpha+\beta+\gamma}= \begin{cases} 1 & \text{if }\alpha+\beta+\gamma\equiv0\pmod{3},\\ -\frac{1}{2} & \text{otherwise}. \end{cases}

Its pair marginals vanish because ∑γωα+β+γ=0\sum_{\gamma}\omega^{\alpha+\beta+\gamma}=0. The point of a cube root of unity is that the two edges at a vertex can only cancel each other’s characters if they carry conjugate ones, and this turns tA(K)t_A(K) into a count of 2-colourings.

Lemma 3.2. Let AA be a connected linear 3-graph in which every vertex lies in exactly two edges, and let A∗A^* be the graph defined in the proof of Theorem 2.1. Then tA(K)=21−∣A∣t_A(K)=2^{1-|A|} if A∗A^* is bipartite, and tA(K)=0t_A(K)=0 otherwise.

Proof. Write K=12(χ+χ‾)K=\frac{1}{2}(\chi+\overline{\chi}) with χ(α,β,γ)=ωα+β+γ\chi(\alpha,\beta,\gamma)=\omega^{\alpha+\beta+\gamma}, and expand the product over the edges of AA as a sum over choices σ∈{±1}A\sigma\in\{\pm1\}^A of χ\chi or χ‾\overline{\chi} for each edge:

∏e∈AK(xe)=2−∣A∣∑σ∏e∈Aωσe∑v∈exv=2−∣A∣∑σ∏vω(σe+σe′)xv,\prod_{e\in A}K(x_e)=2^{-|A|}\sum_{\sigma}\prod_{e\in A}\omega^{\sigma_e\sum_{v\in e}x_v}=2^{-|A|}\sum_{\sigma}\prod_v\omega^{(\sigma_e+\sigma_{e'})x_v},

where ee and e′e' denote the two edges containing vv. Averaging over xv∈Z/3Zx_v\in\mathbb{Z}/3\mathbb{Z} gives 1 if σe+σe′≡0(mod3)\sigma_e+\sigma_{e'}\equiv0\pmod{3} and 0 otherwise; as σe+σe′∈{−2,0,2}\sigma_e+\sigma_{e'}\in\{-2,0,2\}, the condition is σe=−σe′\sigma_e=-\sigma_{e'}. So tA(K)t_A(K) is 2−∣A∣2^{-|A|} times the number of σ\sigma taking opposite values on any two edges that share a vertex, which is the number of proper 2-colourings of A∗A^*. A connected graph has two of them if it is bipartite, and none otherwise. □

The grid’s graph G∗G^* is K3,3K_{3,3}, which is bipartite, so tG(K)=2−5t_G(K)=2^{-5}; the prism contains triangles, so tP(K)=0t_P(K)=0. Collecting what we have, UU satisfies (U1)–(U3):

Proposition 3.3. Let VV be as in Theorem 3.1 with ∣V∣≤1|V|\leq1, let Ω=Ω0×Z/3Z\Omega=\Omega_0\times\mathbb{Z}/3\mathbb{Z} with the product of μ0\mu_0 and the uniform measure, and let U=V⊗KU=V\otimes K be as above. Then UU is symmetric, ∣U∣≤1|U|\leq1, UU has zero pair marginals, and

tG(U)=tG(V)32<0,tP(U)=0.t_G(U)=\frac{t_G(V)}{32}<0,\qquad t_P(U)=0.

Proof. UU is symmetric because VV and KK are, and ∣U∣≤1|U|\leq1 because ∣V∣≤1|V|\leq1 and ∣K∣≤1|K|\leq1. The rest follows from tA(U)=tA(V)tA(K)t_A(U)=t_A(V)t_A(K) and Theorem 3.2. □

Proof of Theorem 1.1, given that grids are abundant

Let UU be as in Theorem 3.3, and write a=−tG(U)>0a=-t_G(U)>0. The bookkeeping of § 2 gives, for g≥7g\geq7 and 0≤ε≤10\leq\varepsilon\leq1, the exact identity

Ig(1+εU)−Cg=D(1+εU)+∑k=46∑F∈EkaFεktF(U)−abgε6+Rg(ε),(4)I_g(1+\varepsilon U)-C_g=D(1+\varepsilon U)+\sum_{k=4}^{6}\sum_{F\in\mathcal{E}_k}a_F\varepsilon^k t_F(U)-a b_g\varepsilon^6+R_g(\varepsilon), \tag*{(4)}

where Rg(ε)R_g(\varepsilon) is the sum of aFε∣A∣tA(U)a_F\varepsilon^{|A|}t_A(U) over all F∈EkF\in\mathcal{E}_k with 4≤k<g4\leq k<g and all leafless A⊆E(F)A\subseteq E(F) with ∣A∣≥7|A|\geq7. Indeed, tF(1+εU)−1t_F(1+\varepsilon U)-1 is the sum of ε∣A∣tA(U)\varepsilon^{|A|}t_A(U) over nonempty leafless A⊆E(F)A\subseteq E(F). The sets A=E(F)A=E(F) with k≤6k\leq6 give the second term. By Theorem 2.1, proper leafless sets have at least six edges, and those with exactly six are copies of GG, each contributing ε6tG(U)\varepsilon^6t_G(U), or of PP, contributing nothing. Everything else has at least seven edges.

Every term except the grid term is small:

  • Since log⁡(1+u)≤u\log(1+u)\leq u, we have (1+u)log⁡(1+u)−u≤u2(1+u)\log(1+u)-u\leq u^2 for u≥−1u\geq-1. As ∫εU=0\int\varepsilon U=0, this gives

D(1+εU)=∫[(1+εU)log⁡(1+εU)−εU]≤ε2∫U2≤ε2.D(1+\varepsilon U)=\int\bigl[(1+\varepsilon U)\log(1+\varepsilon U)-\varepsilon U\bigr]\leq\varepsilon^2\int U^2\leq\varepsilon^2.
  • As ∣U∣≤1|U| \le1, every ∣tA(U)∣|t_A(U)| is at most 1. The second term in (4) is therefore at most C7ε4C_7\varepsilon^4 in absolute value, where C7=∑k=46∑F∈EkaFC_7 = \sum_{k=4}^{6}\sum_{F\in\mathcal{E}_k}a_F is an absolute constant. We never need to know its sign.

  • A configuration with k<gk<g edges has fewer than 2g2^g edge subsets, so ∣Rg(ε)∣≤2gCgε7|R_g(\varepsilon)| \le2^g C_g\varepsilon^7.

Hence

Ig(1+εU)−Cg≤(1+C7)ε2−abgε6+2gCgε7.(5)I_g(1+\varepsilon U)-C_g \le(1+C_7)\varepsilon^2-a b_g\varepsilon^6+2^g C_g\varepsilon^7. \tag*{(5)}

Everything now depends on how large bgb_g is compared with CgC_g.

Lemma 4.1. As g→∞g\to\infty,

Cg≤exp⁡(glog⁡g+O(g))andbg≥exp⁡(glog⁡g−O(g)).C_g \le\exp(g\log g+O(g)) \qquad\text{and}\qquad b_g \ge\exp(g\log g-O(g)).

The upper bound is a crude count of all possible configurations. The lower bound says that the weighted number of pairs (Erdős configuration, grid inside it) is as large as the weighted number of configurations, up to a factor eO(g)e^{O(g)}. This does not require grids to be typical: heuristically, only a polynomially small proportion of Erdős configurations contain a grid. But polynomial, and even exponential, losses are invisible on the scale glog⁡gg\log g.

Proof of Theorem 1.1, assuming Theorem 4.1. Take ε=g−g/5=exp⁡(−15glog⁡g)\varepsilon=g^{-g/5}=\exp(-\frac{1}{5}g\log g) in (5). Then

(1+C7)ε2=exp⁡(−25glog⁡g+O(1)),(1+C_7)\varepsilon^2=\exp\left(-\frac{2}{5}g\log g+O(1)\right),
abgε6≥exp⁡(−15glog⁡g−O(g)),a b_g\varepsilon^6\ge\exp\left(-\frac{1}{5}g\log g-O(g)\right),
2gCgε7≤exp⁡(−25glog⁡g+O(g)).2^g C_g\varepsilon^7\le\exp\left(-\frac{2}{5}g\log g+O(g)\right).

The middle term exceeds the other two by a factor exp⁡(15glog⁡g−O(g))→∞\exp(\frac{1}{5}g\log g-O(g))\to\infty, so Ig(1+εU)<CgI_g(1+\varepsilon U)<C_g for all sufficiently large gg. □

As anticipated in § 2, the exponent 15\frac{1}{5} has no special role: the same computation works for ε=g−θg\varepsilon=g^{-\theta g} with any θ∈(0,14)\theta\in(0,\frac{1}{4}).

Grids are abundant: proof of Lemma 4.1

Both bounds are statements about labelled configurations. By the orbit–stabiliser theorem, an Erdős kk-configuration FF has (k+2)!/∣Aut⁡(F)∣(k+2)!/|\operatorname{Aut}(F)| labelled copies on the vertex set [k+2][k+2]. Hence

∑F∈EkaF=6Lk(k+2)!and∑F∈EkaFNG(F)=6(k+2)!∑F′NG(F′),(6)\sum_{F\in\mathcal{E}_k}a_F=\frac{6L_k}{(k+2)!} \qquad\text{and}\qquad \sum_{F\in\mathcal{E}_k}a_F N_G(F)=\frac{6}{(k+2)!}\sum_{F'}N_G(F'), \tag*{(6)}

where LkL_k is the number of Erdős kk-configurations on [k+2][k+2], and F′F' ranges over them.

Upper bound

Upper bound. An Erdős kk-configuration on [k+2][k+2] is a set of kk triples from [k+2][k+2], so

Lk≤((k+23)k)≤(k+2)3kk!=exp⁡(2klog⁡k+O(k)).L_k\le\binom{\binom{k+2}{3}}{k}\le\frac{(k+2)^{3k}}{k!}=\exp(2k\log k+O(k)).

Since (k+2)!=exp⁡(klog⁡k+O(k))(k+2)!=\exp(k\log k+O(k)), (6) gives ∑F∈EkaF≤exp⁡(klog⁡k+O(k))\sum_{F\in\mathcal{E}_k}a_F\le\exp(k\log k+O(k)), and summing over k<gk<g gives Cg≤exp⁡(glog⁡g+O(g))C_g\le\exp(g\log g+O(g)).

Lower bound: completing a grid at random

Lower bound: completing a grid at random. Fix k=g−1k=g-1, and a copy of GG on nine of the vertices in [k+2][k+2]. By (6), bg≥6LkG/(k+2)!b_g\ge6L_k^G/(k+2)!, where LkGL_k^G is the number of Erdős kk-configurations on [k+2][k+2] that contain the fixed grid. So we need LkG≥exp⁡(2klog⁡k−O(k))L_k^G\ge\exp(2k\log k-O(k)): up to a factor eO(k)e^{O(k)}, as many configurations through a fixed grid as the upper bound allows for all configurations. We obtain them by completing the grid at random.

What should a completion look like? In an Erdős kk-configuration every vertex lies in at least two edges (as we saw in § 2), and the degrees sum to 3k=2(k+2)+(k−4)3k=2(k+2)+(k-4). So if all degrees are 2 or 3, exactly six vertices have degree 2. We build configurations of this kind using the so-called configuration model (see e.g. [6]). Besides the nine grid vertices, we let six vertices have degree 2, and the remaining k−13k-13 have degree 3; each grid vertex also gets degree 3, i.e. one incidence besides its two grid lines. Represent the missing incidences by stubs: one at each grid vertex, two at each degree-2 vertex and three at each other vertex, so

M=9+12+3(k−13)=3k−18M=9+12+3(k-13)=3k-18

in total. Add k−6k-6 new edges with three stubs each, again MM stubs in total, and match vertex stubs to edge stubs by a uniformly random bijection. Call the resulting multi-hypergraph FF. Every Erdős configuration on [k+2][k+2] which contains the fixed grid and has the prescribed degrees arises from exactly

(k−6)!⋅(3!)k−6⋅(2!)6⋅(3!)k−13(k-6)!\cdot(3!)^{k-6}\cdot(2!)^{6}\cdot(3!)^{k-13}

bijections: the new edges can be labelled in (k−6)!(k-6)! ways, and the stubs at each new edge and at each vertex can be ordered arbitrarily. Therefore

LkG≥P[F∈Ek]⋅(3k−18)!(k−6)! 26 62k−19,L_k^G \ge\mathbb{P}[F\in\mathcal{E}_k]\cdot\frac{(3k-18)!}{(k-6)!\,2^6\,6^{2k-19}},

and by Stirling’s formula the fraction is exp⁡(3klog⁡k−klog⁡k+O(k))=exp⁡(2klog⁡k+O(k))\exp(3k\log k-k\log k+O(k))=\exp(2k\log k+O(k)). So the lower bound in Theorem 4.1 follows from the next proposition. (Any bound of the form P[F∈Ek]≥e−O(k)\mathbb{P}[F\in\mathcal{E}_k]\ge e^{-O(k)} would do, but the natural proof gives a constant.)

Proposition 5.1. P[F∈Ek]→e−6\mathbb{P}[F\in\mathcal{E}_k]\to e^{-6} as k→∞k\to\infty.

The multi-hypergraph FF is an Erdős kk-configuration if and only if

  1. FF is linear, and

  2. no set SS of edges with 3≤∣S∣≤k−13\le|S|\le k-1 spans at most ∣S∣+2|S|+2 vertices.

(Linearity rules out repeated vertices in an edge and repeated edges, and it is the case ∣S∣=2|S|=2 of the definition; FF spans all k+2k+2 vertices because each has degree at least 2.) Condition (i) is local, and it fails with probability bounded away from zero: it is the source of the constant e−6e^{-6}. Condition (ii) is global, but it fails only with probability O(1/k)O(1/k).

Linearity

Linearity. Think of FF through its incidence graph: the bipartite multigraph with the vertices of FF on one side, the edges of FF on the other, and one link for each incidence. FF is linear exactly when this graph has no cycle of length 2 (a vertex matched twice to the same edge) and no cycle of length 4 (two edges sharing two vertices).

Short cycles meeting the grid are rare. The grid itself has none. A grid vertex has a single stub, so it lies on no 2-cycle, and a 4-cycle through it must consist of a grid line and a new edge containing two vertices of that line. There are 18 pairs of vertices on a common grid line, and the stubs of a given pair go to the same new edge with probability O(1/k)O(1/k).

The remaining short cycles are formed by stubs alone, and all but fifteen vertices have three stubs. Let XX and YY be the numbers of 2-cycles and 4-cycles formed by stub pairs. A 2-cycle is specified by a vertex, a new edge, and two stub pairs between them; a 4-cycle by two vertices, two new edges, and four stub pairs forming the cycle. A given set of tt stub pairs is present with probability 1/(M)t=(1+O(1/k))(3k)−t1/(M)_t=(1+O(1/k))(3k)^{-t} for bounded tt, where (M)t=M(M−1)⋯(M−t+1)(M)_t=M(M-1)\cdots(M-t+1). Since almost every vertex has three stubs,

EX=(1+O(1/k)) k⋅k⋅3⋅3⋅2(3k)2→2,EY=(1+O(1/k))(k2)(3⋅2)4(3k)4→4.\mathbb{E}X=(1+O(1/k))\,k\cdot k\cdot\frac{3\cdot3\cdot2}{(3k)^2}\to2,\qquad\mathbb{E}Y=(1+O(1/k))\binom{k}{2}\frac{(3\cdot2)^4}{(3k)^4}\to4.

The method of moments upgrades this to a Poisson limit. For fixed ii and jj, the factorial moment E[(X)i(Y)j]\mathbb{E}[(X)_i(Y)_j] counts ordered tuples of ii distinct 2-cycles and jj distinct 4-cycles that are all present. Tuples of pairwise disjoint cycles contribute 2i4j+o(1)2^i4^j+o(1), by the computation above. In every other tuple, the union of the cycles has a component containing two distinct cycles, and so has more links than nodes. Since each node can be chosen in O(k)O(k) ways and each link costs a factor O(1/k)O(1/k) in probability, these tuples contribute O(1/k)O(1/k). Hence (X,Y)(X,Y) converges in distribution to a pair of independent Poisson random variables with means 2 and 4, and

P[F is linear]=P[X=Y=0]+O(1/k)→e−2e−4=e−6.\mathbb{P}[F\text{ is linear}]=\mathbb{P}[X=Y=0]+O(1/k)\to e^{-2}e^{-4}=e^{-6}.

No dense edge sets

No dense edge sets. Call a set SS of edges of FF bad if 3≤∣S∣≤k−13\le|S|\le k-1 and SS spans at most ∣S∣+2|S|+2 vertices. We show that the expected number of bad sets is O(1/k)O(1/k), handling sets with at most k/2k/2 edges directly and larger ones through their complements. In both cases a bad set forces all stubs of some rr new edges into a prescribed set of roughly 3r3r stubs, at a cost of order k−3rk^{-3r}, while the sets involved can be chosen in about k2rk^{2r} ways. The remaining bounded powers of kk are controlled by the condition ∣S∣≥3|S|\ge3 and by the fact that the grid is itself sparse.

Small sets. Suppose SS is bad and s=∣S∣≤k/2s=|S|\le k/2. Let AA be the set of grid lines in SS, say pp rows and qq columns, h=p+qh=p+q in total, and let the other r=s−hr=s-h edges of SS be new. Choose a set YY of exactly s+2s+2 vertices containing every vertex of SS. Then YY contains the 3h−pq3h-pq vertices covered by AA, and all 3r3r stubs of the new edges in SS are matched to stubs at vertices of YY.

The grid is sparse in the same sense as an Erdős configuration: one grid line covers 3 vertices, and h≥2h\ge2 grid lines cover 3h−pq≥h+33h-pq\ge h+3 (one checks the few cases). Consequently r≥1r\ge1; more precisely r≥3r \ge3 if h=0h = 0 (as s≥3s \ge3), r≥2r \ge2 if h=1h = 1, and r≥1r \ge1 if h≥2h \ge2. Moreover, the number of vertices of YY not forced by AA is s+2−(3h−pq)=r+cs + 2 - (3h - pq) = r + c, where c=2c = 2 if h=0h = 0, c=0c = 0 if h=1h = 1, and c≤−1c \le-1 if h≥2h \ge2.

Now fix AA and rr. The new edges of SS can be chosen in at most (kr)\binom{k}{r} ways and the rest of YY in at most (k+2r+c)\binom{k+2}{r+c} ways, and the 3r3r stubs land among the at most 3(s+2)3(s + 2) stubs at YY with probability at most (3s+6)3r/(M)3r(3s + 6)^{3r}/(M)_{3r}. For bounded rr this gives O(kr⋅kr+c⋅k−3r)=O(kc−r)O(k^r \cdot k^{r+c} \cdot k^{-3r}) = O(k^{c-r}), and c−r≤−1c-r \le-1 in all three cases.

Large sets. Suppose SS is bad and ∣S∣>k/2|S| > k/2, and let TT be its complement, with m=∣T∣<k/2m = |T| < k/2. Since SS spans at most ∣S∣+2=k+2−m|S| + 2 = k + 2 - m vertices, at least mm vertices lie in no edge of SS, so all their edges are in TT. Choose a set ZZ of exactly mm such vertices. Let TT contain h=p+qh = p + q grid lines (pp rows and qq columns) and r=m−hr = m-h new edges. A grid vertex can belong to ZZ only if both grid lines through it are in TT, so ZZ contains at most pq≤2hpq \le2h grid vertices. If ZZ contains jj grid vertices and dd vertices of degree 22, then the vertices of ZZ carry 3m−2j−d3m - 2j - d stubs, all of which must be matched to the 3r3r stubs of the new edges in TT. In particular r≥1r \ge1.

Fix the grid lines in TT, and jj, dd and rr. The new edges of TT can be chosen in at most (kr)\binom{k}{r} ways and ZZ in O((km−j−d))O\left(\binom{k}{m-j-d}\right) ways, and the stub condition has probability (3r)3m−2j−d/(M)3m−2j−d(3r)_{3m-2j-d}/(M)_{3m-2j-d}. For bounded rr this gives O(kr+(m−j−d)−(3m−2j−d))=O(kj−2h−r)O(k^{r+(m-j-d)-(3m-2j-d)}) = O(k^{j-2h-r}), which is O(k−r)=O(k−1)O(k^{-r}) = O(k^{-1}) because j≤2hj \le2h.

Summing over $r. The estimates above are for fixed rr; it remains to show that large rr contribute little. In both cases the bound for a given r≤k/2r \le k/2 is at most kO(1)(kr)2/(3k3r)k^{O(1)} \binom{k}{r}^{2}/\binom{3k}{3r}, with an absolute implied constant. To see this, write (y)x/(M)x=(yx)/(Mx)(y)_x/(M)_x = \binom{y}{x}/\binom{M}{x}. In both cases x≤yx \le y (otherwise the probability is zero) and x,yx,y differ from $3r$ by at most 2424, so (yx)≤(3k)24\binom{y}{x} \le(3k)^{24} and (Mx)≥M−24(M3r)\binom{M}{x} \ge M^{-24}\binom{M}{3r}; moreover (M3r)≥3−18k(M3r)\binom{M}{3r} \ge3^{-18k}\binom{M}{3r} for r≤k/2r \le k/2 and kk large, and the second binomial coefficient in each count is at most kO(1)(kr)k^{O(1)}\binom{k}{r}, because its lower index differs from rr by a bounded amount and r≤k/2r \le k/2.

Heuristically, choosing rr edges and about rr vertices is worth (kr)2\binom{k}{r}^{2}, while forcing 3r3r stubs into a set of about 3r3r stubs costs 1/(3k3r)1/\binom{3k}{3r}. With η(x)=−xlog⁡x−(1−x)log⁡(1−x)\eta(x) = -x \log x - (1-x)\log(1-x), the standard estimates (kr)≤ekη(r/k)\binom{k}{r} \le e^{k\eta(r/k)} and (3k3r)≥e3kη(r/k)/(3k+1)\binom{3k}{3r} \ge e^{3k\eta(r/k)}/(3k+1) make this precise:

(kr)2/(3k3r)≤(3k+1)e−kη(r/k)≤(3k+1)(rk)r,\binom{k}{r}^{2}/\binom{3k}{3r} \le(3k+1)e^{-k\eta(r/k)} \le(3k+1)\left(\frac{r}{k}\right)^r,

using η(x)≥xlog⁡(1/x)\eta(x) \ge x\log(1/x). So the bound for each r≤k/2r \le k/2 is at most kc0(r/k)rk^{c_0}(r/k)^r for an absolute constant c0c_0. For r0≤r≤kr_0 \le r \le\sqrt{k} this is at most kc0−r/2k^{c_0-r/2}, and for k≤r≤k/2\sqrt{k} \le r \le k/2 it is at most kc02−kk^{c_0}2^{-\sqrt{k}}. Choosing r0≥2c0+4r_0 \ge2c_0 + 4, the terms with r≥r0r \ge r_0 add up to O(k−2)O(k^{-2}), while the finitely many r<r0r < r_0 contribute O(1/k)O(1/k) by the fixed-rr estimates. Since there are boundedly many choices of the grid lines involved and of jj and dd, the expected number of bad sets is O(1/k)O(1/k).

Proof of Theorem 5.1. By the two estimates, P[F∈Ek]=P[F is linear]−O(1/k)→e−6\mathbb{P}[F \in\mathcal{E}_k] = \mathbb{P}[F\text{ is linear}] - O(1/k) \to e^{-6}.

This completes the proof of Theorem 4.1, and with it the proof of Theorem 1.1.

References

Institute of Science and Technology Austria (ISTA).

Email address: [email protected]

Department of Mathematics, University of Chicago.

Email address: [email protected]

References

  1. [1]M. Delcourt and L. Postle, Proof of the high girth existence conjecture via refined absorption, arXiv preprint arXiv:2402.17856 (2024).arxiv.org/abs/2402.17856
  2. [2]S. Glock, D. Kühn, A. Lo, and D. Osthus, On a conjecture of Erdős on locally sparse Steiner triple systems, Combinatorica 40 (2020), no. 3, 363–403.DOI
  3. [3]M. Kwan and H. T. Pham, Nonlinear lower-tail deviations at criticality, arXiv preprint arXiv:2610.10233 (2026).arxiv.org/abs/2610.10233
  4. [4]M. Kwan, A. Sah, M. Sawhney, and M. Simkin, High-girth Steiner triple systems, Ann. of Math. (2) 200 (2024), no. 3, 1059–1156.arxiv.org/abs/2201.04554
  5. [5]A. Sidorenko, On positive hypergraphs, European J. Combin. 106 (2022), Paper No. 103574, 5.
  6. [6]N. C. Wormald, Models of random regular graphs, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298.

Paper details

vlnc:W_wgg3zj5e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 12

downloads · 2

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

  • Mathematics

Anthropic Claude Opus 5.5, OpenAI ChatGPT 6 Pro

View statement
Looking for related papers…
Contents