Unavoidable language in padded strings

Question 8.3 · arXiv:2311.05066

arXiv Question high confidence— first stated 2024-11-26

Authors: Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl

Status open high confidence

Question 8.3 of arXiv:2311.05066 asks for a characterisation of sets $\mathcal{S}$ of strings that are $c$-unavoidable languages (every $c$-padded string contains a member of $\mathcal{S}$ or its reverse as a consecutive substring for some constant $c$). The question is motivated by the structure theory of tasselled graph families developed in the same paper. No follow-up work resolving or substantially advancing this question was found in the indexed literature as of May 2026.

Reviewer notes. No follow-up found. The question is highly specific (combinatorics of string patterns arising from tasselled graph families) and appears in a 2024 paper; absence of follow-up is consistent with it being open. The only singleton $c$-unavoidable languages identified in the paper itself are $\mathcal{S}=\{0\cdots01\}$ (up to reversal) and $\mathcal{S}=\{0\cdots0\}$. The series continues at least through paper XIX (arXiv:2506.05602) but none of the subsequent papers in the series appear to address this string-combinatorics question.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Question. For which sets $\mathcal{S}$ of strings is it true that there is a constant $c=c(\mathcal{S})\in\mathbb{N}$ such that every $c$-padded string $S$ contains either a string in $\mathcal{S}$ or the reverse of a string in $\mathcal{S}$ as a consecutive substring?

Context

This question arises in the special case where every graph in $\mathcal{H}$ is a $c'$-tassel for some $c'\in\mathbb{N}$, where each tassel has a unique string $\mathcal{S}_{H,v}$ associated to each neck $v$. A set $\mathcal{S}$ satisfying the condition is called a $c$-unavoidable language, and identifying minimal such languages is key to characterising tasselled families. The only singleton $c$-unavoidable languages are $\mathcal{S}=\{0\cdots 01\}$ (up to reversal) and $\mathcal{S}=\{0\cdots 0\}$.

Also stated in

Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$ (2024-11-26)

Source paper

Induced subgraphs and tree decompositions XIII. Basic obstructions in $\mathcal{H}$-free graphs for finite $\mathcal{H}$
Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · 2024-11-26
https://arxiv.org/abs/2311.05066