betaFeedback

WorksMathematics

A Torsion-Free Group Algebra That Is Not Directly Finite

Abstract

We construct a finitely presented torsion-free counterexample to Kaplansky's direct finiteness conjecture over the field of two elements. The group admits a finite two-dimensional classifying complex.

Introduction

A unital ring RR is directly finite if ab=1ab = 1 implies ba=1ba = 1 for all a,b∈Ra,b \in R. For a field KK and a group GG, the group algebra K[G]K[G] consists of finite formal sums of elements of GG with coefficients in KK, with multiplication extending the group operation bilinearly. Kaplansky’s direct finiteness conjecture asserts that every such group algebra is directly finite. We prove that the implication can fail even when the field is finite and the group is finitely presented and torsion-free. A classifying complex for GG is a connected CW complex with fundamental group GG and contractible universal cover.

Theorem 1.1. There exist a finitely presented torsion-free group GG and elements a,b,c∈F2[G]a,b,c \in\mathbb{F}_2[G] such that

ab=1,ac=0,c≠0.ab = 1,\qquad ac = 0,\qquad c \ne0.

Consequently ba≠1ba \ne1. The group GG admits a finite two-dimensional classifying complex.

The auxiliary element cc certifies failure of the reverse identity: if ba=1ba = 1, then c=(ba)c=b(ac)=0c = (ba)c = b(ac) = 0.

Kaplansky’s formulation separates the characteristic-zero theorem from the positive-characteristic question [8]. In characteristic zero, group algebras are directly finite for every group. The operator-algebra argument also applies to matrix rings; Montgomery gave a concise C∗\mathrm{C}^*-algebra proof [10]. A ring whose matrix rings of every finite size are directly finite is called stably finite.

In arbitrary characteristic, Ara, O’Meara, and Perera proved stable finiteness for group algebras of free-by-amenable groups over division rings [1]. Elek and Szabó extended the conclusion to sofic groups [5], a class defined by finite approximate permutation actions. Their theorem implies that the group in Theorem 1.1 is not sofic. A complementary approach studies the finite cancellation patterns forced by a one-sided inverse. Dykema, Heister, and Juschenko organized these patterns into universal groups and established direct finiteness for several small support pairs over F2\mathbb{F}_2 [4].

Two companion manuscripts are especially relevant. A separate construction gives a scalar counterexample over a finite field of characteristic two for a finitely presented group with odd-order torsion [12], Theorem 1.1. Theorem 1.1 uses the prime field F2\mathbb{F}_2 and a torsion-free group. Its method develops the graph and cone construction of A Torsion-Free Group Algebra with Zero Divisors [13]. That manuscript supplies the parity mechanism for a zero product and the arrangement-exclusion strategy. We adapt those arguments to produce a one-sided inverse and reproduce the estimates and topology needed here.

Graphical presentations relate coincidences of labeled paths to geometric properties of quotient groups, as in Gromov’s random graphical constructions [6] and Ollivier’s small-cancellation theorem [11]. Bereznyuk’s spherical-diagram criterion for graphical asphericity distinguishes coincident graph lifts from genuinely different ones [2]. The same distinction is essential here: pairings of two occurrences of the same graph edge are removed by cone surgeries. We prove the required asphericity and root protection directly in Section 6.

The construction and its main estimates

The group is obtained from a bouquet of circles by attaching cones on finite labeled graphs. A cone kills every closed path in its graph, so a vertex in a chosen component determines a group element by reading a path from a fixed root to that vertex. The desired algebra elements are finite sums of these path labels and their inverses.

Two graphs are used. A common outgoing label allows a simultaneous step in both coordinates of their vertex products. The group element contributed to the corresponding algebra product is constant along such a step. If every vertex of a simultaneous-step component has odd degree, the component has even cardinality and its contributions cancel over F2\mathbb{F}_2. A single even-degree exception instead leaves one surviving contribution. We prescribe the outgoing label sets so that the first graph paired with itself has exactly this exception, while the first graph paired with the second has none.

The change to the parity construction in [13] is to produce product 1 as well as product 0. Seven additional labels, organized by complements of lines in the Fano plane, create the required exception while keeping every inverse-label incidence count balanced. This changes the random model, and we establish its counting estimates directly.

The main difficulty is to make the cone attachments aspherical while ensuring that a path from a root to a different graph vertex has nontrivial image in the group. Both conclusions follow by excluding certain planar pairings of graph paths. The argument has two parts. First, a weighted estimate rules out bounded collections of paths with a small proportion of unpaired positions. Repeated traversal of a graph edge is the main counting obstacle: two compared path words need not impose two sets of random edge conditions. We organize the count by the number of times each edge is used, and choose subdivisions that nearly agree under all the comparisons. This makes the decay of word weights available despite repeated traversals. The permitted unpaired proportion is fixed before the bounds on the number and length of paths. Second, a planar separator extracts one of these bounded collections from any spherical arrangement, however large. The order of these parameter choices is what allows a local counting estimate to exclude all arrangements.

We give the graph criterion and the parity calculation in Section 2. Section 3 constructs the vertex types and proves the word, girth, and diameter estimates. Section 4 proves the bounded-path estimate, and Section 5 carries out the planar extraction. Section 6 proves the topological criterion by cone surgeries. Section 7 then assembles these conclusions.

Labeled graphs and the parity criterion

The algebraic part of the construction is a parity calculation on finite graphs. We first isolate this calculation from the geometric work needed to ensure that the resulting group is torsion-free and that a specified coefficient does not vanish. The use of immersed graphs and their cones follows the construction in [12], Proposition 5.1 and Section 6.

A signed alphabet is a finite set TT with a fixed-point-free involution t↦t‾t \mapsto\overline{t}. Let FF be the rose with one vertex ∗\ast and one geometric edge for each pair {t,t‾}\{t,\overline{t}\}; its two orientations carry the labels tt and t‾\overline{t}. A TT-labeled graph Γ\Gamma has a label on every oriented edge, with opposite orientations carrying inverse labels. It therefore has a label map Γ→F\Gamma\to F taking each edge homeomorphically onto the appropriate edge of the rose. The map is an immersion if the labels on the edges leaving any one vertex are distinct. Write Sx⊆TS_x \subseteq T for these outgoing labels. For t∈Sxt \in S_x, denote by x⋅tx \cdot t the endpoint of the unique edge leaving xx with label tt.

The length of an edge path is its number of edge traversals, counted with multiplicity. A path is immersed if it has no consecutive edge and reverse edge. A closed path is cyclically immersed if this also holds at the closing turn. For a graph immersed in FF, these conditions say precisely that the label word is freely reduced, or cyclically reduced, respectively. We multiply labels in the order in which a path traverses its edges.

Let ΓA\Gamma_A and ΓB\Gamma_B be finite graphs immersed in FF, with vertex sets AA and BB, and choose roots xA∈Ax_A \in A and xB∈Bx_B \in B. Put Γ=ΓA⊔ΓB\Gamma= \Gamma_A \sqcup\Gamma_B. For each connected component Λ\Lambda of Γ\Gamma, let KΛK_\Lambda be its abstract cone, and form

X=F∪Λ∈π0(Γ)KΛ,G=π1(X,∗).(1)X = F \cup_{\Lambda\in\pi_0(\Gamma)} K_\Lambda,\qquad G = \pi_1(X,\ast). \tag*{(1)}

Here the base of each cone is attached by its label map. In particular, the cone need not embed in XX. This is a finite CW complex of dimension at most two. Every closed path in Γ\Gamma has trivial label in GG, because it bounds in its cone.

Let A′⊆AA' \subseteq A and B′⊆BB' \subseteq B be the vertex sets of the components containing the respective roots. For x∈A′x \in A', let gxg_x be the label in GG of any path from xAx_A to xx; define hyh_y for y∈B′y \in B' in the same way. These elements are independent of the chosen paths: the concatenation of one such path with the reverse of another is a closed path in the same component. Thus

gxA=hxB=1,gx⋅t=gxt,hy⋅t=hyt,g_{x_A}=h_{x_B}=1,\qquad g_{x\cdot t}=g_xt,\qquad h_{y\cdot t}=h_yt,

whenever the indicated step exists, where a letter also denotes its image in GG.

Proposition 2.1 (Parity criterion). Let ΓA,ΓB\Gamma_A,\Gamma_B be finite loopless graphs immersed in the same rose, with roots and cone group as above. Suppose that

∣Sx∩Sx′∣=1(mod2)(x,x′∈A′, (x,x′)≠(xA,xA)),\lvert S_x \cap S_{x'}\rvert= 1 \pmod2 \qquad(x,x' \in A',\ (x,x') \ne(x_A,x_A)),
∣Sx∣=0(mod2),\lvert S_x\rvert= 0 \pmod2,
∣Sx∩Sy∣=1(mod2)(x∈A′, y∈B′).(2)\lvert S_x \cap S_y\rvert= 1 \pmod2 \qquad(x \in A',\ y \in B'). \tag*{(2)}

Suppose also that the roots are protected in the following sense:

if a path in Γ starts at xA or xB and ends\text{if a path in }\Gamma\text{ starts at }x_A\text{ or }x_B\text{ and ends}
at a different vertex, its label is nontrivial in G.(3)\text{at a different vertex, its label is nontrivial in }G. \tag*{(3)}

Then the finite scalar sums

