Minimum degree in simplicial complexes

Basic Information

• Paper ID: 2501.01294
• Title: Minimum degree in simplicial complexes
• Authors: Christian Reiher, Bjarne Schülke
• Classification: math.CO (Combinatorics)
• Publication Date: January 2, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2501.01294

Abstract

Given $d\in\mathbb{N}$, let $\alpha(d)$ denote the maximum real number such that every abstract simplicial complex $\mathcal{S}$ satisfying $0<|\mathcal{S}|\leq\alpha(d)|V(\mathcal{S})|$ contains a vertex of degree at most $d$. This paper extends previous results by Frankl, Frankl and Watanabe, and Piga and Schülke, proving that for all integers $d$ and $m$ with $d\geq m\geq 1$, we have $\alpha(2^d-m)=\frac{2^{d+1}-m}{d+1}$. Similar results were independently obtained by Li, Ma, and Rong.

Research Background and Motivation

1. Core Problem: This research addresses the minimum degree problem in simplicial complexes. Given a simplicial complex, how can we determine the critical value of the ratio of edges to vertices such that exceeding this ratio necessarily implies the existence of high-degree vertices?
2. Significance:
   • The problem originates from trace theory of finite set families, holding an important position in extremal set theory
   • Closely related to topological properties and combinatorial structures of simplicial complexes
   • Widely applicable in theoretical computer science and discrete mathematics
3. Existing Limitations:
   • Frankl (1983) first established $\alpha(2^d-1) = \frac{2^{d+1}-1}{d+1}$
   • Frankl and Watanabe further obtained values for $\alpha(2^d-2)$ and $\alpha(2^d)$
   • Piga and Schülke extended results to $\alpha(2^d-c)$ when $d\geq 4c$
   • However, a complete characterization for general $m\leq d$ was lacking
4. Research Motivation: To establish a complete theoretical framework determining the exact values of all $\alpha(2^d-m)$ within the first natural parameter interval.

Core Contributions

1. Main Theorem: Proves that for $d\geq m\geq 1$, we have $\alpha(2^d-m) = \frac{2^{d+1}-m}{d+1}$
2. Technical Breakthrough: Develops more precise local analysis techniques and introduces the flexible "conglomerate" concept
3. Methodological Innovation: Introduces auxiliary functions and multi-simplicial complex settings supporting inductive arguments
4. Boundary Extension: Proves $\alpha(11) = \frac{53}{10}$, resolving the Frankl-Watanabe conjecture
5. Complete Table: Provides a complete list of all $\alpha(d)$ values for $d\leq 16$

Detailed Methodology

Task Definition

Input: Abstract simplicial complex $\mathcal{S}$, where $V(\mathcal{S})$ is the vertex set and $\mathcal{S}$ is the edge set Output: Determine the critical constant $\alpha(d)$ such that $|\mathcal{S}| > \alpha(d)|V(\mathcal{S})|$ implies $\delta(\mathcal{S}) > d$Constraints: $\mathcal{S}$ must be closed under subsets, i.e., if $S'\subseteq S\in\mathcal{S}$, then $S'\in\mathcal{S}$

Core Technical Framework

1. Upper Bound Construction

Construction 1: For $d\geq m\geq 2$, define $\mathcal{S} = \mathcal{P}([d+1]) \setminus \left(\{[d+1]\} \cup \{[d+1]\setminus\{i\} : i\in[m-2]\}\right)$ This construction yields the upper bound $\alpha(2^d-m) \leq \frac{2^{d+1}-m}{d+1}$.

2. Lower Bound Proof Strategy

Employs weight analysis method:

• Define weight $q(x) = \sum_{x\in F\in\mathcal{S}} \frac{1}{|F|}$ for each vertex $x$
• Utilize the weighted Kruskal-Katona theorem to establish weight lower bounds
• Handle local structures via "conglomerate" techniques

3. Conglomerate Concept

Definition: A set $K\in V^{(d+1)}$ is called a conglomerate if there exists a vertex $x\in K$ such that $|\{A : x\in A\subseteq K\} \setminus \mathcal{B}_1| \leq m$

Key Properties:

• Most subsets in a conglomerate belong to $\mathcal{B}_1$
• Any two conglomerates intersect in at most one vertex
• The weight sum of each conglomerate satisfies specific lower bounds

Technical Innovations

