What is G₃(k, n)?

Vertices are all binary strings of length n with exactly k zeros. Two vertices are adjacent when a consecutive 3-cycle on positions (i, i+1, i+2) — either forward (right rotation: new[i]=s[i+2], new[i+1]=s[i], new[i+2]=s[i+1], i.e. (a,b,c)→(c,a,b)) or reverse (left rotation: new[i]=s[i+1], new[i+1]=s[i+2], new[i+2]=s[i], i.e. (a,b,c)→(b,c,a)) — changes the string. An edge exists only when the triple is not all-0 or all-1. The graph has |V| = C(n,k) vertices and 2(n−2) generator types. G₃ is denser than G₂ and has diameter roughly half that of G₂.

Distance Formulas

Let A = 0^k1^n−k (canonical vertex), B with 1-based zero positions z₁<…<zₖ. Define dᵢ = zᵢ−i, I(B) = Σdᵢ, Δ(B) = |Σ(−1)ⁱ⁺¹(dᵢ mod 2)|.

No closed-form exact formula is known for d(X,Y) between arbitrary vertices. The app uses BFS for exact distances and displays the two-sided bounds.

Controls — Left Panel

• n — string length (3–15). k — zeros per string; |V| = C(n,k).
• Wrapped (n−2,n−1,0) — adds the 3-cycle wrapping the last two positions with position 0.
• ▶ Generate — rebuild graph; resets all pins, stretch offsets, and sort mode.
• 🎯 Sort Vertices — enter BFS-root pick mode (see below).
• 📏 d(X,Y) — open distance calculator (see below).
• Node Color — four coloring modes (see below).
• Show generator labels — draw a small ▶N / ◀N pill at the midpoint of each edge showing the position index and direction.
• Show all holography — when checked, every node shows its lattice-path diagram at all times; when unchecked, the diagram appears only on hover (see Holography).
• Show I(B) formula — adds a per-term I(B)=Σ(zᵢ−i) expansion inside each holography tooltip.
• Node Radius, Repulsion, Attraction — physics tuning.
• Analysis font (px) — scales all text in the right panel (8–18 px).
• Edge label font (px) — scales the generator label pills on edges (7–16 px).
• 🔀 Shake & Resettle — randomise positions, re-enable mirror symmetry.
• Keep symmetric — mirrors each node with its string-reversal partner across the vertical centre line during physics and drag.
• 📌 Stretch (pin nodes) — enter stretch mode: drag nodes to pin them; drag edge handles to bend edges (see Stretch Mode).
• ❄ Freeze — instantly halt physics; A and A* get text callouts.

Node Coloring — Four Modes

1 — By degree: color = number of incident edges.

2 — d from A: BFS distance from A. Green (d=0, A itself shown gold) → red (d=diam=A*).

3 — d from A*: same gradient rooted at A* (complement of mode 2).

4 — d from clicked: live BFS from any node you click.

Green ring = A   Purple ring = A*   Gold fill = source   Orange fill = target   Blue ring = d(X,Y) nodes

Red square nodes — see U′ Approximation below.

Edge Coloring & Labels

Color = 3-cycle position index i (10-color palette). Solid stroke = forward rotation (right rotation: (a,b,c)→(c,a,b)). Dashed stroke = reverse rotation (left rotation: (a,b,c)→(b,c,a)). Multiple edges between the same pair of nodes are fanned out with perpendicular offsets so they don't overlap.

When Show generator labels is on, each edge shows a small pill at its visual midpoint: ▶2 = forward 3-cycle at position 2, ◀2 = reverse, ▶3w = wrapped generator.

📌 Stretch Mode — Pinning Nodes & Bending Edges

Check Stretch (pin nodes) to enter stretch mode (cursor changes to a cell crosshair).

• Drag a node → it is pinned in place (red dashed ring + "P" dot). Pinned nodes are immune to physics forces; unpinned nodes settle around them.
• Click a pinned node (without dragging) → unpins it.
• Drag an edge handle (orange dot at the edge midpoint, offset perpendicularly from any generator label) → bends that edge into a Bézier arc. The handle position sets the control-point offset.
• Click an edge handle (without dragging) → resets the edge to its automatic shape.
• ✕ Clear all pins button appears when any node is pinned; click to release all at once.

With Keep symmetric on, pinning a node simultaneously pins its reversal partner at the mirror position.

❄ Freeze

Instantly stops physics and zeros all velocities. A and A* receive leader-line callouts so they are easy to identify. Press ▶ Unfreeze to resume. Useful before Sort Vertices or d(X,Y) on large graphs.

🎯 Sort Vertices

Click the button, then click any node U as the BFS root. Nodes partition into layers L_d = {v : d(U,v) = d}.

• ⬤ Rings — U at center, each layer on a concentric annular band. White disc background with black boundary circles labeled d= / c= (layer index / count) on left and right.
• ≡ Rows — layers as horizontal bands; nodes ordered within each row by the barycenter heuristic to reduce crossings. ▼ / ▲ toggles direction. d= / c= badges on the left margin.

Node radius auto-scales so nodes fit inside their band. A small verification block shows BFS vs formula d(U,A) and d(U,A*). Holography tooltips remain active in both sub-modes.

📏 d(X,Y) Calculator

Click the button, then click two nodes on the graph (they highlight with a blue ring) or type their binary labels. Press ↳ Compute.

• d(X,Y) — exact BFS distance.
• N_o(X,Y) — number of shortest paths (BFS layer-counting).
• N_p(X,Y) — number of all simple paths (DFS backtracking, capped at 1,000,000).

The bounds ⌈½Σ|xᵢ−yᵢ|⌉ ≤ d ≤ Σ⌈|xᵢ−yᵢ|/2⌉ are also displayed. After computing, click any node to start a new query.

◻ Holography — Lattice Path Diagrams

For each binary string B = b₁b₂…bₙ with k zeros, a k × (n−k) rectangle encodes the string as a lattice path:

• Start at the lower-left corner.
• 0 → step right. 1 → step up. End at the upper-right corner.
• Cells below the red path are shaded pink. Their count is I(B) = Σ(zᵢ−i) — the area statistic.

The label below reads A=N (Area = I(B)). With Show I(B) formula on, the per-term breakdown (z₁−1)=d₁ … is shown above it.

Hover any node to see its diagram (works in free layout, Rings, and Rows modes). Check Show all holography to display all diagrams simultaneously.

◻ U′ Approximation — Red Squares

For each node X, define U = I(B) (the lattice-path area) and U′ = ⌈U/2⌉. The exact formula gives d(A,X) = (I(B)+Δ(B))/2, so U′ = ⌈I/2⌉ is the "naïve" approximation that ignores the parity correction Δ.

When U′ ≠ d(A,X), the node is drawn as a red square instead of a colored circle. This happens precisely when Δ(B) > I(B) mod 2 — i.e., when the alternating parity sum contributes a non-trivial correction. For k=1 the approximation is always exact (no squares). For k≥2 squares appear at nodes where the correction term is non-zero.

Formula & Diameter Verification

At build time the app checks d(A,B) = (I(B)+Δ(B))/2 for every vertex B and displays a green ✓ or red ⚠ pill in the right panel. When |V| ≤ 350 the diameter ⌈k(n−k)/2⌉ is also BFS-verified.