New Optima for the Deletion Shadow

Basic Information

• Paper ID: 2505.01131
• Title: New optima for the deletion shadow
• Author: Benedict Randall Shaw
• Classification: math.CO (Combinatorics)
• Publication Date: May 2025
• Paper Link: https://arxiv.org/abs/2505.01131

Abstract

For a family $\mathcal{F}$ consisting of words of length $n$ from an alphabet $A=[r]=\{1,\dots,r\}$, Danh and Daykin defined the deletion shadow $\Delta\mathcal{F}$ as the family containing all words obtained by deleting one letter from words in $\mathcal{F}$. They posed the question: given the size of such a family, how small can its deletion shadow be? For alphabet size 2, they answered this question using Kruskal-Katona-like results. However, Leck proved that for larger alphabets, no ordering exists that yields such results. For families of size $s^n$, the minimum shadow is known to be achieved by optimal families of the form $[s]^n$. This paper provides the minimum shadows for many intermediate sizes between these levels, proving that families of the form "all words in $[s]^n$ where symbol $s$ appears at most $k$ times" are optimal. The proof employs fractional techniques that may have independent value.

Research Background and Motivation

Problem Definition

This research addresses the deletion shadow problem, a fundamental problem in combinatorics:

1. Deletion Shadow: For a word family $F \subset A^n$, its deletion shadow $\Delta F$ is the set of all words obtained by deleting any character at any position from any word in $F$
2. Core Question: Given the size of a family $|F|$, how can one minimize its deletion shadow $|\Delta F|$?

Historical Development

• Danh-Daykin Pioneering Work: For alphabet size 2, they proved a Kruskal-Katona-like result, showing that initial segments in simple order minimize the deletion shadow
• Leck's Negative Result: Proved that for $r \geq 3$, no ordering exists such that all initial segments minimize their deletion shadow
• Limitations of Known Results: Previously, only the minimum deletion shadow for families of size $s^n$ was known, achieved by families of type $[s]^n$

Research Significance

1. Theoretical Value: Extends the theory of shadow problems in extremal combinatorics
2. Technical Innovation: Introduces fractional family techniques to circumvent Leck's impossibility result
3. Application Prospects: Provides new tools for related problems in coding theory and information theory

Core Contributions

1. Main Theorem: Proves that families of the form "all words in $[s]^n$ where symbol $s$ appears at most $k$ times" have the minimum deletion shadow for their given size
2. Technical Innovation: Develops fractional family theory for handling deletion shadow problems, including new compression concepts
3. Resolves Bollobás-Leader Conjecture: Solves an important open problem in the field
4. Density Lifting: Provides $n-1$ new known optimal sizes between each consecutive pair of $s^n$ and $(s+1)^n$

Methodology Details

Task Definition

• Input: Alphabet $A=[r]$, word length $n$, family size constraints
• Output: Word families with minimum deletion shadow
• Constraints: All words in the family have equal length and come from a finite alphabet

Core Technical Framework

1. Fractional Family Theory

Traditional discrete families $F \subset A^n$ can be represented using indicator functions taking values in $\{0,1\}$. Fractional families generalize this to:

