LemmaStatement: AI-generatedProof: AI-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Stack construction of closed walks with loops and repeated edges

Statement

Let $A$ be a finite $d$ -regular adjacency-slot matrix, with $d \geq 2$ , and fix a vertex $v$ . For every integer $k \geq 1$ there are at least $C_{k} (d - 1)^{k}$ closed labelled walks of length $2 k$ starting at $v$ . Slot labels and their reversal are as in Reversible labels for adjacency slots, and $C_{k}$ is the Dyck-word count in Dyck words and elementary Catalan growth. Arbitrary diagonal slot counts and parallel slots are allowed.

Facts & Assumptions

Given: The objects and hypotheses in the statement.

Goal: Establish every assertion in the statement.

[F1]

Each vertex has $d$ outgoing labels, and reversal is an involution exchanging endpoints; fixed loop labels are permitted (Reversible labels for adjacency slots).

[F2]

There are $C_{k}$ Dyck words of length $2 k$ , each having exactly $k$ positive symbols (Dyck words and elementary Catalan growth).

Proof

1.1F1F2construct

Fix a Dyck word, start at $v$ , and keep a stack of labels, initially empty. At a positive symbol choose any outgoing label if the stack is empty; otherwise exclude exactly the reversal of the top label. Traverse the chosen label and push it. At a negative symbol traverse the reversal of the top label and pop it. Inductively the current vertex is the terminal vertex of the stack path starting at $v$ . The Dyck condition ensures a top label exists at each negative symbol. At the end the stack is empty and the walk ends at $v$ . Every positive symbol has at least $d - 1$ choices, and negative symbols are forced.

2.1F1F2step 1.1constructalgebra∎

The resulting labelled walk uniquely determines its Dyck word and every choice. Indeed, reconstruct the stack from the empty stack: at an empty stack a step must be a push; at a nonempty stack a label equal to the reversal of its top must be a pop, and any other label must be a push. The construction prohibited precisely that reversal at a push. This deterministic decoding also works when a loop label is its own reversal, because labels, rather than endpoints alone, are compared. Thus different Dyck words or different choices cannot produce the same labelled walk. There are at least $C_{k} (d - 1)^{k}$ such walks, as claimed.

Depends on

Used by · 1

Extracting a nonconstant eigenvalue from closed-walk moments

Dependency tree · 2 levels

Each result is drawn at its shortest distance from this item. Arrows run from prerequisites to the items that use them; this item has a heavier outline. External source nodes link directly to the cited text. The view shows up to two dependency steps; open a prerequisite to continue.