Post

My WABI submission: anti-lexicographic SUS-anchors. For sigma=4, this selection scheme (a k=1 sampling scheme) has density within 1% of the lower bound! The idea: find the smallest* substring that does not have a 2nd occurrence, and sample its start pos. curiouscoding.nl/posts/sus-an...

*: small w.r.t. the anti-lexicographic order, which minimizes the first character and maximizes the remaining ones. So AZZZZ is a small string in this order. You might recognise this from my thesis or Pisa DSB talk. But it's such a simple yet strong result, it deserves more attention :)

All are invited to help with a proof of the density [which would be great for an extended version]. I have ideas, but need someone to discuss them with, and it gets a bit more messy than I hoped.