2025/05/02 by Shaw, Benedict Randall
#05D05 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2505.01131
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 sn, 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. Our proof uses some fractional techniques that may be of independent interest.