1. Refined Local Analysis: Compared to Piga-Schülke's "cluster" concept, conglomerates allow finite overlap, providing greater flexibility
2. Multi-Complex Induction: Introduces auxiliary functions and multiple simplicial complexes supporting induction on edge count without violating minimum degree conditions
3. Weight Optimization: Achieves tighter bounds through precise weight assignment and inequality techniques
4. Peak Theory: Generalizes the problem to $\mathbb{N}_{\geq 2}$-complexes ("peaks"), providing a unified framework

Experimental Setup

Theoretical Verification

This work is primarily theoretical, with results verified through rigorous mathematical proofs:

1. Upper Bound Verification: Proves tightness of upper bounds through explicit construction
2. Lower Bound Proof: Uses proof by contradiction and extremal principles
3. Special Case Verification: Validates consistency with known results

Computational Verification

Authors mention verification of additional cases:

• $\alpha(17) = \frac{50}{7}$
• $\alpha(20) = 8$

Experimental Results

Main Results

Theorem 1.1: For $d\geq m\geq 1$, we have $\alpha(2^d-m) = \frac{2^{d+1}-m}{d+1}$

Theorem 1.2: $\alpha(11) = \frac{53}{10}$ (resolves the Frankl-Watanabe conjecture)

Complete Numerical Table

Theoretical Findings

1. Formula Validity Range: The main formula no longer holds when $m > d$
2. Critical Phenomena: Structural changes occur near $m = d+1$
3. Asymptotic Behavior: For fixed $d$, $\alpha(2^d-m)$ decreases linearly with respect to $m$

Related Work

Historical Development

1. Frankl (1983): Established exact values for $\alpha(2^d-1)$, pioneering research in this field
2. Frankl-Watanabe (1994): Determined $\alpha(2^d-2)$ and $\alpha(2^d)$, proposed the $\alpha(11)$ conjecture
3. Piga-Schülke (2021): Developed the "cluster" method, handling cases with $d\geq 4c$

Related Techniques

• Kruskal-Katona Theorem: Classical result on shadow inequalities
• Extremal Set Theory: Studies relationships between set family size and structural constraints
• Simplicial Complex Theory: Foundational concepts in algebraic topology

Advantages of This Work

1. Completely resolves the first natural parameter interval $(m \leq d)$
2. Employs more refined and flexible technical methods
3. Unifies previously scattered results

Conclusions and Discussion

Main Conclusions

1. Completely determines exact values of $\alpha(2^d-m)$ for $d\geq m\geq 1$
2. Develops systematic methods for addressing minimum degree problems in simplicial complexes
3. Resolves an important conjecture in the field

Limitations

1. Parameter Restrictions: Main theorem applies only to $m \leq d$ cases
2. Computational Complexity: Proof techniques become complex for large parameters
3. Generalization Difficulty: Extension to more general parameters requires new technical breakthroughs

Future Directions

1. Investigate $\alpha(2^d-m)$ for $m > d$
2. Consider parameters not of the form powers of 2
3. Explore analogous problems for higher-dimensional simplicial complexes
4. Develop more efficient computational methods

In-Depth Evaluation

Strengths

1. Theoretical Completeness: Thoroughly resolves an important open problem
2. Methodological Innovation: The conglomerate concept and multi-complex techniques are original
3. Technical Depth: Proofs involve refined combinatorial analysis and inequality techniques
4. Exact Results: Provides explicit formulas rather than asymptotic estimates

Weaknesses

1. Readability: Complex proof techniques create high barriers to understanding
2. Computational Efficiency: Methods may be inefficient for verifying large parameter cases
3. Application Scope: Primarily theoretical results; practical applications require further exploration

Impact

1. Academic Value: Resolves fundamental problems in extremal combinatorics, advancing theory
2. Methodological Contribution: New techniques may apply to related problems
3. Completeness: Provides important milestone for research in this direction

Applicable Scenarios

1. Research in extremal set theory and combinatorial optimization
2. Applications of simplicial complexes and algebraic topology
3. Combinatorial structure analysis in theoretical computer science
4. Related problems in graph and hypergraph theory

References

Key references include:

• Frankl, P. (1983). On the trace of finite sets
• Frankl, P. & Watanabe, M. (1994). Some best possible bounds concerning the traces of finite sets
• Piga, S. & Schülke, B. (2021). On extremal problems concerning the traces of sets
• Katona, G. (1968). A theorem of finite sets
• Kruskal, J. B. (1963). The number of simplices in a complex

This paper makes significant contributions to extremal combinatorics, completely resolving a core case of the minimum degree problem in simplicial complexes through ingenious technical innovations, establishing a solid foundation for subsequent research.