Claude–Knuth cycles

[mtorpey]

An interesting recent result from Don Knuth, an old exercise he wrote finally having been solved with the assistance of the Claude AI engine.

https://www-cs-faculty.stanford.edu/~knuth/papers/claude-cycles.pdf

Some of the proof seems hard, but I think the actual constructions (of the graph and the decomposition) are pretty easy. Maybe it'd be nice to have them.

Not sure of an appropriate name for either concept. Claude–Knuth cycles?

[reiniscirpons]

For implementing the digraph things are more or less clear, though we should take care to check we dont already have a function for generating digraphs of this type.

But I was wondering about what to do with the cycles. We don't currently seem to have a function for finding disjoint unions of cycles with a size constraint like this it seems. Defining a one-off function that does not generalize and only works for the Knuth digraph seems a shame.

So perhaps we could define a more general function DigraphUniformCycleDecomposition(D, k) which takes a digraph D and a number k and reurns a decomposition of D into k cycles of the same length, if it exists, and return false if it does not exist (Maybe we could return fail, but this might be confusing if the function fails for unrelated reasons).

Then we can implement the method from the paper as a particular instance when D is the Knuth digraphs and k=3. Writing a (possibly innefficient) general function that solves the problem via backtracking (i.e. find a cycle of length |D|/k, remove cycle from graph, find another cycle, rinse repeat until no more cycles are found, and backtrack choosing a different cycle if there are still edges remaining) say, might be a fun as well, and could be a good exercise in backtrack optimization.