New Optima for the Deletion Shadow

Abstract

For a family \(\mathcal{F}\) of words of length \(n\) drawn from an alphabet \(A=[r]=\{1,\dots,r\}\), Danh and Daykin defined the deletion shadow \(\Delta \mathcal{F}\) as the family containing all words that can be made by deleting one letter of a word of \(\mathcal{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^n\), where the optimal family has form \([s]^n\). We give the minimal shadow for many intermediate sizes between these levels, showing that families of the form "all words in \([s]^n\) in which the symbol \(s\) appears at most \(k\) times" are optimal. This proves a conjecture of Bollobás and Leader. Our proof uses some fractional techniques that may be of independent interest.