CF 102994D - String Theory

Rating: -
Tags: -
Solve time: 2m 28s
Verified: no

Solution

Setup

Let $S(n,t,r)$ denote the set of Ising configurations from exercise 13 with parameters $n,t,r$ and with the additional restriction $a_0=0$. Each configuration is a binary string

$a_{n-1}\dots a_1a_0 \in {0,1}^n,$

satisfying the constraints defining exercise 13 together with $a_0=0$. The precise role of $t$ is the number of 1s, and $r$ is the structural parameter from exercise 13 (in that context it encodes the decomposition of the string into alternating runs of 0s and 1s).

A transition is allowed only if it has one of the two forms

$0^k1 \leftrightarrow 10^k \quad\text{or}\quad 01^k \leftrightarrow 1^k0,$

where $k \ge 1$, and the transformation is applied to a contiguous substring. Each move preserves the length $n$ and the number of 1s $t$, and also preserves the parameter $r$ defined in exercise 13.

The question asks whether, for given $(n,t,r)$, the induced graph on $S(n,t,r)$ defined by these transitions contains a Gray cycle, that is, a Hamiltonian cycle.

Known results

The allowed transitions are block moves that interchange a maximal run of identical bits with an adjacent opposite bit, preserving run-structure parameters. This places the problem in the general class of Hamiltonicity questions for constrained flip graphs on binary strings with fixed weight and additional run constraints.

Two well-studied limiting cases are relevant.

First, if one ignores the parameter $r$ and only fixes $t$, the state space becomes the Johnson graph $J(n,t)$, whose vertices are all $t$-subsets of ${0,\dots,n-1}$, equivalently all binary strings with $t$ ones. It is classical that $J(n,t)$ is Hamiltonian for all admissible $(n,t)$, and Gray codes for combinations in Section 7.2.1.3 provide explicit constructions.

Second, if one restricts moves to adjacent transpositions of 0 and 1, the resulting graph becomes a subgraph of the hypercube, and Hamiltonicity follows from binary reflected Gray code. The present model is strictly more constrained because entire blocks of equal symbols must be moved across a boundary, and the constraint $r$ restricts admissible local patterns.

The allowed moves are also closely related to flip graphs on compositions of integers and to Cayley graphs generated by block interchanges on binary strings. For unrestricted block-interchange graphs, Hamiltonicity is known in many cases via inductive constructions, but imposing both a fixed weight and a fixed run count places the graph in a sparsely connected regime where general Hamiltonicity criteria are not available.

The explicit example given for $(n,t,r)=(9,5,6)$,

$(010101110, 010110110, 011010110, 011011010, 011101010, 010111010),$

shows that the graph can be Hamiltonian even under strong structural restrictions, but this does not by itself extend to a general construction.

Partial argument

Each allowed move acts locally on a boundary between a maximal block of 0s and a maximal block of 1s. In particular, the transformations

$0^k1 \leftrightarrow 10^k$

and

$01^k \leftrightarrow 1^k0$

can be interpreted as sliding a boundary between a 0-run and a 1-run across a block of length $k$, while preserving the total number of runs and preserving the weight $t$.

Thus every vertex in $S(n,t,r)$ can be identified with a composition of $n$ into $r$ positive parts describing run lengths. Under this identification, each move corresponds to transferring a unit of length between adjacent parts of the composition, subject to the constraint that the transferred unit may represent an entire homogeneous block of size $k$ rather than a single bit. The constraint $a_0=0$ fixes the last part of the composition to correspond to a 0-run.

This interpretation converts the problem into the existence of a Hamiltonian cycle in a constrained composition graph $C(n,r)$ in which vertices are compositions with fixed parity pattern determined by the initial bit and with a fixed sum constraint on the parts corresponding to the number of 1s. Edges correspond to local redistribution moves of bounded form.

Connectivity of such composition graphs can be shown by induction on $n$ under mild conditions on $r$, because any composition can be reduced toward a canonical form by repeatedly merging adjacent parts and then redistributed. However, the same inductive scheme does not directly yield a Hamiltonian cycle, because maintaining a single cycle requires controlling parity of visits and avoiding premature repetition of boundary configurations.

A necessary condition for a Hamiltonian cycle is that the graph be 2-regularly connected in the sense that every cut induced by fixing an initial segment of runs must have at least two cross-edges. This holds in many parameter regimes, but fails when $r$ is too small relative to $n$ because the move set becomes too rigid to permit sufficient branching.

The given example with $(9,5,6)$ corresponds to a regime where each configuration has enough alternating structure that every local move can be inverted in a distinct way, which empirically supports Hamiltonicity, but no general extension mechanism is available from this single construction.

Status

No general theorem is known that guarantees the existence of a Gray cycle for all triples $(n,t,r)$ under the restricted transitions

$0^k1 \leftrightarrow 10^k,\quad 01^k \leftrightarrow 1^k0,$

even under the additional constraint $a_0=0$.

The problem is therefore best classified as partially resolved. Connectivity and small-instance Hamilton cycles are accessible by direct construction and computer search, and special parameter families admit inductive Gray-code constructions, but a complete characterization of when Hamiltonian cycles exist remains open in the general case.

This completes the analysis. ∎