This analysis reveals optimal structures for deletion shadows, indicating efficiency in intermediate family sizes.
For a family F of words of length n drawn from an alphabet A=[r]=\1,,r\, Danh and Daykin defined the deletion shadow Δ F as the family containing all words that can be made by deleting one letter of a word of F. They asked, given the size of such a family, how small its deletion shadow can be, and answered this with a Kruskal-Katona type result when the alphabet has size $2$. However, Leck showed that no ordering can give such a result for larger alphabets. The minimal shadow has been known for families of size sⁿ, where the optimal family has form [s]ⁿ. We give the minimal shadow for many intermediate sizes between these levels, showing that families of the form 'all words in [s]ⁿ in which the symbol s appears at most k times' are optimal. Our proof uses some fractional techniques that may be of independent interest.
No takes yet. Share an insight, caveat, or question.
Benedict Randall Shaw (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: