On an extension problem on the moment curve

Basic Information

• Paper ID: 2511.14176
• Title: On an extension problem on the moment curve
• Authors: Seunghun Lee (Keimyung University), Eran Nevo (Universidad de Valladolid & Hebrew University)
• Classification: math.CO (Combinatorics)
• Publication Date: November 18, 2025 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2511.14176

Abstract

This paper investigates the extension problem for finite geometric simplicial complexes on the moment curve. The main results demonstrate that for $2 \leq d \leq 4$ dimensions, any finite geometric simplicial complex $\Delta$ on the moment curve can be extended to a triangulation $T$ of a cyclic polytope $C$, where $\Delta, T, C$ share the same vertex set. However, for $d \geq 5$, for any $n \geq d+3$, there exist complexes on $n$ vertices that cannot be extended in this manner.

The result for $d=4$ has important algebraic applications: combined with the correspondence of Oppermann and Thomas (2012), it proves that every maximal rigid object in the higher-dimensional cluster category $\mathcal{O}_{A_n^2}$ is cluster tilting.

Research Background and Motivation

Core Problem

This paper investigates the following natural extension problem (Question 1.1): Can every geometric simplicial complex on a finite point set $A$ on the moment curve $\gamma_d = \{(t, t^2, \ldots, t^d) : t \in \mathbb{R}\}$ in $\mathbb{R}^d$ be extended to a triangulation of $\text{conv}(A)$ without adding new vertices?

Importance of the Problem

1. Foundational combinatorial geometry: The moment curve and cyclic polytope are central objects in discrete geometry. The cyclic polytope maximizes the number of faces for a given dimension and number of vertices (McMullen's upper bound theorem).
2. Pure combinatorial nature: Although the problem is stated geometrically, it is fundamentally combinatorial—the intersection of $d$-simplices corresponds to interlacing patterns, and boundary faces are determined by Gale evenness conditions.
3. Algebraic applications: Through the Oppermann-Thomas correspondence, this problem is directly related to representation theory of higher-dimensional Auslander algebras.

Limitations of Existing Research

• Low-dimensional cases: For $d=2$, any complex can be extended; for $d=3$, there exist non-extendable examples on general point sets (e.g., Schönhardt polyhedra).
• Specificity of moment curves: The situation on moment curves has not been systematically studied.
• Higher-dimensional Stasheff-Tamari posets: Edelman and Reiner defined two partial orders; Williams (2024) proved their equality, but their relationship to the extension problem remains unclear.

Research Motivation

Determine the dimensional threshold for extensibility and explore its applications in algebraic topology and representation theory.

Core Contributions

1. Dimensional Dichotomy Theorem (Theorem 1.2):
   • For $D \leq 4$: Any collection of non-overlapping simplices can be extended to a triangulation of a cyclic polytope.
   • For $D \geq 5$ and $n \geq D+3$: Non-extendable examples are constructed.
2. Algebraic Application (Corollary 1.4): Proves that for $\delta=2$, every maximal rigid object in $\mathcal{O}_{A_n^\delta}$ is cluster tilting.
3. Technical Innovations:
   • Introduces height functions and lifting techniques to define partial order relations $\prec_{d+1}$ and $\preceq_{d+1}$ between simplices.
   • For $d=2,3$, constructs extensions using the lattice properties of HST$(n,d)$.
   • For $d=3$, provides complex combinatorial lemmas (Lemma 3.8) to handle interlacing patterns.
4. Algorithmic Results (Proposition 5.2): Provides a greedy extension algorithm with $O(n^5)$ time complexity for $d=3,4$.

Detailed Methodology

Task Definition

Input: A collection $\mathcal{F}$ of pairwise non-overlapping $d$-simplices on a finite point set $A \subseteq \gamma_d$.

Output: Determine whether there exists a triangulation $T \in S(n,d)$ such that $\mathcal{F} \subseteq T$.

Constraint: No new vertices are added.

Core Technical Framework

1. Interlacing Pattern Characterization (Proposition 2.2)

Two simplices $\sigma, \tau \subseteq \gamma_d$ overlap in $\mathbb{R}^d$ if and only if they are $(d+2)$-interlacing:

• There exists a sequence $v_1 < \cdots < v_{d+2}$ that alternately belongs to $\sigma$ and $\tau$.

This completely transforms the geometric problem into a combinatorial one.

2. Height Functions and Partial Order Relations

For a simplex $\sigma = \{\gamma_d(t_1), \ldots, \gamma_d(t_k)\}$, define:

• Lifting: $\hat{\sigma} = \{\gamma_{d+1}(t_1), \ldots, \gamma_{d+1}(t_k)\}$
• Height function: $h_\sigma: \text{conv}(\sigma) \to \mathbb{R}$, defined by projecting the last coordinate of $\text{conv}(\hat{\sigma})$.

Key Relation (Proposition 2.4): $\sigma \prec_{d+1} \tau$ if and only if:

• For even $d$: $\sigma, \tau$ satisfy condition (σ) but not condition (τ) for $(d+2)$-interlacing.
• For odd $d$: $\sigma, \tau$ satisfy condition (τ) but not condition (σ) for $(d+2)$-interlacing.

Define $\sigma \preceq_{d+1} \tau$ as the reflexive transitive closure of $\prec_{d+1}$, and prove this is a partial order (Lemma 2.7).

3. Higher Stasheff-Tamari Partial Order

Triangulations $T, T' \in S(n,d)$ satisfy $T \leq_{d+1} T'$ if $h_T(p) \leq h_{T'}(p)$ for all $p \in C(n,d)$.

Submersion Set: $\text{sub}(T) = \{\sigma \subseteq \gamma_d : \sigma \leq_{d+1} T, \dim(\sigma) = \lceil d/2 \rceil\}$

Key Fact (Theorem 2.12, Edelman-Reiner): For $d=2,3$, the map $\Phi: T \mapsto \text{sub}(T)$ is a lattice embedding, and: $\text{sub}(T_1 \wedge T_2) = \text{sub}(T_1) \cap \text{sub}(T_2)$

Proof Strategy for Low-Dimensional Cases

Construction for $d=2$ (Theorem 3.1)

For an edge or triangle $\sigma$, construct $T(\sigma)$:

1. $\sigma$ partitions $C(n,2)$ into at most 3 polygons $P_i$.
2. For each $P_i$, connect the maximum vertex $m_i$ to other unconnected vertices.
3. Verify that all simplices satisfying the conditions satisfy $\tau \leq_3 T(\sigma)$.

Complex Construction for $d=3$ (Theorem 3.2)

Input: Triangles $\sigma, \tau_1, \ldots, \tau_m$ whose liftings in $\mathbb{R}^4$ are pairwise non-overlapping.

Strategy:

1. Simplification: Assume $\min(\sigma) = 1$ via coning operations.
2. Interval decomposition: Define $J_L, I_M, J_M, J_R$ relative to $\sigma = \{v_1, v_2, v_3\}$.
3. Initial triangulation: Start from the maximal triangulation $T_M^{V_0}$ ($V_0 = [n] \setminus I_M$).
4. Inductive coning: Perform coning on points in $I_M$ in a specific order.
5. Key reduction (Claim 1): Reduce the problem to finding a triangulation in $S(J_M, 2)$ avoiding specific interlacing patterns.

Core Lemma (Lemma 3.8): Given edge sets $L, R$ and triangle set $M$ satisfying specific interlacing constraints, one can construct a triangulation of a polygon such that each edge avoids forbidden interlacing patterns with $L, M, R$.

The proof uses complex induction:

• Induction on $|V| + |M| + |R| + |L|$.
• Select a "middle triangle" $t = \{w_1 < w_2 < w_3\}$ such that the interval $[w_1, w_3]$ is maximal.
• Construct a sequence of diagonals $w_2q_0, w_2q_1, \ldots$ emanating from $w_2$.
• Verify through detailed case analysis that the final diagonal satisfies all conditions.

Unified Proof Framework (Theorem 1.2(i))

1. Dimension reduction: Use Proposition 3.3 to reduce to the $\lceil D/2 \rceil$-dimensional skeleton.
2. Ordering: Order simplices $\sigma_1, \ldots, \sigma_m$ in a specific manner.
3. Construct sequence: Use Theorems 3.1/3.2 to obtain $T_i$ such that $\sigma_i \in T_i$ and $\sigma_j \leq_D T_i$ for $j < i$.
4. Take meet: $S_k = T_k \wedge T_{k+1} \wedge \cdots \wedge T_m$.
5. Verification: Use the intersection property of submersion sets (equation (1)) and Lemma 2.13 to prove $\sigma_k \in S_k$.

High-Dimensional Non-Extensibility Construction

Basic Example (Proposition 4.1, Rambau)

For $d=5, n=8$, the following three 5-simplices cannot be extended: $\sigma_1 = \{1,2,3,4,5,6\}, \quad \sigma_2 = \{3,4,5,6,7,8\}, \quad \sigma_3 = \{1,2,3,6,7,8\}$

Proof idea: Any new 5-simplex $\tau$ must simultaneously avoid 7-interlacing, leading to $\tau = \sigma_3$, a contradiction.

Extended Construction

• Adding vertices (Proposition 4.2): Extend to $n+1$ vertices by adding cones over visible facets.
• Lifting dimension (Proposition 4.4): Lift to dimension $D+1$ via the join operation $\mathcal{F} * \{\{n+1\}\}$.

Combining these two operations yields examples for all $D \geq 5, n \geq D+3$.

Experimental Setup

This is a pure theoretical mathematics paper with no traditional experiments. However, it provides:

Algorithmic Analysis (Section 5)

Greedy Algorithm (Proposition 5.2):

• Input: A complex $\Delta$ on $n$ vertices.
• Strategy: Iteratively select a $(d-1)$-simplex $\tau$, find a $d$-simplex $\sigma$ containing $\tau$ that does not $(d+2)$-interlace with existing facets.
• Time complexity: $O(n^5)$
  • Single check: $O(n^2)$
  • At most $O(n)$ checks per step
  • At most $O(n^2)$ steps

Computational Complexity Questions

Problem 5.1 is posed: Find optimal algorithms for computing extensions when $d=3,4$.

Output size lower bound: $\Omega(n^2)$ (some triangulations have $\Theta(n^2)$ faces).

Experimental Results

Summary of Theoretical Results

Key Quantitative Results

1. Tightness (Proposition 4.5): $n = d+2$ is the threshold for extensibility.
   • $n \leq d+2$: Always extendable.
   • $n \geq d+3$: Non-extendable examples exist for $d \geq 5$.
2. Minimal counterexample size:
   • Dimension: $d=5$
   • Vertices: $n=8$
   • Number of simplices: 3
3. Algorithm efficiency: $O(n^5)$ time ($d=3,4$).

Verification of Algebraic Applications

Corollary 1.4 is verified through the following correspondence chain: $\text{Non-overlapping 4-simplices} \xleftrightarrow[\text{Thm 1.3}]{} \text{Rigid objects} \xRightarrow[\text{Thm 1.2(i)}]{d=4} \text{Extendable} \xleftrightarrow[\text{Thm 1.3}]{} \text{Cluster tilting}$

This fills the gap in the Oppermann-Thomas work for the $\delta=2$ case ($\delta=1$ was known, counterexamples exist for $\delta \geq 3$).

Lattice Property Comparison (Table 1)

Observation: Lattice properties and extensibility are not completely equivalent, but have deep connections.

Related Work

Combinatorics of Cyclic Polytopes

1. Edelman-Reiner (1996): Define two higher Stasheff-Tamari partial orders, prove they are equal and form a lattice for $d=2,3$.
2. Rambau (1997): Provide non-extendable examples for $d=5, n=8$, establish connections between the two partial orders (Theorem 2.11).
3. Williams (2024): Prove the two partial orders are equal for all dimensions.
4. Edelman-Rambau-Reiner (2000), Williams (2022): Study that HST is not a lattice for $d=4,5$.

Interlacing Patterns and Hypergraph Coloring

• Alternating oriented matroids (Björner et al. 1999): The interlacing conditions in Proposition 2.2 define alternating oriented matroids.
• (AB)$_{l/2}$-free hypergraphs (Ackerman-Keszegh-Pálvölgyi 2020, Keszegh-Pálvölgyi 2024): The non-overlapping condition in this paper is equivalent to $(AB)_{d+1}$-freeness.

Algebraic Representation Theory

• Iyama (2011): Introduce higher-dimensional Auslander algebras $A_n^\delta$.
• Oppermann-Thomas (2012): Establish correspondence between $A_n^\delta$ and triangulations of cyclic $2\delta$-polytopes (Theorem 1.3).
• Zhou-Zhu (2011), Buan et al. (2009): For $\delta=1$, maximal rigid objects are cluster tilting.

Convex Partitions of Polyhedra

• Chazelle (1984), Chazelle-Palios (1990): Study convex partitions of non-convex polyhedra, but allow subdivision of simplices (different from this paper).

Conclusions and Discussion

Main Conclusions

1. Dimensional threshold: $d \leq 4$ is the precise threshold where the extension problem on moment curves is always solvable.
2. Algebraic-geometric correspondence: First time a pure representation-theoretic problem (cluster tilting property for $\delta=2$) is solved via combinatorial methods.
3. Methodological contribution: Height functions and lifting techniques provide new perspectives for studying cyclic polytopes.

Limitations

1. Algorithm complexity:
   • The $O(n^5)$ algorithm may not be optimal (output size is only $O(n^2)$).
   • Problem 5.1 remains unresolved: What is the optimal algorithm complexity?
2. Quantitative questions (Problem 5.3):
   • How many new vertices are needed for extension when $d \geq 5$?
   • Currently only known that $m(d,n) \geq 1$.
3. Minimal counterexamples (Problem 5.5):
   • Do there exist non-extendable examples with 2 $d$-simplices ($d \geq 5$)?
   • Lemma 5.6 proves that 1 simplex is always extendable.
4. Lattice properties (Question 5.4):
   • Is HST$(d+4, d)$ a lattice ($d \geq 4$)?
   • The deeper connection to extensibility remains unclear.

Future Directions

1. Algebraic approach: Can Theorem 1.2 be proved purely algebraically (similar to reverse application of 24)?
2. Algorithm optimization:
   • Improve extension algorithms for $d=3,4$.
   • Study approximate extensions for $d \geq 5$.
3. Generalizations:
   • Extension problems on other algebraic curves.
   • More general convex position point sets.
4. Combinatorial structures:
   • Characterize all minimal non-extendable configurations for $d \geq 5$.
   • Study combinatorial properties of interlacing patterns.

In-Depth Evaluation

Strengths

1. Theoretical completeness:
   • Provides complete characterization of the extension problem ($d \leq 4$ feasible, $d \geq 5$ infeasible).
   • Proof is tight ($n=d+2$ vs. $n=d+3$ boundary).
2. Technical innovations:
   • Height function method: Elegantly transforms geometric problems into partial order theory, both elegant and powerful.
   • Lemma 3.8: The combinatorial lemma handling the $d=3$ case is extremely sophisticated, involving complex case analysis.
   • Unified framework: Unifies proofs for $d=2,3$ through submersion sets and lattice meet operations.
3. Interdisciplinary impact:
   • Connects discrete geometry, algebraic topology, and representation theory.
   • Corollary 1.4 is the first to solve a pure algebraic problem using combinatorial methods.
   • Provides new tools for studying higher cluster categories.
4. Writing quality:
   • Clear structure (Section 2 preliminaries, Section 3 positive results, Section 4 counterexamples).
   • Numerous figures aid understanding (Figures 1-9).
   • Detailed proofs (e.g., 15-page proof of Lemma 3.8).

Weaknesses

1. Proof complexity:
   • The proof of Lemma 3.8 is extremely lengthy, involving multiple layers of induction and extensive case analysis.
   • Difficult to extract core intuition; more concise proofs may exist.
2. Limited algorithmic results:
   • The $O(n^5)$ algorithm has a significant gap with the $\Omega(n^2)$ output size lower bound.
   • No actual implementation or numerical experiments provided.
   • No algorithmic results for $d \geq 5$.
3. Many open problems:
   • Problem 5.3 (number of new vertices), Problem 5.5 (minimal counterexamples), Question 5.4 (lattice properties) remain unresolved.
   • Some results depend on unpublished work (e.g., Williams' conclusion that HST$(d+3,d)$ is a lattice).
4. Limited scope of algebraic applications:
   • Corollary 1.4 applies only to $\delta=2$.
   • No discussion of generalization to other types of Auslander algebras.
   • Lacks deeper discussion of algebraic significance.

Impact

1. Academic contribution:
   • Foundational result: Solves the natural extension problem on moment curves.
   • Methodology: Height functions and lifting techniques may apply to other geometric problems.
   • Interdisciplinary bridge: Strengthens connections between combinatorial geometry and representation theory.
2. Practical value:
   • Algorithms: Polynomial-time algorithms for $d=3,4$ have potential practical applications.
   • Criteria: Interlacing conditions provide efficient extensibility checking.
3. Reproducibility:
   • All proofs are complete and detailed.
   • Algorithm descriptions are clear (Algorithm in Proposition 5.2).
   • Counterexample constructions are explicit (Propositions 4.1, 4.2, 4.4).
4. Future research:
   • Multiple concrete open problems are posed.
   • Provides new perspectives on higher Stasheff-Tamari posets.
   • May inspire research on other algebraic-combinatorial correspondences.

Applicable Scenarios

1. Theoretical research:
   • Study of combinatorial properties of cyclic polytopes and moment curves.
   • Representation theory of higher cluster categories.
   • Oriented matroids and interlacing patterns.
2. Computational geometry:
   • Triangulation algorithms for low-dimensional ($d \leq 4$) point sets.
   • Analysis of combinatorial structures of convex polytopes.
3. Teaching:
   • Demonstrates combinatorial approaches to geometric problems.
   • Application examples of partial order theory and lattice theory.

Selected References

1. Edelman & Reiner (1996): The higher Stasheff-Tamari posets. Mathematika, 43(1):127-154.
   • Define HST partial orders, prove lattice properties for $d=2,3$.
2. Oppermann & Thomas (2012): Higher-dimensional cluster combinatorics and representation theory. J. Eur. Math. Soc., 14(6):1679-1737.
   • Establish correspondence between $A_n^\delta$ and cyclic polytope triangulations.
3. Rambau (1997): Triangulations of cyclic polytopes and higher Bruhat orders. Mathematika, 44(1):162-194.
   • Provide non-extendable examples for $d=5, n=8$.
4. Williams (2024): The two higher Stasheff-Tamari orders are equal. J. Eur. Math. Soc., published online first.
   • Prove equality of the two HST partial orders.
5. Ziegler (1995): Lectures on polytopes. Graduate Texts in Mathematics, Vol. 152, Springer.
   • Standard reference on cyclic polytopes.

Overall Assessment: This is a high-quality combinatorics paper that completely solves the extension problem on moment curves and establishes profound connections to representation theory. Technically rigorous and innovative, particularly the height function method and the complex proof of Lemma 3.8 demonstrate the authors' deep expertise. While some proofs are lengthy and many open problems remain, these do not diminish the paper's significant contributions to the intersection of discrete geometry and algebraic topology. For researchers studying cyclic polytopes, cluster algebras, or oriented matroids, this is essential reading.