|国家预印本平台
首页|New optima for the deletion shadow

New optima for the deletion shadow

New optima for the deletion shadow

来源:Arxiv_logoArxiv
英文摘要

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. Our proof uses some fractional techniques that may be of independent interest.

Benedict Randall Shaw

数学

Benedict Randall Shaw.New optima for the deletion shadow[EB/OL].(2025-05-02)[2025-06-14].https://arxiv.org/abs/2505.01131.点此复制

评论