What is G₂(k, n)?

Vertices are all binary strings of length n with exactly k zeros — equivalently, k-element subsets of {1,…,n}. Two vertices are adjacent when swapping two neighboring positions (i, i+1) changes the string (one is 0, the other 1). The graph has |V| = C(n,k) vertices and is the Schreier coset graph of S_n over S_k × S_n−k.

Distance Formulas

Let z_i = 1-based position of the i-th zero. A = 0^k1^n−k is the canonical vertex; A* = 1^n−k0^k is its antipode.

Selecting source = A in the right panel shows the full I(B) term-by-term breakdown. For an arbitrary source, the general Σ|xᵢ−yᵢ| formula is expanded.

Controls — Left Panel

• n — string length (2–15). Larger n may have C(n,k) > 350 vertices, which skips the full BFS-diameter check.
• k — number of zeros per string (paper convention); |V| = C(n,k).
• Wrapped (0, n−1) — adds the generator swapping positions 0 and n−1, shown dashed in the legend.
• ▶ Generate — rebuild graph with new n, k. Resets freeze and sort mode.
• 📐 Grid (k=2) — place nodes on a grid with axes z₁, z₂ (zero positions). Only valid when k=2; occupied region is z₁ < z₂.
• 🎯 Sort Vertices — enter BFS-root pick mode; see Sort Vertices section below.
• 📏 d(X,Y) — compute distance and path counts between two chosen nodes; see d(X,Y) section below.
• Node Color — radio group with four coloring modes; see Node Coloring section below.
• Node Radius — visual node size in pixels.
• Repulsion / Attraction — tune the force-directed physics.
• 🔀 Shake & Resettle — randomise positions and restart physics. Enables mirror-symmetry mode.
• Keep symmetric — when checked, dragging a node also mirrors its reversal partner B↔reverse(B) across the vertical center line. Shake always enables this.
• ❄ Freeze — instantly halt all physics. A and A* are labeled with callouts. Press again to resume. Useful for large graphs (e.g. n=10, k=4) that take a long time to settle.

Node Interaction (free layout)

• Click a node → selects it as source. All nodes recolor by BFS distance from source (green=near, red=far, gold=source).
• Click a second node → selects it as target. Right panel shows d(src,tgt), the distance formula breakdown, and the shortest path with highlighted edges.
• Click the source again → deselects everything.
• Click empty canvas (with both selected) → starts a new source pick.
• Drag a node → moves it; physics resumes after release. If Keep Symmetric is on, the reversal partner moves simultaneously.

Node Coloring — Four Modes

Switch modes with the Node Color radio buttons in the left panel. Rings on A and A* are always visible regardless of mode.

1 — By degree (default)

Color = degree (number of incident edges = count of 01/10 bigrams in the string). A and A* always have degree 1.

2 — d from A

Color = BFS distance from A, precomputed at build time. Green (d=0, A itself, gold) → red (d=k(n−k), which is always A*). Visualises the I-statistic I(B) = Σ(zᵢ−i) across the whole graph. Click-independent.

3 — d from A*

Exact complement of mode 2: color = BFS distance from A*. A* is gold; A is red. Nodes that were green in mode 2 are now red and vice versa.

4 — d from clicked source

BFS from whichever node you click. Gradient updates live. Falls back to degree coloring until a source is picked.

Permanent overlays (all modes)

• Green double-ring + large black label — canonical A = 0^k1^n−k.
• Purple double-ring + large black label — antipodal A* = 1^n−k0^k, always at distance k(n−k) from A.
• Gold ring + fill — selected source.
• Orange ring + fill — selected target.
• Blue ring + blue label — X or Y node selected in d(X,Y) mode.
• Pale yellow glow ring — nodes on the highlighted shortest path (mode 4 only).

Edge Coloring

• Edge color — encodes which transposition (i, i+1) generated the edge (see Transpositions legend in left panel): red=(0,1), orange=(1,2), yellow=(2,3), green=(3,4), cyan=(4,5), …
• Yellow glow behind an edge — it lies on the highlighted shortest path.
• Curved edges — any edge that would pass through another node is bent into a Bézier arc. In Sort mode this applies to all edges, not just wrapped ones; same-layer and back-edges alternate curve side to reduce overlap.
• Dimmed edges (Sort mode) — non-tree edges are drawn at ~40% opacity so the BFS layer structure stays readable.

❄ Freeze

Instantly stops all physics. All node velocities are zeroed. While frozen, A and A* get prominent text callouts with leader lines so they are easy to identify. The button turns amber and reads ▶ Unfreeze. Press again to resume physics. Useful when generating large graphs (e.g. n=10, k=4 has 210 nodes) that take a long time to settle before you want to use Sort Vertices or d(X,Y).

🎯 Sort Vertices

Click the button to enter pick mode: the canvas dims, the cursor becomes a crosshair, and a banner prompts you to click any node U as the BFS root. Press Esc to cancel.

BFS from U partitions all nodes into layers L_d = {v : d(U,v) = d}. Two sub-modes:

⬤ Concentric Rings

U sits at the center. The canvas radius is divided into nL equal bands (nL = number of layers). Layer d occupies the annular band [d·w, (d+1)·w] and nodes are placed at its mid-radius. Solid black boundary circles mark each ring boundary on a white disc background. Labels on the left and right show d=… / c=… (layer index / node count). The ring is rotated so the most-connected node to the previous layer sits at the top.

≡ Layered Rows

The canvas is divided into nL equal horizontal bands. Layer d fills band d, with nodes centered in the band. Within each row, nodes are ordered by the barycenter heuristic (average neighbor position in the previous row) to minimise crossings. Dashed separators and d=… / c=… badges mark each row. Use ▼ Top→Down / ▲ Bottom→Up to flip direction.

Node radius is auto-scaled so nodes fit inside their band when the graph has many layers. Exit via ✕ Exit Sort Mode, Esc, Shake, Generate, or Grid.

📏 d(X,Y) — Distance Calculator

Click the button to open the calculator. Pick nodes X and Y by clicking them on the graph (they highlight with a blue ring and blue label) or by typing their bit-string labels in the input boxes. Once both are set, click ↳ Compute d(X,Y).

Three values are computed and shown in the right panel:

• d(X,Y) — shortest-path distance, found by BFS from X.
• N_o(X,Y) — number of shortest paths from X to Y. Computed by a BFS layer-counting pass: each node accumulates the sum of path counts from its BFS parents.
• N_p(X,Y) — number of all simple paths from X to Y, found by DFS with a visited-set. Capped at 1,000,000; displayed as "≥ 1,000,000" if the cap is reached.

After computing, click any node to pick a new X and start a fresh query without leaving the mode. Click ✕ Exit to close.

Diameter Verification

The Distance Formulas panel always shows the closed-form diameter k(n−k). When |V| ≤ 350, a full BFS-from-every-vertex check is run at build time and the result is shown as BFS=24 ✓ (match) or BFS=4 ⚠ (mismatch, indicating a bug).