2025-11-21T23:25:22.022250

New optima for the deletion shadow

Shaw

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 $Î\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.

academic

New optima for the deletion shadow

基本信息

论文ID: 2505.01131
标题: New optima for the deletion shadow
作者: Benedict Randall Shaw
分类: math.CO (组合数学)
发表时间: May 2025
论文链接: https://arxiv.org/abs/2505.01131

摘要

对于由长度为 $n$ 、来自字母表 $A=[r]=\{1,\dots,r\}$ 的单词组成的族 $\mathcal{F}$ ，Danh和Daykin定义了删除影子 $\Delta\mathcal{F}$ 为包含所有通过删除 $\mathcal{F}$ 中单词的一个字母而得到的单词的族。他们提出了一个问题：给定这样一个族的大小，其删除影子能有多小？当字母表大小为2时，他们用类似Kruskal-Katona的结果回答了这个问题。然而，Leck证明了对于更大的字母表，不存在能给出这种结果的排序。对于大小为 $s^n$ 的族，已知最小影子由形式为 $[s]^n$ 的最优族达到。本文给出了这些层级之间许多中间大小的最小影子，证明了形式为" $[s]^n$ 中符号 $s$ 最多出现 $k$ 次的所有单词"的族是最优的。证明使用了一些可能具有独立价值的分数技术。

研究背景与动机

问题定义

本研究关注删除影子问题，这是组合数学中的一个基本问题：

删除影子：对于单词族 $F \subset A^n$ ，其删除影子 $\Delta F$ 是通过删除 $F$ 中任意单词的任意一个位置的字符而得到的所有单词的集合
核心问题：给定族的大小 $|F|$ ，如何使其删除影子 $|\Delta F|$ 最小？

历史发展

Danh-Daykin开创性工作：当字母表大小为2时，证明了类似Kruskal-Katona定理的结果，即按简单序排列的初始段能最小化删除影子
Leck的否定结果：证明了当 $r \geq 3$ 时，不存在任何排序使得所有初始段都能最小化其删除影子
已知结果局限性：此前仅知道大小为 $s^n$ 的族的最小删除影子，由 $[s]^n$ 型族达到

研究意义

理论价值：扩展了极值组合学中的影子问题理论
技术创新：引入分数族技术绕过Leck的不可能性结果
应用前景：为编码理论、信息论中的相关问题提供新工具

核心贡献

主要定理：证明了形式为" $[s]^n$ 中符号 $s$ 最多出现 $k$ 次的所有单词"的族具有给定大小下的最小删除影子
技术创新：开发了分数族理论来处理删除影子问题，包括新的压缩概念
证明了Bollobás-Leader猜想：解决了该领域的一个重要开放问题
密度提升：在每对连续的 $s^n$ 和 $(s+1)^n$ 之间提供了 $n-1$ 个新的已知最优大小

方法详解

任务定义

输入：字母表 $A=[r]$ ，单词长度 $n$ ，族大小约束
输出：具有最小删除影子的单词族
约束：族中所有单词长度相同，来自有限字母表

核心技术框架

1. 分数族理论

传统的离散族 $F \subset A^n$ 可以用指示函数表示，取值为 $\{0,1\}$ 。分数族将此推广为：

定义：分数族是从 $A^n$ 到 $[0,1]$ 的函数 $f$
权重： $|f| = \sum_{w \in A^n} f(w)$
删除影子： $(\Delta f)(x_1,\ldots,x_{n-1}) = \max_{y \in A, i \in [n]} f(x_1,\ldots,x_{i-1},y,x_i,\ldots,x_{n-1})$

2. 分数Hamming球

扩展离散Hamming球 $B^{(n,s)}(k)$ （ $[s]^n$ 中符号 $s$ 最多出现 $k$ 次的单词）到分数版本：

符号 $s$ 最多出现 $k$ 次：权重为1
符号 $s$ 恰好出现 $k+1$ 次：权重为 $\alpha \in [0,1]$
其他情况：权重为0

记为 $b^{(n,s)}_{k,\alpha}$ ，具有良好性质： $\Delta b^{(n,s)}_{k,\alpha} = b^{(n-1,s)}_{k,\alpha}$

3. 压缩理论

由于均匀分数族会最小化删除影子但不对应离散族，需要限制优化范围：

$s$ -压缩：分数族 $f$ 满足，对于 $y < x_i$ 且 $s \leq x_i$ ： $f(x_1,\ldots,x_n) > 0 \Rightarrow f(x_1,\ldots,x_{i-1},y,x_{i+1},\ldots,x_n) = 1$

主要定理及证明思路

定理4.1：设 $f$ 是 $A^n$ 上的 $s$ -压缩分数族，满足 $|f| \leq s^n$ ， $h$ 是与 $f$ 同权重的分数Hamming球，则 $|\Delta f| \geq |\Delta h|$ 。

证明策略：

归纳基础： $n=1$ 时直接验证
层分解：将 $f$ 分解为 $f_x(x_1,\ldots,x_{n-1}) = f(x_1,\ldots,x_{n-1},x)$
构造对比族：构造分数族 $g$ ，各层都是分数Hamming球
分情况讨论：
- 情况1： $g_s$ 权重较小，利用最后坐标删除的下界
- 情况2： $g_s$ 权重适中，利用非最后坐标删除的下界和归纳假设
- 情况3：处理边界情况
优化分析：将问题转化为关于权重分布的优化问题