a=∑x∈A′gx,b=∑x∈A′gx−1,c=∑y∈B′hy−1in F2[G](4)a = \sum_{x \in A'} g_x,\qquad b = \sum_{x \in A'} g_x^{-1},\qquad c = \sum_{y \in B'} h_y^{-1}\quad\text{in }\mathbb{F}_2[G] \tag*{(4)}

satisfy ab=1ab = 1, ac=0ac = 0, and c≠0c \ne0. Consequently ba≠1ba \ne1.

Proof. On A′×A′A' \times A' form the simultaneous-step graph: for every common outgoing label tt at xx and x′x', join (x,x′)(x,x') to (x⋅t,x′⋅t)(x \cdot t,x' \cdot t). The step with label t‾\overline{t} at the latter vertex is the reverse of this edge, rather than a second edge. Different steps with the same pair of endpoints remain distinct edges. The graph is loopless because the factor graphs are loopless, and its degree at (x,x′)(x,x') is exactly ∣Sx∩Sx′∣|S_x \cap S_{x'}|.

The group element contributed to abab by a vertex is constant on each component of this graph. Indeed, by (2.2),

gx⋅tgx′⋅t−1=(gxt)(gx′t)−1=gxgx′−1.g_{x \cdot t}g_{x' \cdot t}^{-1} = (g_xt)(g_{x'}t)^{-1} = g_xg_{x'}^{-1}.

In every finite graph the number of vertices of odd degree is even, because the sum of the degrees is twice the number of edges. By (2), every component that does not contain (xA,xA)(x_A,x_A) therefore has an even number of vertices. Its contributions to abab cancel in characteristic two. In the component containing (xA,xA)(x_A,x_A), that vertex is the unique vertex of even degree, so the component has odd cardinality. Its constant contribution is gxAgxA−1=1g_{x_A}g_{x_A}^{-1} = 1. This proves ab=1ab = 1.

Apply the same construction to A′×B′A' \times B'. Its degree at (x,y)(x,y) is ∣Sx∩Sy∣|S_x \cap S_y|, which is always odd. Hence every component has even cardinality. The contribution gxhy−1g_xh_y^{-1} to acac is constant along each simultaneous step by the same calculation, so ac=0ac = 0.

Finally, hxB=1h_{x_B} = 1, and (3) gives hy≠1h_y \ne1 for every y∈B′∖{xB}y \in B' \setminus\{x_B\}. Thus the coefficient of the identity in cc is exactly one, and c≠0c \ne0. If ba=1ba = 1, associativity would give c=(ba)c=b(ac)=0c = (ba)c = b(ac) = 0, a contradiction.

Only protection of xBx_B is needed for the last coefficient calculation. We retain the symmetric condition (3) because the geometric argument will establish it for both roots. The remaining task is to construct finite immersed graphs satisfying (2) whose cone complex is aspherical and whose roots satisfy (3).

Types and random matchings

We construct the outgoing label sets first, so that every choice of edges has the parity properties needed for the algebraic argument. We then choose the edges by random matchings. The estimates in this section show that we may condition on logarithmic girth while retaining useful bounds for prescribed edges, and that the resulting components have logarithmic diameter. The construction and the use of conditioned matchings adapt the method of [13], Section “Prescribed types and random matchings”; the label counts and estimates below are for the types used here.

Prescribing the outgoing labels

Fix

q=128,v=q2+q+1=16513,p=q+1v.q = 128,\qquad v = q^2 + q + 1 = 16513,\qquad p = \frac{q+1}{v}.

Let P\mathcal{P} and L\mathcal{L} be the points and lines of the projective plane over Fq\mathbb{F}_q. Concretely, these are the one-dimensional and two-dimensional subspaces of Fq3\mathbb{F}_q^3, with incidence given by containment.

Counting nonzero vectors gives vv points, and duality gives vv lines. Every line contains q+1q+1 points, and every point lies on q+1q+1 lines. Two distinct points span a unique line, and two distinct lines intersect in exactly one point.

Adjoin a set E\mathcal{E} of seven extra letters to P\mathcal{P}, and put T=P⊔ET=\mathcal{P}\sqcup\mathcal{E}. Pair each extra letter with a distinct ordinary letter. Since v−7v-7 is even, the remaining ordinary letters can be paired among themselves. These pairs define the fixed-point-free involution t↦tˉt\mapsto\bar{t} on TT. As before, FF is the rose with one edge for each inverse pair.

Identify E\mathcal{E} with the seven points of the projective plane over F2\mathbb{F}_2, and let D\mathcal{D} consist of the complements of its seven lines. Each D∈DD\in\mathcal{D} has four elements, and distinct members of D\mathcal{D} intersect in two elements. Each extra letter belongs to four members of D\mathcal{D}: three Fano lines contain the letter and four do not. Each pair of distinct extra letters belongs to two members of D\mathcal{D}, since the number of Fano lines containing at least one of them is 3+3−1=53+3-1=5.

Let mm tend to infinity through positive integers congruent to 11 modulo 44, and set n=vmn=vm. All asymptotic statements below use this sequence. Partition sets AA and BB into classes indexed by L\mathcal{L}, with mm vertices in each class of AA and m−1m-1 vertices in each class of BB. Thus

∣A∣=n,∣B∣=n−v.|A|=n,\qquad|B|=n-v.

The ordinary part of the outgoing label set SxS_x at a vertex xx is its indexing line. Choose a distinguished vertex xA∈Ax_A\in A and give it all seven extra letters. For every D∈DD\in\mathcal{D}, prescribe extra part exactly DD at

am=(q+1)m−14vertices of A,bm=(q+1)(m−1)4vertices of B.(5)a_m=\frac{(q+1)m-1}{4}\quad\text{vertices of }A,\qquad b_m=\frac{(q+1)(m-1)}{4}\quad\text{vertices of }B. \tag*{(5)}

These are integers because q+1≡m≡1(mod4)q+1\equiv m\equiv1\pmod{4}. Every remaining vertex has empty extra part.

For each DD, distribute its prescribed vertices among the vv line classes with counts differing by at most one. These distributions can be realized simultaneously on disjoint vertices. Indeed, in each line class the total demand in AA, including xAx_A if applicable, is at most 7⌈am/v⌉+17\lceil a_m/v\rceil+1, and in BB it is at most 7⌈bm/v⌉7\lceil b_m/v\rceil. Both bounds are

7(q+1)4vm+O(1),\frac{7(q+1)}{4v}m+O(1),

whose coefficient of mm is strictly less than one. For all sufficiently large mm, each bound is smaller than m−1m-1. Fix one such assignment of the sets SxS_x, and also fix any root xB∈Bx_B\in B, before choosing edges.

Proposition 3.1 (Balanced types and parity). For all sufficiently large m≡1(mod4)m\equiv1\pmod{4}, the prescribed sets Sx⊆TS_x\subseteq T, x∈A⊔Bx\in A\sqcup B, satisfy the following identities. For every Y∈{A,B}Y\in\{A,B\} and t∈Tt\in T,

∣{x∈Y:t∈Sx}∣=∣Y∣p.\left|\{x\in Y:t\in S_x\}\right|=|Y|p.

Their intersection cardinalities satisfy

∣Sx∩Sx′∣=1(mod2)(x,x′∈A, (x,x′)≠(xA,xA)),∣SxA∣=0(mod2),∣Sx∩Sy∣=1(mod2)(x∈A, y∈B).(6)\begin{aligned} |S_x\cap S_{x'}|&=1\pmod{2} &&(x,x'\in A,\ (x,x')\ne(x_A,x_A)),\\ |S_{x_A}|&=0\pmod{2},\\ |S_x\cap S_y|&=1\pmod{2} &&(x\in A,\ y\in B). \tag*{(6)} \end{aligned}

Moreover, 129≤∣Sx∣≤136129\le|S_x|\le136 at every vertex.

Proof. An ordinary letter lies on q+1q+1 lines, so occurs at exactly (q+1)m=np(q+1)m=np vertices of AA and (q+1)(m−1)=(n−v)p(q+1)(m-1)=(n-v)p vertices of BB. An extra letter belongs to four members of D\mathcal{D}, and therefore occurs 4am+1=(q+1)m4a_m+1=(q+1)m times in AA and 4bm=(q+1)(m−1)4b_m=(q+1)(m-1) times in BB. This proves (3.2).

The intersection of two ordinary parts has size q+1=129q+1=129 when the lines agree and size one otherwise. For the extra parts, all intersections have even size except the intersection of the full seven-element set with itself. In fact, the possible even sizes are zero, two, and four. Only xAx_A has the full extra part, giving exactly the exception in (6). Finally, the possible sizes of SxS_x are 129, 133, and 136.

For Y∈{A,B}Y\in\{A,B\}, write Yt={x∈Y:t∈Sx}Y_t=\{x\in Y:t\in S_x\}. For each inverse pair, choose a bijection Yt→YtˉY_t\to Y_{\bar{t}}. A matched pair (x,y)(x,y) gives one undirected edge, oriented from xx to yy with label tt and in the reverse direction with label tˉ\bar{t}. Overlap between YtY_t and YtˉY_{\bar{t}} is allowed, so loops may occur at this stage. More precisely, a match joins the label slots (x,t)(x,t) and (y,tˉ)(y,\bar{t}); these remain distinct when x=yx=y. Denote the resulting graphs by ΓA\Gamma_A and ΓB\Gamma_B, and put Γ=ΓA⊔ΓB\Gamma=\Gamma_A\sqcup\Gamma_B. Every outgoing label at a vertex occurs exactly once, so the maps to FF are immersions. Degrees count half-edges, including both half-edges of a loop, and are bounded by

129≤deg⁡(x)≤d∗:=136.(7)129\leq\deg(x)\leq d_*:=136. \tag*{(7)}

Turn frequencies and decay of word weights

At an interior vertex of a path with consecutive labels t,ut,u, the outgoing labels used by the path are tˉ,u\bar{t},u. For a reduced turn, meaning u≠tˉu\ne\bar{t}, define

w(t,u)={(q+1)−1,tˉ,u∈P,p,one of tˉ,u is in P and the other is in E,1/2,tˉ,u∈E.w(t,tˉ)=0.(8)w(t,u)= \begin{cases} (q+1)^{-1}, & \bar{t},u\in\mathcal{P},\\ p, & \text{one of }\bar{t},u\text{ is in }\mathcal{P}\text{ and the other is in }\mathcal{E},\\ 1/2, & \bar{t},u\in\mathcal{E}. \end{cases} \qquad w(t,\bar{t})=0. \tag*{(8)}

For either Y=AY=A or Y=BY=B, uniformly over reduced turns,

∣{x∈Y:tˉ,u∈Sx}∣=np w(t,u)+O(1).(9)\left|\{x\in Y:\bar{t},u\in S_x\}\right|=np\,w(t,u)+O(1). \tag*{(9)}

Here and below constants in O(1)O(1) do not depend on mm. To verify the formula, two distinct ordinary letters occur together on just one line, giving mm or m−1m-1 choices. An extra letter occurs in each line class 4am/v+O(1)=pm+O(1)4a_m/v+O(1)=pm+O(1) times in AA, including the possible distinguished vertex in the error, and 4bm/v+O(1)=p(m−1)+O(1)4b_m/v+O(1)=p(m-1)+O(1) times in BB. Summing over the q+1q+1 lines containing a specified ordinary letter gives np2+O(1)np^2+O(1). Finally, two distinct extra letters occur together 2am+1=np/2+1/22a_m+1=np/2+1/2 times in AA and 2bm=(n−v)p/22b_m=(n-v)p/2 times in BB. These are precisely the three cases of (9).

For a word W=t1⋯thW=t_1\cdots t_h of positive length, put

P(W)=∏i=1h−1w(ti,ti+1),P(W)=\prod_{i=1}^{h-1}w(t_i,t_{i+1}),

with the empty product equal to one. This weight is positive exactly when the word is reduced. Since the rule in (8) is symmetric in tˉ,u\bar{t},u, it also gives

w(t,u)=w(uˉ,tˉ),P(W−1)=P(W),W−1=tˉh⋯tˉ1.w(t,u)=w(\bar{u},\bar{t}),\qquad P(W^{-1})=P(W),\qquad W^{-1}=\bar{t}_h\cdots\bar{t}_1.

Thus reversing the orientation of a path does not change its weight. The square of this weight has summable total mass in long word lengths, as the next estimate shows.

Lemma 3.2 (Decay of word weights). There is a constant δ>0\delta> 0, depending only on the prescribed alphabet and weights, such that for all sufficiently large integers hh,

∑W∈ThP(W)2≤exp⁡(−2δh).(10)\sum_{W \in\mathcal{T}^{h}} P(W)^2 \le\exp(-2\delta h). \tag*{(10)}

Proof. Let MM be the nonnegative matrix with entries Mt,u=w(t,u)2M_{t,u} = w(t,u)^2. Define a positive vector ff on T\mathcal{T} by

f(t)={4,tˉ∈E,1,tˉ∈P.f(t) = \begin{cases} 4, & \bar{t} \in\mathcal{E},\\ 1, & \bar{t} \in\mathcal{P}. \end{cases}

Exactly seven ordinary letters have value four under ff; all extra letters have value one. If tˉ\bar{t} is ordinary, there are v−1=q(q+1)v - 1 = q(q + 1) allowed ordinary successors and seven extra successors. Allowing all seven of the exceptional ordinary letters among those successors gives

(Mf)(t)≤qq+1+7p2+21(q+1)2<1=f(t).(Mf)(t) \le\frac{q}{q+1} + 7p^2 + \frac{21}{(q+1)^2} < 1 = f(t).

If tˉ\bar{t} is extra, the six allowed extra successors contribute 6/46/4, and the ordinary successors contribute (v+21)p2(v + 21)p^2. Thus

(Mf)(t)≤64+(v+21)p2<4=f(t).(Mf)(t) \le\frac{6}{4} + (v + 21)p^2 < 4 = f(t).

Both strict inequalities hold for q=128q = 128. Consequently a fixed λ<1\lambda< 1 satisfies Mf≤λfMf \le\lambda f coordinatewise. Writing 11 for the all-ones vector and using 1≤f≤411 \le f \le4\mathbf{1}, we obtain

∑W∈ThP(W)2=1TMh−11≤4∣T∣λh−1.\sum_{W \in\mathcal{T}^{h}} P(W)^2 = \mathbf{1}^{\mathsf{T}}M^{h-1}\mathbf{1} \le4|\mathcal{T}|\lambda^{h-1}.

For example, δ=−14log⁡λ>0\delta= -\frac{1}{4}\log\lambda> 0 makes the last quantity at most exp⁡(−2δh)\exp(-2\delta h) for all sufficiently large hh.

Conditioning on large girth

Initially choose all the bijections independently and uniformly, and write P\mathbb{P} for this probability law. Fix c0>0c_0 > 0 so small that

c0log⁡(2∣T∣/p)<1,2c0log⁡d∗<1,L=⌊c0log⁡n⌋.(11)c_0 \log(2|\mathcal{T}|/p) < 1,\qquad2c_0 \log d_* < 1,\qquad L = \lfloor c_0 \log n \rfloor. \tag*{(11)}

Girth is the length of a shortest simple cycle; loops and pairs of parallel edges count as cycles of lengths one and two. Let GLG_L be the event that Γ\Gamma has girth at least LL. We first prove that this event is nonempty for all sufficiently large nn, so that the conditioned law

PL(⋅)=P(⋅∣GL)\mathbb{P}_L(\mathord{\cdot}) = \mathbb{P}(\mathord{\cdot}\mid G_L)

is defined.

A match prescription specifies one matched pair in one of the bijections, on a specified side AA or BB. The reverse orientation describes the same prescription. A collection is feasible if some tuple of bijections satisfies it. Every bijection on side YY has NY=∣Y∣pN_Y = |Y|p pairs. Before conditioning, a feasible collection of distinct prescriptions has probability ∏(NY)e−1\prod(N_Y)_{e}^{-1}, where the product runs over the bijections, ee is their respective number of prescriptions, and (N)e=N(N−1)⋯(N−e+1)(N)_e = N(N - 1)\cdots(N - e + 1).

There are at most 2nk∣T∣k2n^k|T|^k choices of vertices and labels that can describe a cycle of length kk. A feasible simple cycle uses kk distinct prescriptions, even for k=1k=1 or k=2k=2, and therefore has probability at most (np−vp−k)−k(np-vp-k)^{-k}. If an edge is called bad when it lies on a cycle of length less than LL, the expected number of bad edges is consequently at most

2∑1≤k<Lk(2∣T∣p)k=o(n).2\sum_{1\le k<L} k\left(\frac{2|T|}{p}\right)^k=o(n).

Here np−vp−k≥np/2np-vp-k\ge np/2 for large nn, uniformly for k<Lk<L, and the last assertion follows from (11).

We use the following elementary switch. Suppose that xyxy and uzuz are edges on the same side, both oriented with the same label tt. Assume that uzuz is not bad and that the distance between {x,y}\{x,y\} and {u,z}\{u,z\} exceeds 2L2L. Distances between different components are understood to be infinite. Transpose the two targets in the bijection, replacing xy,uzxy,uz by xz,uyxz,uy. This preserves every outgoing label set and creates no cycle of length less than LL.

For the last assertion, any new short cycle must contain a new edge. If it contains just one, deleting that edge gives an old path of length less than LL between the two distant endpoint sets, a contradiction. If it contains both, deleting the new edges gives two old paths. Either one of these crosses between the endpoint sets, again contradicting their distance, or the paths join xx to yy and uu to zz. In the latter case the old uu-to-zz path together with uzuz is a cycle of length less than LL, contrary to the choice of uzuz. This argument also applies when x=yx=y; the corresponding residual path can have length zero.

Choose an initial tuple with o(n)o(n) bad edges, as supplied by (3.10). Given a bad edge xyxy, the number of edges having an endpoint within distance 2L2L of xx or yy is O(d∗2L+2)=o(n)O(d_*^{2L+2})=o(n), by (11). The appropriate bijection contains at least np−vpnp-vp edges, so it has an edge uzuz which is neither bad nor excluded by this distance condition. The switch removes the bad edge xyxy and creates no new bad edges. Repeating decreases the number of bad edges strictly at each step and eventually gives a tuple in GL\mathcal G_L. Since every tuple has positive probability, P(GL)>0\mathbb P(\mathcal G_L)>0.

The purpose of switching is also quantitative. It permits an upper bound for an additional prescribed edge without any lower bound for P(GL)\mathbb P(\mathcal G_L).

Lemma 3.3 (Prescriptions under girth conditioning). There is a nonnegative sequence rn=vp+O(d∗2L+2)=o(n)r_n=vp+O(d_*^{2L+2})=o(n) with the following property. If SS is a collection of ss distinct prescriptions having positive probability under PL\mathbb P_L, and ee is a further prescription not in SS, then

PL(e∣S)≤1np−s−rnwhenever np−s−rn>0.(12)\mathbb P_L(e\mid S)\le\frac{1}{np-s-r_n}\qquad\text{whenever }np-s-r_n>0. \tag*{(12)}

In particular, for every fixed C1>0C_1>0, a specified collection of E≤C1LE\le C_1L distinct prescriptions satisfies the uniform bound

PL(all E prescriptions hold)≤(np)−Eexp⁡(o(L)).\mathbb P_L(\text{all }E\text{ prescriptions hold})\le(np)^{-E}\exp(o(L)).

Proof. The conditional law is uniform on the finite set of tuples satisfying GL\mathcal G_L and SS. Partition this set into Ω+\Omega_+, the tuples containing e=xye=xy, and Ω−\Omega_-, those not containing it. If Ω+\Omega_+ is empty there is nothing to prove. Otherwise orient ee with its prescribed label. For any tuple in Ω+\Omega_+, at least

np−vp−s−O(d∗2L+2)≥np−s−rnnp-vp-s-O(d_*^{2L+2})\ge np-s-r_n

edges of its bijection are sufficiently distant from {x,y}\{x,y\} and are not in SS. Choose the constant defining rnr_n uniformly large enough for this inequality. Switching xyxy with any such edge gives a tuple in Ω−\Omega_{-}: all old edges avoid short cycles, so the preceding switching argument preserves girth, and neither deleted edge is prescribed by SS.

The output uniquely determines the input and the chosen switch. Indeed, if ϕ′:Yt→Ytˉ\phi':Y_t\to Y_{\bar t} is the output bijection, then z=ϕ′(x)z=\phi'(x) and u=(ϕ′)−1(y)u=(\phi')^{-1}(y). Replacing these two matches by ϕ(x)=y\phi(x)=y and ϕ(u)=z\phi(u)=z recovers the input, even when the domain and codomain overlap as vertex sets. Thus

∣Ω+∣(np−s−rn)≤∣Ω−∣.|\Omega_{+}|(np-s-r_n)\leq|\Omega_{-}|.

Dividing by the total number of tuples proves (12). Incompatible additional prescriptions have probability zero and satisfy the same bound.

Expose a specified collection of E≤C1LE\leq C_1L edges in any order. If a prefix is impossible its joint probability is zero; otherwise (12) applies at every step. Hence

PL(all E prescriptions hold)≤∏s=0E−1(np−s−rn)−1≤(np)−Eexp⁡(O(E(E+rn)n)).\mathbb{P}_L(\text{all }E\text{ prescriptions hold})\leq\prod_{s=0}^{E-1}(np-s-r_n)^{-1}\leq(np)^{-E}\exp\left(O\left(\frac{E(E+r_n)}{n}\right)\right).

Since E=O(L)E=O(L), L=O(log⁡n)L=O(\log n), and rn=o(n)r_n=o(n), the error in the exponent is o(L)o(L), uniformly for the stated range of EE.

Expansion and component diameter

We now use (12) for collections with a small linear number of edges. The high minimum degree forces small vertex sets to expand, even under girth conditioning.

Proposition 3.4 (Component diameter). There is a fixed constant d>0d>0 such that, with PL\mathbb{P}_L-probability tending to one as m→∞m\to\infty, every connected component of ΓA\Gamma_A and ΓB\Gamma_B has diameter at most dLdL.

Proof. For a vertex set SS in either graph, let N[S]N[S] be SS together with all its neighbors. We first show that there is a constant ρ>0\rho>0 such that, with probability tending to one,

∣N[S]∣≥2∣S∣for every S with 1≤∣S∣≤ρn on either side.(13)|N[S]|\geq2|S|\qquad\text{for every }S\text{ with }1\leq|S|\leq\rho n\text{ on either side.} \tag*{(13)}

All constants used to choose ρ\rho below are independent of nn.

Suppose ∣S∣=k≤ρn|S|=k\leq\rho n and ∣N[S]∣<2k|N[S]|<2k. Take ρ<1/4\rho<1/4, so that 2k≤n−v2k\leq n-v for sufficiently large nn. We can then enlarge N[S]N[S] to a set ZZ of exactly 2k2k vertices on the same side. Every edge incident to SS has both endpoints in ZZ. The sum of the degrees in SS is at least 129k129k, and an edge contributes at most two to that sum. Therefore ZZ contains at least

r=⌈129k/2⌉r=\lceil129k/2\rceil

distinct edges. Notice that 64.5k≤r≤65k64.5k\leq r\leq65k.

There are at most (en/(2k))2k(en/(2k))^{2k} choices for ZZ. For a fixed ZZ, the number of possible labeled edge prescriptions with endpoints in ZZ is at most 4∣T∣k24|T|k^2. Thus the number of sets of rr such prescriptions is at most

(4∣T∣k2r)≤(C2k)r\binom{4|T|k^2}{r}\leq(C_2k)^r

for a fixed constant C2C_2; if fewer than rr prescriptions are available, the event is empty. Reduce ρ\rho so that 65ρ<p/465\rho<p/4. Because rn=o(n)r_n=o(n), all denominators in (12), when exposing these rr edges, are at least np/2np/2 for sufficiently large nn. Each collection therefore has probability at most (2/(np))r(2/(np))^r. A union bound, first over ZZ and then its prescribed edges, now bounds the probability of failure for this kk on either fixed side by

(en2k)(C2k)r(2np)r≤(C3(k/n)62.5)k(14)\binom{en}{2k}(C_2k)^r\left(\frac{2}{np}\right)^r \leq\left(C_3(k/n)^{62.5}\right)^k \tag*{(14)}

for a fixed C3C_3. The exponent 62.562.5 is 129/2−2129/2-2; rounding rr changes only the constant because 64.5≤r/k≤6564.5 \leq r/k \leq65. Choose ρ\rho smaller once more so that C3ρ62.5<1/2C_3\rho^{62.5}<1/2. For k≤nk \leq\sqrt{n}, the right side of (14) is at most (C3n−31.25)k(C_3n^{-31.25})^k, whose sum tends to zero. For n<k≤ρn\sqrt{n}<k\leq\rho n, it is at most 2−k2^{-k}, again with sum tending to zero. Including both sides proves (13) with probability 1−o(1)1-o(1).

Assume (13). Starting with any vertex, successive closed balls double in cardinality as long as they have at most ρn\rho n vertices. In particular every ball of radius

R=⌈log⁡2n⌉+1R=\lceil\log_2 n\rceil+1

has more than ρn\rho n vertices. On a geodesic of length DD in a component, select vertices at spacings 2R+12R+1. Their radius-RR balls are pairwise disjoint, because distances between vertices on a geodesic equal their separations along it. All these balls lie on one side, which has at most nn vertices. Hence

(⌊D2R+1⌋+1)ρn<n,D<2R+1ρ.\left(\left\lfloor\frac{D}{2R+1}\right\rfloor+1\right)\rho n<n,\qquad D<\frac{2R+1}{\rho}.

Since R=O(log⁡n)R=O(\log n) and L∼c0log⁡nL\sim c_0\log n, a fixed dd bounds the last expression by dLdL for all sufficiently large nn. This proves the proposition simultaneously for all components.

A bounded path estimate

We now use the word estimate of Lemma 3.2 to rule out short systems of paths with extensive label comparisons. An edge of the image graph may occur many times in these paths. The proof keeps track of this repetition by counting subgraphs at successive multiplicity levels. Comparisons then recover the square of the word weight needed for Lemma 3.2. We develop the multiplicity and block argument of [12], Section “A bounded-pattern estimate” for the types constructed here.

A position of a path means an edge traversal, so different positions may traverse the same edge of Γ\Gamma. A comparison consists of two disjoint intervals of positions of equal length, together with one of the following requirements: their words agree in the given orders, or their words are t1⋯tht_1\cdots t_h and tˉh⋯tˉ1\bar{t}_h\cdots\bar{t}_1. The comparisons in a system use disjoint positions. We allow cyclic intervals on a closed path. Throughout this section comparisons must also satisfy

paired positions traverse distinct underlying undirected edges of Γ.(15)\text{paired positions traverse distinct underlying undirected edges of }\Gamma. \tag*{(15)}

Write HH for the sum of the path lengths and b0b_0 for the number of positions not used in a comparison.

Theorem 4.1 (Bounded path estimate). There is a constant ε>0\varepsilon>0, depending only on the fixed alphabet and turn weights, with the following property. For every integer K0≥1K_0\geq1, real number C≥1C\geq1, and integer I≥0I\geq0, the probability under PL\mathbb{P}_{\mathrm{L}} that Γ\Gamma contains a system satisfying all the following conditions tends to zero as n⟶∞n\longrightarrow\infty:

  1. There are at most K0K_0 positive-length paths. Each is closed and cyclically immersed, except possibly one immersed interval path whose initial vertex is xAx_A or $x_B.

  1. The total length satisfies L≤H≤CLL \le H \le CL.

  1. There are at most II comparisons, satisfying (15), and b0≤εHb_0 \le\varepsilon H.

In particular, ε\varepsilon is chosen before K0,C,IK_0,C,I. The threshold in nn and the rate of convergence may depend on these three bounds.

Fix K0,C,IK_0,C,I for the proof. All constants described below as bounded may depend on these parameters and on the fixed alphabet. All o(L)o(L) estimates are uniform over the systems and patterns satisfying these bounds. We always work under the conditional law PL\mathbb{P}_L. Index each closed path by choosing a starting vertex. If a comparison crosses one of these indexing points, split both intervals of that comparison at the corresponding position. The number of resulting comparisons is still bounded in terms of II and K0K_0, and their union of paired positions has not changed.

The image graph and its multiplicity levels

Let Δ⊆Γ\Delta\subseteq\Gamma be the image of a putative system. It has at most CLCL edges and girth at least LL. We first show that it has bounded topological complexity. Here the cycle rank of a finite graph is ∣E∣−∣V∣+|E|-|V|+ the number of connected components.

Lemma 4.2. For fixed CC, every finite graph of girth at least LL with at most CLCL edges has bounded cycle rank, uniformly in LL.

Proof. Delete vertices of degree at most one repeatedly; this does not change the cycle rank. Components of the remaining graph that are circles number at most CC, since each has at least LL edges. Remove these components, and suppress every degree-two vertex in what remains. The resulting multigraph DD, if nonempty, has minimum degree at least three. Give each edge of DD the positive integer length of the path it represents. The sum of these lengths is at most CLCL.

Suppose DD has r>0r>0 edges. Choose a directed edge uniformly from the 2r2r choices, then take a non-backtracking walk with kk directed edges, choosing each continuation uniformly. The uniform law on directed edges is stationary: a directed edge starting at zz has deg⁡(z)−1\deg(z)-1 allowed predecessors, each of which chooses it with probability 1/(deg⁡(z)−1)1/(\deg(z)-1). Thus the expected sum of the inherited lengths along the walk is at most kCL/rkCL/r. Markov’s inequality puts at least half of the probability on walks of length at most 2kCL/r2kCL/r. Since every individual walk has probability at most (2r)−12−(k−1)(2r)^{-1}2^{-(k-1)}, there are at least r2k−1r2^{k-1} such short walks.

Take k=⌈log⁡2(8r)⌉+1k=\lceil\log_2(8r)\rceil+1. Then r2k−1>(2r)2r2^{k-1}>(2r)^2, whereas there are at most (2r)2(2r)^2 ordered pairs of endpoint vertices. Two distinct short walks therefore have the same endpoints. Expanding their edges gives distinct reduced paths in the original graph. Their union contains a cycle: in a forest there is only one reduced path between any two vertices. This cycle has length at most 4kCL/r4kCL/r, so the girth bound implies

r≤4C(⌈log⁡2(8r)⌉+1).r \le4C(\lceil\log_2(8r)\rceil+1).

The right side grows logarithmically with rr, and hence this inequality bounds rr in terms of CC. Suppression preserves cycle rank, whose contribution from DD is at most rr; the removed circle components contribute at most CC. □\square

Mark every vertex of Δ\Delta whose degree differs from two, and also every initial and terminal vertex of our indexed paths. There are no isolated vertices. A leaf can occur only as an endpoint of the possible interval path, because every other path turn is immersed. There are therefore at most two leaves. To see explicitly that the remaining marks are bounded, write β\beta for the cycle rank and cc for the number of components. The degree sum gives

∑deg⁡(z)≥3(deg⁡(z)−2)=2β−2c+#{z:deg⁡(z)=1}.\sum_{\deg(z)\ge3}(\deg(z)-2)=2\beta-2c+\#\{z:\deg(z)=1\}.

Lemma 4.2 bounds both the number and the total degree of vertices of degree at least three. There are at most 2K02K_0 additional path-endpoint marks. Each component contains a path start. Consequently Δ\Delta is the union of a bounded number of chains, that is, paths between marked vertices with disjoint, unmarked degree-two interiors. A chain may have the same marked vertex at both ends. Choose an orientation on every chain.

Every path traverses whole chains. Let mem_e be the total number of traversals of the undirected edge ee by the entire path system. This multiplicity is constant on the edges of each chain. Two successive uses of the same oriented edge by a single indexed path have starting positions separated by at least LL: the intervening path from the initial vertex of that edge back to itself is a nonempty reduced closed walk and contains a cycle. For a path of length hh, each orientation can therefore occur at most h/L+1h/L+1 times. Summing over paths and the two orientations yields

me≤2(H/L+K0)≤2(C+K0),M:=⌈2(C+K0)⌉.(16)m_e\le2(H/L+K_0)\le2(C+K_0),\qquad M:=\lceil2(C+K_0)\rceil. \tag*{(16)}

An unlabelled pattern records the finite marked chain graph, its positive chain lengths, the side AA or BB of each component, the indexed paths as sequences of oriented chain traversals, and the endpoints and directions of the comparisons. It records whether there is an interval path and, if so, which root is its initial vertex. Only patterns having the structure just proved and satisfying (15) are retained. The underlying graph in a pattern is an image graph: a realization must map its vertices and edges injectively into the appropriate sides of Γ\Gamma.

There are boundedly many chain traversals by (16). All lengths and comparison endpoints are integers between 00 and CLCL. Hence the number of unlabelled patterns is polynomial in LL. This includes the finitely many choices of chain graph, traversal sequences, sides, and interval designation.

For a pattern, let m∗:=max⁡eme≤Mm_*:=\max_e m_e\le M. Its stage jj graph Δj\Delta_j consists of all edges with me≥jm_e\ge j and their endpoints, for 1≤j≤m∗1\le j\le m_*. Write VjV_j and EjE_j for its numbers of vertices and edges. Let ι\iota be 1 if there is an interval path and 0 otherwise, and put

k1=ι,kj=0(j>1).k_1=\iota,\qquad k_j=0\quad(j>1).

We will fix the prescribed root only when counting stage one. This loss of a factor nn pays precisely for the two possible unpaired path endpoints in the following incidence estimate.

Lemma 4.3. The stage graphs satisfy

∑j=1m∗Ej=H,∑j=1m∗Vj≤H+ι,∑j=1m∗(Vj−Ej−kj)≤0.(17)\sum_{j=1}^{m_*}E_j=H,\qquad \sum_{j=1}^{m_*}V_j\le H+\iota,\qquad \sum_{j=1}^{m_*}(V_j-E_j-k_j)\le0. \tag*{(17)}

Proof. The first identity counts an edge once at each of its mem_e stages. At a vertex zz, put a(z)a(z) equal to the number of interval endpoints located there, counting both if they coincide; then ∑za(z)=2ι\sum_z a(z)=2\iota. Every other traversal incidence is paired, by a path turn, with an incidence on a different half-edge. For any particular half-edge at zz, all but a(z)a(z) of its mem_e incidences must therefore be paired with the other half-edges. For sufficiently large nn, L>2L > 2, so Δ\Delta has no loops; it follows that

2max⁡e∋zme≤∑e∋zme+a(z).2\max_{e\ni z} m_e \le\sum_{e\ni z}m_e+a(z).

A vertex occurs at exactly max⁡e∋zme\max_{e\ni z}m_e stages. Summing this inequality over vertices gives ∑jVj≤∑eme+ι=H+ι\sum_j V_j \le\sum_e m_e+\iota=H+\iota. Since ∑jkj=ι\sum_j k_j=\iota, the last assertion follows.

One grid for all comparisons

The role of (17) is visible in the embedding count. For fixed labels, choosing VjV_j vertices, prescribing EjE_j distinct edges, and fixing kjk_j roots leave a factor nVj−Ej−kjn^{V_j-E_j-k_j}. Apart from factors subexponential in LL, the turn frequencies also supply one word weight for each chain. Thus (17) permits us to combine the stage estimates without a positive net power of nn. It remains to sum over labels compatible with the comparisons; the precise embedding count appears in (23) below.

For orientation, suppose two edge-disjoint chain segments are required to carry the same word WW. Their turn-weight contribution is P(W)2P(W)^2, although only one word is free to vary. The same holds for inverse words because P(W−1)=P(W)P(W^{-1})=P(W). Lemma 3.2 then supplies exponential decay. In the actual system, the comparison endpoints need not line up, and chains can be traversed repeatedly. We now subdivide the chains into long words whose boundaries nearly agree across comparisons; the multiplicity stages will account for the repeated traversals.

Fix an unlabelled pattern. Give each oriented chain coordinates from 00 to its length, putting edge positions at half-integers. Split a comparison whenever either of its path intervals crosses a chain end. The bounded number of chain traversals gives a bounded number of resulting subcomparisons. In chain coordinates each is a restriction of

x↦σx+a,σ∈{1,−1},a∈Z.(18)x \mapsto\sigma x+a,\qquad\sigma\in\{1,-1\},\qquad a\in\mathbb{Z}. \tag*{(18)}

If σ=1\sigma=1, the labels in chain orientation agree; if σ=−1\sigma=-1, they are inverse. This follows by incorporating into the comparison the orientation of each of its two chain traversals.

We need blocks whose grids agree approximately under every map in (18). Choose a fixed integer d1≥1d_1\ge1 bounding the number of offsets, padding their list with zeros when necessary. Put

N=⌊L1/(2(d1+1))⌋,R=⌊N⌋.N=\left\lfloor L^{1/(2(d_1+1))}\right\rfloor,\qquad R=\lfloor\sqrt{N}\rfloor.

Partition [0,1)d1[0,1)^{d_1} into Nd1N^{d_1} boxes of side 1/N1/N. Among the Nd1+1N^{d_1}+1 vectors with coordinates {ℓa/L}\{\ell a/L\}, 0≤ℓ≤Nd10\le\ell\le N^{d_1}, two lie in the same box. Subtracting their indices gives 1≤u≤Nd11\le u\le N^{d_1} such that

dist⁡(ua/L,Z)≤1/N\operatorname{dist}(ua/L,\mathbb{Z})\le1/N

for every offset aa.

Choose one such uu deterministically from the pattern and set

s:=LuR.s:=\frac{L}{uR}.

Uniformly over patterns,

LNd1N≤s≤LR,dist⁡(a/s,Z)≤R/N.\frac{L}{N^{d_1}\sqrt{N}}\le s\le\frac{L}{R},\qquad\operatorname{dist}(a/s,\mathbb{Z})\le R/N.

In particular, s→∞s\to\infty, s=o(L)s=o(L), and all the distances in the last display tend to zero. The lower bound even gives s≥L(d1+3)/2/(2(d1+1))s\ge L^{(d_1+3)/2^{}}/(2(d_1+1)) for large LL, so all estimates involving L/sL/s are uniform.

On each chain take the edge positions lying in grid intervals [ks,(k+1)s)[ks,(k+1)s) contained in its coordinate interval. These sets are the full blocks. The final fragment has fewer than s+1s+1 positions. Index underlying full blocks by ii, and write hih_i for their lengths and mim_i for their chain multiplicities. Thus hi=s+O(1)h_i=s+O(1) and 1≤mi≤M1\le m_i\le M. Every traversal of a chain uses the same subdivision; a block ii therefore has mim_i separate occurrences in the path system.

Choose κ=κL>0\kappa=\kappa_L>0 tending to zero, large enough to dominate the grid displacement R/NR/N and the rounding error 10/s10/s. For each subcomparison, match two full-block occurrences if it compares contiguous portions of these occurrences of length at least (1−κ)s(1-\kappa)s. Record the entire substring constraint on that overlap. For large LL this gives a partial matching of occurrences. Indeed, the matched portion occupies more than half of each block. Two different proposed matches incident to the same occurrence would therefore overlap, contrary to the disjointness of all compared positions. The match is recorded only once, irrespective of which of its two occurrences is considered first.

We next bound the full-block occurrences left unmatched. Exclude the boundedly many block occurrences within distance 3s+O(1)3s+O(1) of a subcomparison endpoint or a chain end, measuring distance along the corresponding traversal. A remaining block occurrence either has every position unpaired, or lies wholly inside one subcomparison. In the latter case its grid interval maps under (18) to an interval displaced by at most (R/N)s(R/N)s from a grid interval on the partner chain. Reflection may exchange open and closed endpoints, changing the number of half-integer positions by at most two. The partner interval is full, because the source block is also far from the corresponding subcomparison ends. The two blocks consequently overlap in at least (1−κ)s(1-\kappa)s compared positions, and are matched.

Let b∗b_* be the number of unmatched full-block occurrences. There are O(L/s)O(L/s) occurrences altogether. Each unmatched occurrence outside the bounded exceptional collection contributes at least s−1s-1 unpaired positions. It follows that

sb∗≤b0+O(s+L/s)=b0+o(L).(19)sb_* \le b_0+O(s+L/s)=b_0+o(L). \tag*{(19)}

The constants here count subcomparison ends and chain traversals, not individual edges.

Now forget the occurrence indices while retaining all matches and their substring constraints. This gives a multigraph on the underlying blocks; call its edges links. A link whose two occurrences belong to the same underlying block is a self-link. Isolated blocks are included as components. For a component U\mathcal{U}, put

SU=∑i∈Umi,zU=max⁡i∈Umi,bU=#{unmatched occurrences of blocks in U}.(20)S_{\mathcal{U}}=\sum_{i\in\mathcal{U}}m_i,\qquad z_{\mathcal{U}}=\max_{i\in\mathcal{U}}m_i,\qquad b_{\mathcal{U}}=\#\{\text{unmatched occurrences of blocks in }\mathcal{U}\}. \tag*{(20)}

In particular, ∑UbU=b∗\sum_{\mathcal{U}}b_{\mathcal{U}}=b_*. Figure 1 illustrates the nearly aligned grids and the distinction between occurrences and underlying blocks.

Aligned blocks and occurrences with underlying blocks

Figure 1. Aligned blocks and the two levels of comparison. In (a), away from subcomparison ends, the image of a full grid interval is displaced by o(s)o(s) from a partner grid interval; the shaded portion JJ records a comparison of s−o(s)s-o(s) positions. Reflection reverses order and inverts letters. The intervals and their small end discrepancies are schematic. In (b), i(r)i^{(r)} denotes the rrth occurrence of block ii. Occurrence joins form a partial matching, but forgetting the occurrence indices can give several links at one underlying block.

Lemma 4.4. There is a number ρL→0\rho_L\to0, uniform over patterns, with the following properties. Every word assignment counted in this lemma is required to be reduced on each block.

  1. Given the reduced word on one block of a link component U\mathcal{U}, at most exp⁡(ρLs∣U∣)\exp(\rho_Ls|\mathcal{U}|) assignments of words to all its blocks satisfy the link constraints.

  1. If U\mathcal{U} contains a self-link, the total number of such assignments is at most exp⁡(ρLs∣U∣)\exp(\rho_Ls|\mathcal{U}|).

  1. If U\mathcal{U} has no self-link, then

2zU≤SU+bU.(21)2z_{\mathcal{U}}\le S_{\mathcal{U}}+b_{\mathcal{U}}. \tag*{(21)}

Proof. Root a spanning tree of the link component at the block whose word is given. A link from a known block determines at least (1−κ)s(1-\kappa)s letters of the next block, whose total length is at most s+1s+1. There are at most ∣T∣κs+1|T|^{\kappa s+1} choices for its remaining letters. Multiplying along the tree proves the first assertion, even if we ignore reducedness and all links outside the tree when making this upper bound.

For the second assertion, start with a block carrying a self-link. If its coordinate map is a translation, the constraint takes the form tx=tx+at_x=t_{x+a} on at least (1−κ)s(1-\kappa)s consecutive positions. The integer aa is nonzero: a=0a=0 would pair occurrences of the same underlying edge, violating (15). The equality graph on the hih_i positions is a forest. In fact all its edges have the same nonzero step, and within each residue class modulo ∣a∣|a| they connect successive positions in their natural order. There are at least (1−κ)s(1-\kappa)s distinct equality edges, leaving at most hi−(1−κ)s≤κs+1h_i-(1-\kappa)s\le\kappa s+1 components. Choosing one letter per component gives at most ∣T∣κs+1|T|^{\kappa s+1} choices.

A reflection self-link cannot occur with reduced block words. Let JJ be the interval of positions on which the constraint reads tx=ta−xt_x=t_{a-x}. Its reflected image also lies in the same block, and both have more than half the block’s positions. Their intersection is therefore a nonempty interval invariant under reflection. If it has a central fixed position, the letter there would equal its inverse, contrary to the fixed-point-free involution on TT. If it has no fixed position, its two central adjacent positions are reflections of each other and have inverse letters, contrary to reducedness. After counting the words on the initial self-linked block, propagate along a spanning tree as above. Enlarging ρL\rho_L by a fixed factor proves the second assertion.

Finally, choose a block with mi=zum_i=zu. If there is no self-link, every matched occurrence of this block has its partner among the Su−zuSu-zu occurrences of other blocks. There are at least zu−buzu-bu such matched occurrences, and distinct occurrences have distinct partners. Hence zu−bu≤Su−zuzu-bu\le Su-zu, which is (21).

Word bins and stage expectations

The link constraints make the number of free words small. To combine this fact with the probability of embedding a labelled graph, we must also retain each block’s word weight. For its word WiW_i, in the chosen chain orientation, record the integer

di:=⌊−log⁡P(Wi)⌋.d_i := \lfloor-\log P(W_i)\rfloor.

All these words are reduced. Since the fixed collection of positive turn weights has a positive minimum, there is a constant a0>0a_0>0 depending only on those weights such that, for large LL,

δs2≤di≤a0s,#{W∈Thi:⌊−log⁡P(W)⌋=di}≤exp⁡(2di−δs).(22)\frac{\delta s}{2} \le d_i \le a_0s,\qquad\#\{W\in T^{h_i}:\lfloor-\log P(W)\rfloor=d_i\}\le\exp(2d_i-\delta s). \tag*{(22)}

Here and below only positive-weight words are counted. For completeness, Lemma 3.2 implies P(W)2≤e−2δhiP(W)^2\le e^{-2\delta h_i} for each word, so di≥δhi−1≥δs/2d_i\ge\delta h_i-1\ge\delta s/2 for large ss. The minimum turn weight gives the upper bound. Every word in the bin has P(W)>e−di−1P(W)>e^{-d_i-1}, and therefore the number in the bin is at most

e2di+2∑W∈ThiP(W)2≤e2di+2−2δhi≤e2di−δs.e^{2d_i+2}\sum_{W\in T^{h_i}}P(W)^2\le e^{2d_i+2-2\delta h_i}\le e^{2d_i-\delta s}.

These estimates are uniform because hi=s+O(1)h_i=s+O(1) and s→∞s\to\infty. Enlarge the pattern by recording all did_i. There are O(L/s)O(L/s) full blocks, each with O(s)O(s) possible bins. Thus the logarithm of the number of bin choices is O((L/s)log⁡(s+2))=o(L)O((L/s)\log(s+2))=o(L). Together with the earlier polynomial count, the total number of enlarged patterns is

exp⁡(o(L)).\exp(o(L)).

The grid, occurrence matching, and link multigraph are determined by the unlabelled pattern, and introduce no further choices.

Fix one enlarged pattern. A full label assignment means labels on all edges of its abstract image graph, read inversely on reverse edges, giving an immersion into FF and satisfying the comparisons and bins. This is a condition on strings on the abstract graph; it does not require an embedding in the random graph. At stage jj, consider the restrictions of all such full label assignments to Δj\Delta_j. Let ZjZ_j count their injective realizations in Γ\Gamma, with the component sides prescribed by the pattern, and with the root fixed if kj=1k_j=1. Every realization of the original enlarged pattern gives Zj≥1Z_j\ge1 at every stage.

For a fixed one of these stage label assignments, the expected number of its realizations is at most

nVj−Ej−kjexp⁡(−∑i:mi≥jdi+o(L)).(23)n^{V_j-E_j-k_j}\exp\left(-\sum_{i:m_i\ge j}d_i+o(L)\right). \tag*{(23)}

To prove this, let QjQ_j be the number of active chains, that is, chains whose edges belong to Δj\Delta_j. They have exactly Ej−QjE_j-Q_j unmarked internal vertices. At such a vertex the incoming and outgoing chain labels form a reduced turn t,ut,u, and (9) bounds its possible images on its prescribed side by

np w(t,u)+O(1)=np w(t,u)(1+O(1/n)).np\,w(t,u)+O(1)=np\,w(t,u)(1+O(1/n)).

At each remaining unfixed vertex use the upper bound nn; a fixed root is marked and has only one choice. This bounds the number of possible vertex assignments by

nVj−kjpEj−Qj∏internal turns of active chainsw(t,u)exp⁡(O(L/n)).n^{V_j-k_j}p^{E_j-Q_j} \prod_{\text{internal turns of active chains}}w(t,u)\exp(O(L/n)).

Restrict to the assignments that are injective and compatible with all vertex types. Each requires EjE_j distinct edge prescriptions. Lemma 3.3 bounds their joint probability by (np)−Ejexp⁡(o(L))(np)^{-E_j}\exp(o(L)).

Multiplication leaves nVj−Ej−kjp−Qjn^{V_j-E_j-k_j}p^{-Q_j} times the displayed turn product. The bounded factor p−Qjp^{-Q_j} is exp⁡(o(L))\exp(o(L)). Every turn weight is at most one, so discarding all factors except internal turns of full blocks increases the product. The remaining product is

∏i:mi≥jP(Wi)≤exp⁡(−∑i:mi≥jdi).\prod_{i:m_i\ge j} P(W_i) \le\exp\left(-\sum_{i:m_i\ge j} d_i\right).

which proves (23). This count uses injective realizations of the image graph; it does not replace distinct edge prescriptions by repeated traversals.

The number of stage label assignments has the bound

exp⁡(o(L)+∑U without self-linkzU≥j(2min⁡i∈Udi−δs)).(24)\exp\left(o(L)+\sum_{\substack{U\ \text{without self-link}\\ z_U\ge j}}\left(2\min_{i\in U}d_i-\delta s\right)\right). \tag*{(24)}

Indeed, a link component is represented at stage jj exactly when zU≥jz_U\ge j. The possible words on its represented blocks are projections of assignments on the entire link component. A projection has cardinality no larger than the set being projected. If the component has no self-link, choose a block attaining the minimum bin, even when that block is absent from stage jj. (22) gives at most exp⁡(2min⁡i∈Udi−δs)\exp(2\min_{i\in U}d_i-\delta s) choices on this block, and Lemma 4.4 bounds the extensions by exp⁡(ρLs∣U∣)\exp(\rho Ls|U|). If the component has a self-link, the second assertion of that lemma gives this last factor without any initial word choice. Constraints between different words, or at chain junctions, can only reduce these counts.

Summed over components, the propagation error is ρLsO(L/s)=o(L)\rho Ls O(L/s)=o(L). There are only boundedly many chain end fragments, containing O(s)O(s) positions in total; assigning their letters freely costs at most ∣T∣O(s)=exp⁡(o(L))|T|^{O(s)}=\exp(o(L)). These observations prove (24). Requiring stage labels to extend as strings was essential: it permits the minimum-bin block to be used even at stages where it is absent.

Let BjB_j be the product of the right sides of (23) and (24), choosing their uniform error bounds. Then

ELZj≤Bj,PL(the enlarged pattern is realized)≤min⁡1≤j≤m∗Bj.(25)\mathbb{E}_L Z_j\le B_j,\qquad\mathbb{P}_L(\text{the enlarged pattern is realized})\le\min_{1\le j\le m_*}B_j. \tag*{(25)}

The second inequality is Markov’s inequality at each individual stage. We will now bound the minimum by multiplying the deterministic numbers BjB_j.

Combining the stages

Proof of Theorem 4.1. Lemma 4.3 shows that the total exponent of nn in ∏j=1m∗Bj\prod_{j=1}^{m_*}B_j is nonpositive. For a component UU without a self-link, write dmin⁡=min⁡i∈Udid_{\min}=\min_{i\in U}d_i. Its positive label-count term occurs at zUz_U stages; the negative term −di-d_i occurs at mim_i stages. Its total contribution to the logarithm, apart from the uniform errors, is at most

zU(2dmin⁡−δs)−∑i∈Umidi≤(2zU−SU)dmin⁡−δszU≤a0sbU−δs2SU.\begin{aligned} z_U(2d_{\min}-\delta s)-\sum_{i\in U}m_i d_i \le(2z_U-S_U)d_{\min}-\delta s z_U \\ &\le a_0s b_U-\frac{\delta s}{2}S_U. \end{aligned}

For the last inequality, if 2zU−SU≤02z_U-S_U\le0, use dmin⁡≥δs/2d_{\min}\ge\delta s/2 to bound the preceding line by −δsSU/2-\delta sS_U/2. If 2zU−SU>02z_U-S_U>0, use dmin⁡≤a0sd_{\min}\le a_0s and 2zU−SU≤bU2z_U-S_U\le b_U from (21); the remaining term satisfies −δszU≤−δsSU/2-\delta sz_U\le-\delta sS_U/2.

For a component with a self-link there is no positive label-count term, and (22) gives

−∑i∈Umidi≤−δs2SU.-\sum_{i\in\mathcal{U}}m_id_i\le-\frac{\delta s}{2}S_U.

The full-block occurrences account for all positions except O(s)O(s) positions in end fragments. Replacing their actual lengths hi=s+O(1)h_i=s+O(1) by ss changes the count by O(L/s)O(L/s), because the multiplicities are bounded. Thus

s∑USU=H+O(s+L/s)=H+o(L).s\sum_U S_U=H+O(s+L/s)=H+o(L).

Equation (19) also gives s∑UbU≤b0+o(L)s\sum_U b_U\le b_0+o(L). There are at most MM stages, so summing their uniform errors still gives o(L)o(L). We conclude that

log⁡∏j=1m∗Bj≤−δ2H+a0b0+o(L).(26)\log\prod_{j=1}^{m_*}B_j\le-\frac{\delta}{2}H+a_0b_0+o(L). \tag*{(26)}

Choose, once and for all,

ε:=min⁡{14,δ16(1+a0)}.(27)\varepsilon:=\min\left\{\frac{1}{4},\frac{\delta}{16(1+a_0)}\right\}. \tag*{(27)}

Both δ\delta and a0a_0 depend only on the fixed alphabet and weights, so this choice is independent of K0,C,IK_0,C,I. If b0≤εHb_0\le\varepsilon H and H≥LH\ge L, the uniform error in (26) is small enough, for all sufficiently large nn, that

log⁡∏j=1m∗Bj≤−δ4H.\log\prod_{j=1}^{m_*}B_j\le-\frac{\delta}{4}H.

Some stage therefore has

Bj≤exp⁡(−δH4m∗)≤exp⁡(−δH4M).B_j\le\exp\left(-\frac{\delta H}{4m_*}\right)\le\exp\left(-\frac{\delta H}{4M}\right).

Equation (25) bounds the realization probability of this enlarged pattern by the last expression. No independence of the stages has been used; a full realization must survive every one of their separate first-moment bounds. Finally, sum over the exp⁡(o(L))\exp(o(L)) enlarged patterns from (4.10) and use H≥LH\ge L. The resulting bound

exp⁡(−δL4M+o(L))⟶0\exp\left(-\frac{\delta L}{4M}+o(L)\right)\longrightarrow0

proves the theorem, with the stated order of quantifiers. □\square

From spherical arrangements to bounded path systems

Theorem (15) excludes path systems whose number of paths, total length in units of LL, and number of comparison intervals are bounded. The topological argument will produce a planar pairing of paths with none of those bounds. We show that every such pairing yields a system covered by the theorem. Planarity has two roles: an Euler characteristic count organizes the pairing into few intervals, and a separator reduces the number of paths while losing few paired positions. This is the spherical-arrangement method of [12], Section “From bounded patterns to spherical arrangements”; we include the geometric and quantitative details needed here.

Definition 5.1 (Reduced spherical arrangement). A reduced spherical arrangement over Γ\Gamma consists of finitely many pairwise disjoint piecewise linear closed disks in an oriented sphere, together with the following data. Each boundary reads a positive-length cyclically immersed closed path in Γ\Gamma, except possibly one boundary. That boundary reads a positive-length immersed interval path starting at xAx_A or xBx_B, with its two endpoints represented at a single marked boundary point, called the break. No immersion condition is imposed across the break. At least one ordinary, cyclically immersed boundary is required.

The paths are read in the boundary orientations induced by the disks. Their edge occurrences are paired in distinct twos by mutually disjoint piecewise linear arcs. The interiors of the arcs lie outside the disks, and each occurrence contains exactly one arc endpoint in its interior. Paired occurrences have inverse signed letters and use distinct underlying undirected edges of Γ\Gamma.

The distinction between occurrences and graph edges is essential: different occurrences may traverse the same edge, but the two ends of any one pairing arc may not. The graph obtained by collapsing each disk to a vertex may be disconnected and may have loops or parallel edges.

Proposition 6.1 will show that the absence of these arrangements makes the cone complex aspherical and protects the two roots. The present section proves that the random graphs can be chosen to have this absence property.

Theorem 5.2 (Absence of reduced spherical arrangements). In the random matching model of Section 3, conditioned on girth at least LL, the probability that Γ\Gamma admits a reduced spherical arrangement tends to zero as m≡1(mod4)m \equiv1 \pmod{4} tends to infinity. Consequently, for every sufficiently large admissible mm there is a matching outcome with girth at least LL, the component diameter bound of Proposition 3.4, and no reduced spherical arrangement.

We first establish the three deterministic tools used in the proof. The first closes path segments without changing any original occurrences. The other two depend only on planarity.

Closing immersed segments

Fix the constant dd of Proposition 3.4, and work for now with an outcome in which every component of Γ\Gamma has diameter at most dLdL. Each side of Γ\Gamma has at most nn vertices and minimum degree at least 129.

Lemma 5.3 (Short closures). There is a fixed integer D0D_0, depending only on dd and c0c_0, with the following property for all sufficiently large admissible nn. If every component of Γ\Gamma has diameter at most dLdL, then every positive-length immersed path segment in Γ\Gamma extends to a cyclically immersed closed path by appending at most D0LD_0L edges. The original segment is retained without cancellation. One may take any integer

D0≥d+8c0log⁡2+8.D_0 \ge d + \frac{8}{c_0 \log2} + 8.

Proof. We first construct a short based loop that avoids specified edges at its basepoint. For large nn we have L≥3L \ge3, so the girth condition excludes loops and parallel edges. Delete at most two prescribed undirected edges incident to a vertex zz. In the remaining graph every vertex still has degree at least 127, and in particular at least three. With

k=⌊log⁡2n⌋+1,k = \lfloor\log_2 n \rfloor+ 1,

there are at least 3⋅2k−1>n3 \cdot2^{k-1} > n non-backtracking walks of length kk starting at zz. Two distinct such walks, say PP and QQ, end at the same vertex. Reduce PQ−1PQ^{-1} as a linear path. Cancellation removes their common terminal segment. Since PP and QQ are distinct and have equal length, it does not remove either entire walk. We obtain a nonempty linearly immersed based loop of length at most 2k2k; its first and last edges avoid the deleted edges. The loop need not be cyclically immersed at zz.

Let the given segment SS run from aa to bb, and choose a geodesic RR from bb to aa, of length at most dLdL. If RR is nonempty, construct a loop JbJ_b at bb avoiding the last edge of SS and the first edge of RR, and a loop JaJ_a at aa avoiding the last edge of RR and the first edge of SS. Then

SJbRJaSJ_bRJ_a

is cyclically immersed: each constituent is immersed as a linear path, and each of the four joins avoids immediate reversal. If RR is empty, then a=ba=b, and one loop at aa avoiding the first and last edges of SS makes SJaSJ_a cyclically immersed. Thus the total added length is at most dL+4kdL+4k in either case. Finally, L≥(c0/2)log⁡nL \ge(c_0/2)\log n and L≥1L \ge1 for large nn, so

k≤(2c0log⁡2+2)L.k \le\left(\frac{2}{c_0\log2}+2\right)L.

This gives the stated choice of D0D_0.

Organizing the pairing into intervals

We next count how often a planar pairing can change its consecutive partner interval. A pair of neighboring arc ends usually has another neighboring pair opposite it across a digon. Only the other gaps, and the places where we choose to split a path, require interval cuts. This is the linear comparison-interval argument of [13].

Lemma 5.4 (Paired intervals). Suppose a reduced spherical arrangement with N0N_0 disk boundaries is divided into N′≥N0N' \ge N_0 pieces by cutting its paths into consecutive segments. An intact path counts as one piece, and no piece crosses the exceptional break. Then all original occurrence pairings can be represented by at most 6N′6N' disjoint pairs of intervals. Each interval is contained in one designated piece, and each pair compares inverse strings in reverse boundary order. The intervals can also be required not to cross one prescribed indexing gap between occurrences on each original path, using the break as the exceptional indexing gap.

Proof. Thicken the disks and the pairing arcs to a closed regular neighborhood RR made of disks and rectangular bands. Write EE for the number of bands, or equivalently the number of pairing arcs. A gap is the portion of an original disk boundary between successive arc ends in cyclic order. After thickening, each gap gives a corner of a complementary region. For each connected component QQ of S2∖int⁡R\mathbb{S}^{2} \setminus\operatorname{int} R, let ℓQ\ell_Q be the number of band sides along its boundary, counting incidences. This is also its number of gap incidences. Every disk has positive boundary length and every occurrence is paired, so every boundary component of RR encounters a band and ℓQ≥1\ell_Q \ge1.

The neighborhood RR retracts to the graph with N0N_0 vertices and EE edges. Additivity of Euler characteristic when surfaces are glued along boundary circles therefore gives

χ(R)=N0−E,∑Qχ(Q)=2−N0+E,∑QℓQ=2E.\chi(R)=N_0-E,\qquad\sum_Q\chi(Q)=2-N_0+E,\qquad\sum_Q\ell_Q=2E.

In particular,

∑Q(ℓQ−2χ(Q))=2N0−4.\sum_Q\left(\ell_Q-2\chi(Q)\right)=2N_0-4.

This identity does not require RR to be connected; the regions QQ may have several boundary components.

Call a gap good if its region QQ is a disk digon whose two sides belong to distinct bands. The two corners of such a digon are opposite good gaps. Figure 2 shows how coherent boundary orientations reverse the order of occurrences across such a digon.

A good gap and its opposite gap, shown locally between two distinct bands

Figure 2. A good gap and its opposite gap, shown locally between two distinct bands. The complementary region QQ is a disk digon. The coherent boundary orientations reverse the order of the paired occurrences: e,fe, f on one boundary correspond to f′,e′f', e' on the other. Thus an indexing or splitting cut at a good gap must also cut its opposite gap, so that the remaining runs pair as whole intervals. The symbols denote occurrences, not underlying edges of Γ\Gamma; shading only distinguishes disk portions and bands in the surface.

Let BB be the number of gaps that are not good. We bound BB by treating the possible complementary regions as follows.

A disk monogon has one gap between two occurrences joined by the same pairing arc. Those neighboring letters are inverse. Immersion rules this out except at the exceptional break, so the number MM of disk monogons is at most one. Their total contribution to (5.1) is −M-M.

A disk digon using the same band twice turns immediately back along that band at an endpoint. The associated gap is the sole gap at a disk with only one incident arc end: otherwise another band end would intervene in its cyclic order. Different such digons use different degree-one gaps. Hence there are at most N0N_0 such digons and at most 2N02N_0 gaps on them.

Every remaining region is either a disk with ℓQ≥3\ell_Q \ge3, or a connected planar surface with at least two boundary components. In the first case ℓQ≤3(ℓQ−2)\ell_Q \le3(\ell_Q - 2); in the second case χ(Q)≤0\chi(Q) \le0, and the stronger inequality ℓQ≤ℓQ−2χ(Q)\ell_Q \le\ell_Q - 2\chi(Q) holds. These regions have positive contributions to (5.1), with total 2N0−4+M2N_0 - 4 + M. Digons contribute zero. It follows that

B≤M+2N0+3(2N0−4+M)≤8N0.B \le M + 2N_0 + 3(2N_0 - 4 + M) \le8N_0.

Across a good digon, the partners of consecutive occurrences e,fe, f occur consecutively in the opposite order f′,e′f', e'. Taking opposite corners is thus an involution on good gaps. Cut every original boundary at every non-good gap. Also mark its prescribed indexing gap, using the break on the exceptional boundary, and mark all gaps used in dividing the paths into the designated pieces. These extra marks number at most N0+N′N_0 + N'. For each marked good gap, cut both it and its opposite gap. The resulting cut set is stable under the good-gap involution, and its cardinality JJ satisfies

J≤B+2(N0+N′)≤12N′.J \le B + 2(N_0 + N') \le12N'.

Every boundary has a cut, so the remaining consecutive runs of occurrences are linear intervals. All of them lie within designated pieces. Pairing reverses each uncut adjacency, and stability of the cuts ensures that it takes a whole maximal run onto another whole maximal run. A run cannot be paired with itself. For an odd-length run this would fix its middle occurrence, whereas occurrences are paired in distinct twos. For an even-length run it would pair the two middle occurrences and make their adjacent letters inverse. That contradicts immersion inside the run; the exceptional break has been cut. The JJ runs therefore pair in distinct twos, giving at most J/2≤6N′J/2 \le6N' interval pairs as claimed.

A recursive separator bound

Once a long boundary has been divided into pieces of controlled length, deleting a small fraction of the pieces loses only a small fraction of all occurrences. The following consequence of the planar separator theorem, also used in [13] Lemma 4.4, makes the remaining groups of pieces bounded in size.

Lemma 5.5 (Recursive planar separation). Let

Csep=221−2/3.C_{\mathrm{sep}} = \frac{2\sqrt{2}}{1-\sqrt{2/3}}.

For every integer K0≥1K_0 \ge1, a finite planar multigraph with N′N' vertices has a set of at most CsepN′/K0C_{\mathrm{sep}}N'/\sqrt{K_0} vertices whose deletion leaves every connected component with at most K0K_0 vertices.

Proof. Deleting loops and replacing parallel edges by single edges preserves the components after every possible vertex deletion, so it suffices to consider a simple planar graph. The Lipton–Tarjan separator theorem [9] gives, for a simple planar graph on ss vertices, a set of at most 22s2\sqrt{2s} vertices whose removal leaves components with at most 2s/32s/3 vertices. Apply this theorem recursively to each component with more than K0K_0 vertices, starting separately on the original connected components.

At a recursive call on s>K0s > K_0 vertices, charge each of those vertices 22/s2\sqrt{2}/\sqrt{s}. The total charge at that call is 22s2\sqrt{2s} and bounds the number of vertices removed there. Follow any fixed original vertex through the calls containing it, until it is deleted or belongs to a component of size at most K0K_0. The successive charged component sizes decrease by a factor at most 2/32/3. Reading backwards from the last charged size, which is greater than K0K_0, bounds its total charge by

22K0∑j≥0(2/3)j/2=CsepK0.\frac{2\sqrt{2}}{\sqrt{K_0}}\sum_{j\ge0}(2/3)^{j/2}=\frac{C_{\mathrm{sep}}}{\sqrt{K_0}}.

This applies also to a vertex deleted by a separator. Summing the charges over all N′N' original vertices bounds the total number deleted and proves the lemma.

Extracting one bounded path system

We now combine these tools. The original paths will first be divided and closed, then separated into clusters. We retain a cluster whose proportion of unpaired occurrences and number of interval pairs are both small. Controlling the total losses, rather than those of every cluster, is enough to find one such cluster.

Proof of Theorem 5.2. Let ε>0\varepsilon> 0 be the constant in Theorem 4.1, independent of its fixed bounds K0K_0, CC, II. Fix dd from Proposition 3.4 and D0D_0 from Lemma 5.3. We will cut long boundaries into pieces with at most ULUL original occurrences, pay at most D0LD_0L to close each cut piece, and delete at most an η\eta fraction of the pieces. We choose UU large enough to make the closure overhead small and η\eta small enough to control the occurrences lost in separation. Specifically, choose the following constants in order:

U≥max⁡{3,⌈96D0/ε⌉},U an integer,η=min⁡{1/(32U),ε/(64U)},K0=max⁡{1,⌈(Csep/η)2⌉},C=K0(U+D0),I=⌈192C⌉.(28)\begin{aligned} U &\ge\max\{3,\lceil96D_0/\varepsilon\rceil\}, && U\text{ an integer},\\ \eta&= \min\{1/(32U),\varepsilon/(64U)\}, && K_0=\max\{1,\lceil(C_{\mathrm{sep}}/\eta)^2\rceil\},\\ C &= K_0(U+D_0), && I=\lceil192C\rceil. \tag*{(28)} \end{aligned}

In particular,

3D0U≤ε32,2ηU≤116,2ηU≤ε32.(29)\frac{3D_0}{U}\le\frac{\varepsilon}{32},\qquad2\eta U\le\frac{1}{16},\qquad2\eta U\le\frac{\varepsilon}{32}. \tag*{(29)}

All these constants are fixed before n=vmn=vm tends to infinity through m≡1(mod4)m\equiv1\pmod{4}. Their order of dependence is

(types,c0,δ) ;(ε,d) ;D0 ;U ;η ;K0 ;(C,I) ;n.(\text{types},c_0,\delta)\ ;\quad(\varepsilon,d)\ ;\quad D_0\ ;\quad U\ ;\quad\eta\ ;\quad K_0\ ;\quad(C,I)\ ;\quad n.

Suppose there is a reduced spherical arrangement on an outcome satisfying the diameter bound. Let N0N_0 be its number of boundaries and H0H_0 their total length. An ordinary boundary is present, and girth gives H0≥LH_0\ge L.

Keep every path of length at most ULUL intact. For a longer path of length hh, put r=⌈h/(UL)⌉r=\lceil h/(UL)\rceil and divide it into rr consecutive segments whose integer lengths differ by at most one. For large LL each segment has length between UL/3UL/3 and ULUL: h/r>UL/2h/r>UL/2, so ⌊h/r⌋≥UL/3\lfloor h/r\rfloor\ge UL/3 when UL≥6UL\ge6, while ⌈h/r⌉≤UL\lceil h/r\rceil\le UL. Use the linear order from the root on an exceptional path, so no segment crosses its break. Close each segment of every path that was split using Lemma 5.3. Every newly appended occurrence is left unpaired; intact paths receive no added edges.

Let N′N' be the number of resulting paths, and let HaddH_{\mathrm{add}} be their total added length. Each resulting path contains at most ULUL original occurrences and has total length at most (U+D0)L(U+D_0)L. Since a split path contributes at most 3h/(UL)3h/(UL) pieces,

Hadd≤3D0UH0.H_{\mathrm{add}}\le\frac{3D_0}{U}H_0.

Every piece has at least LL original occurrences, by girth for intact ordinary paths and by UL/3≥LUL/3\ge L for split paths, except possibly the one intact exceptional path. Thus

N0≤N′,N′L≤H0+L≤2H0.N_0\le N',\qquad N'L\le H_0+L\le2H_0.

If the exceptional path was split, all its pieces have become closed cyclically immersed paths. Otherwise it remains a single immersed interval starting at its original root.

Apply Lemma 5.4 before the closures are appended. The original pairing is specified by at most 6N′6N' interval pairs, each lying in its designated pieces. Choose the indexing points of intact ordinary paths as in that lemma; index every newly closed path with its original segment followed by its closure. The interval comparisons therefore remain valid in the indexed resulting paths.

Form a multigraph whose vertices are the N′N' pieces and whose edges are the original pairing arcs. It is planar: within each old disk, replace its vertex by one vertex for each consecutive block of arc ends belonging to a piece. Each block can be connected to its new vertex inside a separate sector of the disk. This produces disjoint connections, also for original arcs with both ends at the same disk. The appended closures have no pairing arcs and play no role in this embedding.

By Lemma 5.5 and the choice of K0K_0, delete at most ηN′\eta N' vertices, leaving components with at most K0K_0 pieces. Call these components clusters. If MdelM_{\mathrm{del}} is the number of original occurrences in deleted pieces, then

Mdel≤ηN′UL≤2ηUH0.M_{\mathrm{del}}\le\eta N'UL\le2\eta UH_0.

Keep an original pairing precisely when both of its pieces survive. At most MdelM_{\mathrm{del}} surviving original occurrences lose their partners, because each deleted occurrence had just one partner. An interval pair is either wholly retained or wholly discarded: each of its two intervals lies in one piece. Every retained pair belongs to a single cluster.

For each cluster ZZ, denote its total path length by HZH_Z, including added closures, its number of unpaired occurrences by bZb_Z, and its number of retained interval pairs by IZI_Z. Equations 5.5–5.7 and the parameter choices give

∑ZHZ≥H0−Mdel≥15H0/16,HZ≤K0(U+D0)L=CL,∑ZbZ≤Mdel+Hadd≤εH0/16,∑ZIZ≤6N′≤12H0/L.\begin{aligned} \sum_Z H_Z &\ge H_0-M_{\mathrm{del}}\ge15H_0/16, & H_Z&\le K_0(U+D_0)L=CL,\\ \sum_Z b_Z&\le M_{\mathrm{del}}+H_{\mathrm{add}}\le\varepsilon H_0/16, & \sum_Z I_Z&\le6N'\le12H_0/L. \end{aligned}

These are totals over all remaining clusters; an individual cluster need not yet satisfy the bounded-pattern conditions.

Discard all clusters with bZ>εHZb_Z>\varepsilon H_Z. Their total length is at most ε−1∑ZbZ≤H0/16\varepsilon^{-1}\sum_Z b_Z\le H_0/16. Also discard all clusters with IZ>192HZ/LI_Z>192H_Z/L. Their total length is at most (L/192)∑ZIZ≤H0/16(L/192)\sum_Z I_Z\le H_0/16. After these two exclusions, at least 13H0/1613H_0/16 of cluster length remains.

A cluster with HZ<LH_Z<L contains no positive-length cyclically immersed path, by girth. It can therefore consist only of the one intact exceptional path. There is at most one such cluster. If its length is h<Lh<L, the original arrangement also has an ordinary boundary of length at least LL, so H0≥h+L>2hH_0\ge h+L>2h. Discarding this final cluster, if present, costs less than H0/2H_0/2. A positive total length remains, since 13H0/16−H0/2=5H0/16>013H_0/16-H_0/2=5H_0/16>0.

Choose one remaining cluster. It has at most K0K_0 positive-length paths and satisfies

L≤HZ≤CL,bZ≤εHZ,IZ≤192HZ/L≤192C≤I.L\le H_Z\le CL,\qquad b_Z\le\varepsilon H_Z,\qquad I_Z\le192H_Z/L\le192C\le I.

All paths are cyclically immersed except possibly the entire intact exceptional interval, still starting at xAx_A or xBx_B. The retained comparisons still pair distinct underlying edges. Closures may revisit edges or meet other paths, but their occurrences are all unpaired, which Theorem 4.1 permits. This cluster is therefore a path system excluded by that theorem for the single fixed triple (K0,C,I)(K_0,C,I) in (28).

The construction applies to every finite arrangement, with no bound on N0N_0 or H0H_0, and always yields a system for that same triple. The probability of such a system is o(1)o(1) by Theorem 4.1; the probability that the diameter bound fails is o(1)o(1) by Proposition 3.4. This proves the asserted exclusion probability. The simultaneous girth, diameter, and exclusion requirements consequently have positive probability for all sufficiently large admissible mm.

Cone pictures, asphericity, and protected roots

The probabilistic argument has produced finite immersed graphs for which no reduced spherical arrangement exists. We now turn that exclusion into the two geometric properties needed in Section 2: asphericity of the cone complex and protection of the roots. We give the cone-picture argument of [12], Proposition 5.1 and Corollary 5.3 in full, including the surgeries that preserve a rooted boundary.

Proposition 6.1 (Cone criterion). Let Γ=ΓA∪ΓB\Gamma=\Gamma_A\cup\Gamma_B be a finite graph immersed in the rose FF, with chosen roots xA,xBx_A,x_B, and let XX and GG be defined by (2.1). If Γ\Gamma admits no reduced spherical arrangement as in Definition 5.1, then

π2(X)=0\pi_2(X) = 0 and the root-protection condition (3) holds.

Moreover, XX is a finite aspherical complex of dimension at most two, and GG is finitely presented and torsion-free.

The main issue is to pass from a sphere or a null-homotopy to a reduced arrangement. Its disks will record fillings through cones, and its arcs will record inverse letters in the intervening map to the rose. When a pair of inverse letters traverses the same edge of Γ\Gamma, a band surgery removes that pair. Minimizing the total boundary length makes all such pairs impossible.

Maps represented by cone pictures

For Σ=S2\Sigma= S^2 or D2D^2, a cone picture is a map f:Σ→Xf:\Sigma\to X together with finitely many pairwise disjoint piecewise linear closed disks DiD_i in the interior of Σ\Sigma with the following properties. On the complement of their interiors, ff takes values in FF. For each ii there is a component Λi\Lambda_i of Γ\Gamma and a factorization

f∣Di:Di⟶KΛi⟶Xf|_{D_i}:D_i \longrightarrow K_{\Lambda_i} \longrightarrow X

whose restriction to ∂Di\partial D_i is a specified closed edge path in Λi\Lambda_i. In the disk case we also specify an edge path in Γ\Gamma whose label is read on ∂Σ\partial\Sigma. That path may have distinct endpoints, since all graph vertices map to ∗*.

Lemma 6.2 (Picture representation). Every map S2→XS^2 \to X is homotopic to a cone picture. Every disk map whose boundary is the label of a specified edge path in Γ\Gamma is homotopic relative to that boundary to a cone picture.

Proof. We first give a relative replacement of each cone by ordinary relator disks. Choose a maximal tree in a component Λ\Lambda and a vertex of that tree. The edges outside the tree give a free basis of π1(Λ)\pi_1(\Lambda), represented by based edge loops. Let YΛY_\Lambda be Λ\Lambda with one disk attached along each of these basis loops. Van Kampen’s theorem gives π1(YΛ)=0\pi_1(Y_\Lambda)=0. The cellular boundary map from its two-cells has image the integral cycle group of Λ\Lambda and is injective: the basis loops give a basis of H1(Λ;Z)H_1(\Lambda;\mathbb{Z}). Therefore YΛY_\Lambda has zero reduced integral homology. A simply connected acyclic CW complex is contractible, by the Hurewicz and Whitehead theorems [7].

Both YΛY_\Lambda and KΛK_\Lambda contain Λ\Lambda as a CW subcomplex and are contractible. The identity on Λ\Lambda extends to maps in both directions: extend successively over the relative cells, using the vanishing homotopy groups of the target. The two composites are homotopic to the corresponding identities relative to Λ\Lambda. For this last assertion use the same cell-extension argument on the products with [0,1][0,1], prescribing the homotopy on the two ends and on Λ×[0,1]\Lambda\times[0,1]. Thus the replacements are homotopy equivalences relative to Λ\Lambda, not merely equivalences of their absolute homotopy types. After attachment along Λ→F\Lambda\to F, they give a homotopy equivalence relative to FF between XX and the finite presentation complex obtained from FF by attaching these relator disks.

Here is the picture construction for this presentation complex. Replace the attaching maps by mapping-cylinder collars and subdivide, so that simplicial approximation applies to the surface map. This changes neither the homotopy type relative to FF nor a prescribed boundary word. In the interior of each relator disk choose a point outside the images of the one-dimensional simplices and of the degenerate two-dimensional simplices of the surface. Its preimage is a finite set of points, each with a neighborhood mapped homeomorphically to a neighborhood of the chosen point. By compactness and finiteness of the triangulations, a sufficiently small closed disk about the chosen point has as its entire preimage a disjoint union of such disk neighborhoods.

In each target relator disk, expand that small disk to the full disk and collapse the surrounding annulus radially to its boundary. This map is homotopic to the identity relative to the boundary. Collapse the mapping-cylinder collars to their attaching paths in FF as well. After postcomposition, the surface outside the selected source disks maps into FF, while each source disk maps into one relator disk. Returning through the relative equivalence to XX makes each of these disk maps factor through the corresponding abstract cone. All homotopies fix a prescribed outer boundary. This gives the asserted cone pictures.

We shall also use two elementary changes to a picture. A homotopy of one inner boundary path in its graph can be made on a collar of that boundary. Fill the resulting boundary in the same cone. The new and old fillings, with the collar included, are homotopic relative to the original boundary because the abstract cone is contractible. Thus inner paths can be tightened cyclically. If the result is constant, the inner disk can be removed, filling it by that constant map into FF. An outer path can likewise be tightened with its graph endpoints fixed; the corresponding homotopy of its label is accommodated by a boundary collar.

Length reduction by band surgery

Suppose first that π2(X)≠0\pi_2(X) \ne0. Among cone pictures representing non-null-homotopic spheres, choose one minimizing the sum of the lengths of its inner boundary paths. Alternatively, suppose root protection fails. Fix a root r∈{xA,xB}r \in\{x_A,x_B\} and a distinct vertex zz joined to it by a path with trivial label in GG. Among all cone pictures of null-homotopies of labels of paths from rr to this fixed zz, choose one minimizing the sum of all inner boundary lengths and the outer path length. These minima exist because lengths are nonnegative integers and Lemma 6.2 provides the required pictures. Among pictures attaining the minimum, remove all constant inner boundaries.

The preceding collar changes show that every remaining inner boundary is nonempty and cyclically immersed. In the disk case the outer path is immersed and nonempty, since its endpoints are distinct. There is at least one inner disk. For the sphere case, a map with no such disk would factor through FF, whose universal cover is a tree and whose second homotopy group is zero. For the disk case, a nonempty immersed path in Γ\Gamma has a nonempty freely reduced label word, which cannot bound a disk in FF.

Complete a disk picture to a sphere by adjoining a formal exterior disk D∞D_\infty. Its interior carries no map into XX. Mark its boundary at the initial point of the specified outer path; this is the exceptional break, representing the two endpoints of that path. Choose the orientation of the sphere so that the boundary of D∞D_\infty, starting at the break, reads the path from rr to zz. This choice may reverse all ordinary boundary words, which preserves cyclic immersion. In the sphere case simply orient the sphere and give all disks their induced orientations.

On the complement of these disks, the map takes values in the rose. Put it in piecewise linear general position with respect to one point in the interior of each rose edge, keeping the boundary words fixed. The preimages of these points are disjoint embedded arcs and circles. Every letter occurrence has exactly one arc endpoint. Discard the circles. The arcs pair all occurrences, and paired letters are inverse when read in the oriented disk boundaries: the two ends of a transverse arc have opposite crossing signs, and disk-boundary orientations are opposite to those of the complementary surface.

It remains to show that paired occurrences use distinct underlying edges of Γ\Gamma. Suppose an arc pairs two traversals of the same edge ee. Choose a thin rectangular band around the arc. It maps into a small open interval in the corresponding rose edge and lifts to the interior of the abstract graph edge ee. The lift agrees with both specified boundary lifts at the band ends. Whenever an inner disk meets the band, its cone must therefore be the cone on the component containing ee.

The local shortening is particularly simple in graph paths. Splice the disk boundaries along the two sides of the band and then contract the residual portions of the two paired traversals within ee. This removes two full edge occurrences in total. For ordinary boundaries the changes, with suitable cyclic starting points, are

(eP,e−1Q)⟼PQ,ePe−1Q⟼(P,Q).(30)(eP, e^{-1}Q) \longmapsto PQ,\qquad ePe^{-1}Q \longmapsto(P,Q). \tag*{(30)}

Here e−1e^{-1} denotes the reverse oriented graph edge, rather than merely a letter with the same label. Consequently all concatenations in (30) are paths in the same graph, and the new boundaries are closed. For a rooted exterior boundary the corresponding changes are

(PeR,e−1Q)⟼PQR,PeQe−1R⟼PR.(31)(PeR, e^{-1}Q) \longmapsto PQR,\qquad PeQe^{-1}R \longmapsto PR. \tag*{(31)}

In the second formula QQ is closed at the terminal vertex of ee; in both formulas the resulting exterior path has exactly the original graph endpoints r,zr,z. The contractions along ee are realized by boundary-collar homotopies.

We now specify the resulting surface maps in all four cases. This also explains why the operation retains the failure that was minimized.

If the band joins two distinct inner disks, their union with the band is a disk. The maps on all three pieces factor together through the same abstract cone, since their lifts agree on the attaching intervals. Replace them by this single cone disk and shorten its boundary as in the first formula of (30). The replacement is homotopic to the old map relative to the rest of the surface, and the total boundary length decreases by two. Further tightening can only decrease it. An essential sphere remains essential, and a disk still fills the same exterior word.

If the band joins an inner disk to D∞D_{\infty}, their union is again a disk, now an enlarged exterior disk. Retain its complementary disk and restrict the old map to that complement. Its new boundary is PQRPQR as in the first formula of (31). The resulting picture is a null-homotopy of a path from rr to zz; the old inner boundary and exterior boundary have been replaced by a boundary shorter than their combined length by two.

If both ends of the band lie on D∞D_{\infty}, their union is an annulus in the completed sphere. Its complement consists of two disks. Retain the one whose boundary contains the marked break, as shown in Figure 3. The restricted map on that disk, after the edge-collar contraction, fills the word PRPR in the second formula of (31). Thus this operation uses only a restriction of the existing map; it does not require a separate filling of QQ. It preserves the fixed endpoints and decreases the total length by at least two. The path PRPR cannot tighten to the empty path, because r≠zr \ne z.

Band returning to the formal exterior disk, shown schematically in the domain sphere

Figure 3. A band returning to the formal exterior disk, shown schematically in the domain sphere. The two paired occurrences traverse the same graph edge in opposite directions. The exterior disk and the band form an annulus. Retaining its complementary disk on the break side replaces PeQe−1RPeQe^{-1}R by PRPR with the same graph endpoints: QQ is closed at the terminal vertex of ee, and the restricted picture fills PRPR. Shading denotes the formal exterior disk and band; the exterior disk itself carries no map to XX.

Finally suppose both band ends lie on one inner disk. The union NN of the disk and band is an annulus, and its map factors through the same abstract cone KΛK_{\Lambda}. The complement of NN in the sphere consists of two disks Q1,Q2Q_1,Q_2. Cap each new boundary by a disk mapping through KΛK_{\Lambda}, using the boundary lifts inherited from NN, and shorten these boundary paths to PP and QQ in the second formula of (30). In the rooted case one of Q1,Q2Q_1,Q_2 contains D∞D_{\infty}. Retain that component with its new cap and remove the formal exterior disk. This is another disk picture with the same exterior path. Its total inner boundary length is at most the old total minus two, because the two possible new cap boundaries together have length two less than the old boundary and all other retained disks already belonged to the old picture.

In the sphere case, the same operation gives two capped spheres; at least one must still be essential. To verify this without an ambiguity from choices of caps, lift the original sphere map to the universal cover X~\widetilde{X}. The factorization N→KΛ→XN \to K_{\Lambda} \to X lifts through a single lift KΛ→X~K_{\Lambda} \to\widetilde{X}, chosen to agree with the lifted sphere on NN. Use that very same lift for both new caps. Write f~1,f~2\widetilde{f}_1,\widetilde{f}_2 for the resulting lifted capped spheres, with the orientations induced from Q1,Q2Q_1,Q_2. Their fundamental homology classes satisfy

f~∗[S2]=f~1∗[S2]+f~2∗[S2]in H2(X~;Z).(32)\widetilde{f}_*[S^2] = \widetilde{f}_{1*}[S^2] + \widetilde{f}_{2*}[S^2]\quad\text{in }H_2(\widetilde{X};\mathbb{Z}). \tag*{(32)}

Compute this identity before the boundary-collar shortenings, which are homotopies and do not change these homology classes. The difference of the cycles on the two sides consists of the old annulus and the two caps, with their boundary orientations canceling. This cycle factors through the contractible abstract cone KΛK_{\Lambda}, so its homology class is zero. No assertion that the image of this cone is an embedded contractible subspace is needed. Since X~\widetilde{X} is simply connected, the Hurewicz map π2(X~)→H2(X~;Z)\pi_2(\widetilde{X}) \to H_2(\widetilde{X};\mathbb{Z}) is an isomorphism. The left side of (32) is nonzero, and hence one capped sphere is essential. Its total boundary length is smaller than the original one by at least two.

Figure 4 shows this splitting into two capped spheres and the homology identity that preserves essentiality.

Figure 4. An inner cone disk and its returning band form an annulus, shown schematically in the domain sphere. Here DP,DQD_P,D_Q are its complementary disks, with boundary paths P,QP,Q. Capping both through the same abstract cone produces two spheres. For the original sphere map ff, the symbols [f~][\widetilde{f}] and [f~i][\widetilde{f}_i] denote the second homology classes of its lift and of the two capped spheres in the universal cover. Using for both caps the same lift of KΛ→XK_\Lambda\to X as for the original annulus gives the displayed identity. If ff is essential, at least one capped sphere remains essential. Shading denotes the annulus and caps in the domain, without asserting that their images embed in XX.

Each case contradicts minimality. The chosen pairing therefore uses distinct underlying graph edges. All the other requirements of Definition 5.1 have already been verified: the ordinary boundaries are positive and cyclically immersed, there is at least one such boundary, and the only possible exceptional boundary is a positive immersed path starting at a designated root. Thus either failure would give a reduced spherical arrangement. Its assumed absence proves both π2(X)=0\pi_2(X)=0 and root protection.

The finite aspherical complex and torsion

For completeness, we finish the two standard consequences needed in Proposition 6.1. The universal cover X~\widetilde{X} is simply connected, and the vanishing of π2(X)\pi_2(X) gives H2(X~;Z)=0H_2(\widetilde{X};\mathbb{Z})=0 by Hurewicz. Its higher cellular homology groups vanish because its dimension is at most two. Thus it is simply connected and acyclic. If it had a nonzero homotopy group, the first such group would, by Hurewicz, give a nonzero homology group. All homotopy groups therefore vanish, and Whitehead’s theorem makes X~\widetilde{X} contractible. Hence XX is aspherical. Its finite two-dimensional CW structure gives a finite presentation for GG.

The cellular chains of this contractible universal cover give a free resolution over ZG\mathbb{Z}G,

0⟶C2(X~)⟶C1(X~)⟶C0(X~)⟶Z⟶0.0 \longrightarrow C_2(\widetilde{X}) \longrightarrow C_1(\widetilde{X}) \longrightarrow C_0(\widetilde{X}) \longrightarrow\mathbb{Z} \longrightarrow0.

If GG had a nonidentity element of finite order, a power of that element would generate a cyclic subgroup CℓC_\ell of prime order ℓ\ell. Restricting this resolution to ZCℓ\mathbb{Z}C_\ell still gives a free resolution of length at most two: ZG\mathbb{Z}G is a free left ZCℓ\mathbb{Z}C_\ell-module, with basis given by representatives for the cosets CℓgC_\ell g in GG. It would follow that Hk(Cℓ;Fℓ)=0H^k(C_\ell;\mathbb{F}_\ell)=0 for every k>2k>2.

To see the contradiction directly, write uu for a generator of CℓC_\ell and N=1+u+⋯+uℓ−1N=1+u+\cdots+u^{\ell-1}. The periodic free resolution

⋯→NZCℓ→u−1ZCℓ→NZCℓ→u−1ZCℓ⟶Z⟶0\cdots\xrightarrow{N} \mathbb{Z}C_\ell\xrightarrow{u-1} \mathbb{Z}C_\ell\xrightarrow{N} \mathbb{Z}C_\ell\xrightarrow{u-1} \mathbb{Z}C_\ell\longrightarrow\mathbb{Z} \longrightarrow0

is exact: the augmentation ideal is the image of multiplication by u−1u-1, the kernel of that multiplication is ZN\mathbb{Z}N, and the kernel of multiplication by NN is the augmentation ideal. Applying Hom⁡ZCℓ(−,Fℓ)\operatorname{Hom}_{\mathbb{Z}C_\ell}(-, F_\ell) with trivial coefficients makes every differential zero, since u−1u-1 acts as zero and NN acts as ℓ=0\ell=0. Therefore Hk(Cℓ;Fℓ)≅FℓH^k(C_\ell; F_\ell) \cong F_\ell for all k≥0k \ge0, the standard cohomological obstruction to torsion in a group of finite cohomological dimension [3]. This contradiction proves that GG is torsion-free and completes the proof of Proposition 6.1.

Completion of the construction

We now choose one finite pair of graphs and apply the deterministic results.

Proof of Theorem 1.1. Use the prescribed types of Section 3 and let m≡1(mod4)m \equiv1 \pmod{4} tend to infinity. The probability space conditioned on girth at least L=⌊c0log⁡(vm)⌋L = \lfloor c_0 \log(vm) \rfloor is nonempty for sufficiently large mm. By Theorem 5.2, with probability tending to one it contains no reduced spherical arrangement. Choose such an outcome with L≥3L \ge3, so that both labeled graphs have no loops or parallel edges.

Attach the cones to the rose as in Section 2, obtaining the finite two-dimensional complex XX, and put G=π1(X)G = \pi_1(X). By Proposition 6.1, the universal cover of XX is contractible, GG is torsion-free, and the labels of paths from either root to a different vertex of its component are nontrivial in GG. Finiteness of XX gives a finite presentation of GG.

The intersection parities proved in Proposition 3.1 now satisfy the hypotheses of Proposition 2.1. That proposition supplies a,b,c∈F2[G]a,b,c \in\mathbb{F}_2[G] with ab=1ab=1, ac=0ac=0, and c≠0c \ne0. Associativity excludes ba=1ba=1, as asserted.

The argument selects a finite matching outcome rather than listing its edges. Once selected, its cones give a finite presentation, and the sums in Proposition 2.1 give finite scalar witnesses.

References

  1. [1][AOP02] Pere Ara, Kevin C. O’Meara, and Francesc Perera. Stable finiteness of group rings in arbitrary characteristic. Advances in Mathematics, 170(2):224–238, 2002.
  2. [2][Ber19] Vadim Yu. Bereznyuk. Asphericity of groups defined by graphs. Mathematical Notes, 105(3):316–328, 2019.DOI
  3. [3][Bro82] Kenneth S. Brown. Cohomology of Groups, volume 87 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1982.
  4. [4][DHJ15] Ken Dykema, Timo Heister, and Kate Juschenko. Finitely presented groups related to Kaplansky’s direct finiteness conjecture. Experimental Mathematics, 24(3):326–338, 2015.arxiv.org/abs/1112.1790
  5. [5][ES04] Gábor Elek and Endre Szabó. Sofic groups and direct finiteness. Journal of Algebra, 280(2):426–434, 2004.
  6. [6][Gro03] Mikhail Gromov. Random walk in random groups. Geometric and Functional Analysis, 13(1):73–146, 2003.DOI
  7. [7][Hat02] Allen Hatcher. Algebraic Topology. Cambridge University Press, Cambridge, 2002.
  8. [8][Kap72] Irving Kaplansky. Fields and Rings. Chicago Lectures in Mathematics. University of Chicago Press, Chicago, second edition, 1972.
  9. [9]Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.
  10. [10]M. Susan Montgomery. Left and right inverses in group algebras. Bulletin of the American Mathematical Society, 75(3):539–540, 1969.DOI
  11. [11]Yann Ollivier. On a small cancellation theorem of Gromov. Bulletin of the Belgian Mathematical Society–Simon Stevin, 13(1):75–89, 2006. Revised preprint, version 2, September 25, 2024.arxiv.org/abs/math/0310022
  12. [12]OpenAI. A Counterexample to Kaplansky’s Direct-Finiteness Conjecture in Characteristic Two. OpenAI Math Release preprint OAI:A-Counterexample-to-Kaplanskys-Direct-Finiteness-Conjecture-in-Characteristic-Two-September-23-2026, 2026.
  13. [13]OpenAI. A Torsion-Free Group Algebra with Zero Divisors. OpenAI Math Release preprint OAI:A-Torsion-Free-Group-Algebra-with-Zero-Divisors-September-23-2026, 2026.

Paper details

vlnc:W_sg7x2r6w
Version
v1 · latest
Published
License
LicenseRef-OpenAI-public
Usage

views · 39

downloads · 2

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

  • Mathematics

unreleased internal OpenAI model

View statement
Looking for related papers…
Contents