ekmett / ekmett/name

TODO examples for the combinatorialist?

Open
#7 0 comments 1 reaction 0 assignees View on GitHub
Dominant language
Haskell
Stars
19
Forks
3
PR merge metrics
No merged PRs in 30d

Description

I was hoping you could annotate the TODO with examples of what efficient implementations of Nominal Sets give you for the combinatorialist? I'm most curious if Nominal Sets reach the Holy Grail of cranking the exact combinatorial complexity of semigroup operations like Boolean matrix-matrix multiply.

When you iterate an element of the full transformation semigroup (functions on a finite set) you blow away things in the range then enter into a cycle. If you graph of the full transformation semigroup under iteration you get several connected components with a group-like center and trees feeding into them. You can partition the set for a given transformation by how things are blown away and eventually end up in cycles. Blog post I did a few years back with pictures: http://chadbrewbaker.github.io/combinatorics/transformations/permutations/2014/08/07/endo.html

Back when working on symmetries in lattice protein folding models I figured out an optimal black box algorithm using prime cycle decompositions to test non-trivial members of the symmetric group:
https://oeis.org/A186202

I submitted it for publication, but it was rejected by Laci Babai. Laci must have forgot about it, because he used the less efficient brute force enumeration in his Graph Isomorphism paper:
https://arxiv.org/pdf/1512.03547.pdf

JD Mitchell's library of finite semigroup algorithms: https://james-d-mitchell.github.io/libsemigroups/

Munro's paper on succinct transformation semigroup operations:
https://arxiv.org/pdf/1108.1983.pdf

Tell me if I am totally wrong, but it is my understanding that given two members of the full transformation semigroup say $h$ and $g$, efficent Nominal Sets help you use the set partition formed by iterating $h$, and the set partition formed by iterating $g$ so that you only have to crunch within partitions that overlap when doing operations that involve $h$ and $g$? You could then feed in a concrete finite semigroup and get exact bounds for the complexity of compute required to do a multiplication/composition in it?

Contributor guide

No contributing guide indexed for this repository

Research direction

Locate the TODO referenced in the issue, then read the surrounding Nominal Sets implementation and its existing documentation. Compare the requested examples and complexity claims with the linked semigroup references; done means the TODO contains accurate, repository-supported examples rather than unresolved speculation.

Written by the indexing model from the issue text.

Assessment

Tech stack
haskell
Domain
documentation
Issue type
Documentation
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
15/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.