• Definition: A fractional family is a function $f: A^n \to [0,1]$
• Weight: $|f| = \sum_{w \in A^n} f(w)$
• Deletion Shadow: $(\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. Fractional Hamming Balls

Extends discrete Hamming balls $B^{(n,s)}(k)$ (words in $[s]^n$ where symbol $s$ appears at most $k$ times) to fractional versions:

• Symbol $s$ appears at most $k$ times: weight 1
• Symbol $s$ appears exactly $k+1$ times: weight $\alpha \in [0,1]$
• Other cases: weight 0

Denoted as $b^{(n,s)}_{k,\alpha}$, with the property: $\Delta b^{(n,s)}_{k,\alpha} = b^{(n-1,s)}_{k,\alpha}$

3. Compression Theory

Since uniform fractional families minimize deletion shadows but do not correspond to discrete families, the optimization range must be restricted:

$s$-Compression: A fractional family $f$ satisfies that for $y < x_i$ and $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$

Main Theorems and Proof Strategy

Theorem 4.1: Let $f$ be an $s$-compressed fractional family on $A^n$ with $|f| \leq s^n$, and let $h$ be a fractional Hamming ball with the same weight as $f$. Then $|\Delta f| \geq |\Delta h|$.

Proof Strategy:

1. Inductive Base: Direct verification for $n=1$
2. Layer Decomposition: Decompose $f$ into layers $f_x(x_1,\ldots,x_{n-1}) = f(x_1,\ldots,x_{n-1},x)$
3. Construct Comparison Family: Construct fractional family $g$ where each layer is a fractional Hamming ball
4. Case Analysis:
   • Case 1: $g_s$ has small weight, use lower bounds for deletion at the last coordinate
   • Case 2: $g_s$ has moderate weight, use lower bounds for deletion at non-last coordinates and inductive hypothesis
   • Case 3: Handle boundary cases
5. Optimization Analysis: Transform the problem into an optimization problem concerning weight distribution

Experimental Setup

This is a pure theoretical mathematics paper with no numerical experiments. All results are obtained through rigorous mathematical proofs.

Experimental Results

Main Results

Theorem 1.2 (Main Result): For any $s \leq r$, $k \leq n$, let family $F$ consist of all words in $[s]^n$ where symbol $s$ appears at most $k$ times. Then among all families of the same size in $[r]^n$, $F$ has the minimum deletion shadow.

Theoretical Verification

• Verified optimality of $[s]^n$-type families using discrete Loomis-Whitney inequality
• Proved optimality of fractional Hamming balls under constraints
• Established connections between discrete and fractional results

Technical Achievements

1. Density Lifting: Provides $n-1$ new known optimal sizes between each pair $(s^n, (s+1)^n)$
2. Method Universality: Fractional techniques may apply to other extremal combinatorics problems
3. Conjecture Resolution: Completely resolves the Bollobás-Leader conjecture

Related Work

Historical Context

1. Kruskal-Katona Theorem: Classical result on shadow problems for set systems
2. Danh-Daykin Work: Generalized shadow problems to word deletion, establishing complete theory for binary alphabets
3. Leck's Impossibility Result: Proved non-existence of complete ordering for large alphabets
4. Bollobás-Leader Fractional Techniques: Applications in isoperimetric inequalities and fractional set systems

Positioning of This Work's Contributions

• Breakthrough: Circumvents Leck's impossibility result, providing exact solutions in restricted settings
• Innovation: First systematic application of fractional techniques to deletion shadow problems
• Refinement: Significantly extends the density of known optimal families

Conclusions and Discussion

Main Conclusions

1. Proves that families of specific forms (discrete families corresponding to fractional Hamming balls) have minimum deletion shadow for their given size
2. Establishes a fractional technique framework for handling deletion shadow problems
3. Resolves the Bollobás-Leader conjecture on the structure of optimal families

Limitations

1. Coverage: Many intermediate sizes with unknown optimal family structures remain
2. Computational Complexity: Does not address algorithmic complexity of finding optimal families
3. Generalizability: Applicability of fractional techniques to other shadow problems requires further verification

Future Directions

The paper proposes two important follow-up questions:

1. Extended Conjecture: Whether more complex multi-layer family structures can be considered
2. Signature Ordering Conjecture: More general optimality conjecture based on lexicographic signatures

In-Depth Evaluation

Strengths

1. Theoretical Depth: Cleverly circumvents known impossibility results through fractional techniques
2. Technical Innovation: Introduction of $s$-compression concept and fractional Hamming balls is original
3. Proof Completeness: Clear inductive proof structure with meticulous case handling
4. Problem Resolution: Completely resolves an important open conjecture

Weaknesses

1. Practical Applicability: Pure theoretical results with limited direct applications
2. Computational Aspects: Does not address algorithmic implementation and complexity analysis
3. Generalizability: Universal applicability of techniques requires further verification

Impact

1. Theoretical Contribution: Provides new technical tools for extremal combinatorics
2. Methodological Value: Fractional techniques may inspire solutions to related problems
3. Completeness: Significantly advances the perfection of deletion shadow problem theory

Applicable Scenarios

1. Coding Theory: Design and analysis of error-correcting codes
2. Information Theory: Channel capacity and coding efficiency problems
3. Theoretical Computer Science: Combinatorial structure analysis in complexity theory

References

The paper cites key literature in the field, including:

• Pioneering work by Danh and Daykin 3,4,5
• Leck's impossibility results 6
• Fractional techniques by Bollobás and Leader 1,2
• Discrete Loomis-Whitney inequality 7
• Related shadow problem research 8

Overall Assessment: This is a high-quality theoretical mathematics paper that resolves an important open problem in deletion shadow theory through innovative fractional techniques. The technical methods are novel, the proofs are rigorous, and the work makes significant contributions to combinatorial mathematics theory. While direct applications are limited, the developed technical framework has substantial theoretical value and potential for generalization.