Superpermutations but Easier - Minimal Injective Superstrings

We consider a problem that is closely related to the minimal superpermutation problem, but is significantly easier: what is the shortest "injective superstring"? That is, what is the shortest string that contains, as substrings, all strings with distinct digits (but fewer digits per string than a permutation)?

The results demonstrated in this video are based on the following article:
Ashlock, Daniel A.; Tillotson, Jenett (1993), "Construction of small superpermutations and minimal injective superstrings", Congressus Numerantium, 93: 91–98.
Blog post: https://njohnston.ca/2024/05/minimal-...

Timestamps:
00:00 Introduction
00:24 A Reminder: Superpermutations
01:47 Definition Time: Injective Superstrings
05:21 Proving Existence (via Graph Theory!)
10:03 Back to Superpermutations: What Goes Wrong

Background reading and watching about superpermutations:
Numberphile video:    • Superpermutations - Numberphile  
Stand-up Maths video:    • Superpermutations: the maths problem solve...  
Quanta article: https://www.quantamagazine.org/sci-fi...

Animations made with Manim.

#superpermutation #permutations #superstring #injectivefunction