What is G₃(k, n)?

Vertices are all binary strings of length n with exactly k zeros — there are C(n,k) of them. Two vertices are adjacent when a consecutive 3-cycle on positions (i, i+1, i+2) transforms one string into the other. There are two generator families:

• Forward σᵢ⁺ — right rotation: (a,b,c) → (c,a,b). Drawn as solid lines, ▶iF label (green).
• Reverse σᵢ⁻ — left rotation: (a,b,c) → (b,c,a). Drawn as dashed lines, ◀iR label (orange).

Note: σᵢ⁻ = (σᵢ⁺)⁻¹, so each undirected edge corresponds to exactly one position i. An edge exists only when the triple is not all-0 or all-1 (constant triples are fixed points). G₃ is a multigraph — two nodes can share parallel edges at different positions.

Edge Label Convention

Each undirected edge is labeled by the generator applied from the lower-indexed endpoint to the higher-indexed endpoint. For example, ◀2R on the edge {1101111, 1111011} means: going from 1101111 (lower index) → 1111011 uses σ₂⁻ (reverse at position 2). The label does not imply a directed edge — traversing in the opposite direction uses σ₂⁺.

Wrapped generator (position n−2, wrapping back to 0) is suffixed with w: e.g. ▶3wF.

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 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

• ↺ Reset — restore defaults: n=5, k=2, all checkboxes off, color mode = By degree.
• 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 — five coloring modes (see below).
• Show Nₒ(A,·) table — show or hide the shortest-path count heatmap table in the right panel.
• Show generator labels — draw a colour-coded pill at the midpoint of each edge: ▶NF (green = forward) or ◀NR (orange = reverse), where N is the position index.
• Show all holography — every node shows its lattice-path diagram at all times; when unchecked, the diagram appears only on hover.
• Show mismatch only — show holography diagrams exclusively for mismatch nodes (red squares). Each diagram shows U= and m= values.
• Show I(B) formula — adds a per-term I(B)=Σ(zᵢ−i) expansion inside each holography tooltip.
• Node Radius, Repulsion, Attraction — physics tuning sliders.
• Holo cell size — scales the holography lattice diagram (6–40 px per cell, default 16). Path stroke width, dots, and labels all scale proportionally.
• Analysis font — scales all content in the right panel uniformly via CSS zoom (8–18 px, baseline 11 px).
• Edge label font — 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. This is a layout heuristic, not the true graph automorphism geometry: reversal pairs are forced to the same y-coordinate at ±x from the centre.
• 📌 Stretch (pin nodes) — enter stretch mode: drag nodes to pin them; drag edge handles to bend edges (see Stretch Mode).
• 📷 Export PNG — saves the canvas as G3_k{k}_n{n}.png. Tip: freeze the layout first for a clean snapshot.
• ❄ Freeze — instantly halt physics; A and A* get text callouts.

Node Coloring — Five Modes

1 — By degree: color = number of incident edges (parallel edges each counted separately).

2 — d from A: BFS distance from canonical A. Green (d=0) → red (d=diam, at A*).

3 — d from A*: same gradient rooted at A*.

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

5 — Nₒ from A (heatmap): log-scale color of the shortest-path count Nₒ(A,·). Blue = 1 path → cyan → green → yellow → red = maximum.

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

Red square nodes — see U′ Approximation below.

Edge Coloring

Color = 3-cycle position index i (10-color palette, consistent across all graphs). Solid stroke = forward generator σᵢ⁺. Dashed stroke = reverse generator σᵢ⁻. Parallel edges between the same node pair are fanned out with perpendicular offsets so they don't overlap visually.

📌 Stretch Mode — Pinning Nodes & Bending Edges

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

• Drag a node → pins it in place (red dashed ring + "P" dot). Pinned nodes are immune to physics forces.
• Click a pinned node (without dragging) → unpins it.
• Drag an edge handle (dot at the edge midpoint) → bends the edge into a Bézier arc.
• Click an edge handle (without dragging) → resets the edge to its automatic shape.
• ✕ Clear all pins — releases all pinned nodes 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. 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. Black circles labeled d= (layer) / c= (count).
• ≡ Rows — layers as horizontal bands ordered by barycenter heuristic. ▼ / ▲ toggles direction.

Node radius auto-scales so nodes fit inside their band. Holography tooltips remain active in both sub-modes.

📏 d(X,Y) Calculator

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

• d(X,Y) — exact BFS distance.
• N_o(X,Y) — number of shortest paths (BFS layer-counting, deduplicated for multigraph).
• N_p(X,Y) — number of all simple paths (DFS backtracking, capped at 1,000,000).
• Two-sided bounds ⌈½Σ|xᵢ−yᵢ|⌉ ≤ d ≤ Σ⌈|xᵢ−yᵢ|/2⌉ are displayed alongside.

◻ Holography — Lattice Path Diagrams

Each binary string B maps to a lattice path in a k × (n−k) rectangle: 0 → step right, 1 → step up. Cells below the red path are shaded pink; their count equals I(B) = U (the Mann–Whitney U statistic).

The tooltip shows U=N (area). With Show I(B) formula, the per-term breakdown is shown. Use the Holo cell size slider (right panel) to enlarge diagrams — default is 16 px per cell.

Hover any node for its diagram, or use the checkboxes to show all / mismatch-only simultaneously.

◻ U′ Approximation & Mismatch (Red Squares)

The "naïve" approximation U′ = ⌈I(B)/2⌉ ignores the parity correction Δ(B). When U′ ≠ d(A,B), the node is drawn as a red square. The mismatch value is:

Enable Show mismatch only to display holography diagrams for mismatch nodes only — each diagram shows both U= and m= values. The mismatch box border turns red for easy identification.

Closed-form mismatch count for k = 3 and k = 4:

Nₒ(A,·) Heatmap Table

Enable Show Nₒ(A,·) table to display a sortable table in the right panel listing every vertex B with its distance d, area I(B), parity correction Δ, and shortest-path count Nₒ(A,B). Color swatches use the same log-scale heatmap as the Nₒ node coloring mode.

Two auto-computed badges indicate whether Nₒ(A,B) is determined solely by I(B) or by the pair (I,Δ) — useful for identifying potential closed-form structure.

Formula & Diameter Verification

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

Keyboard Shortcuts

• Esc — exit Sort Vertices pick mode or d(X,Y) calculator.