One Construction for the Miura-ori Flip-Graph Degree Sequence

Jul 16, 2026

Upload by Liam

Flip graphs of origami crease patterns use flat-foldable mountain-valley assignments as vertices, with edges linking assignments differing by a single face flip; vertex degree counts admissible face flips. For the m×n Miura-ori, the degree sequence is known as a bivariate polynomial only for small degrees, via separate growing casework. This work provides a uniform construction giving, for every degree d, a symmetric polynomial pd(m,n) for all sufficiently large m,n, with total degree d−2 under a single degree bound, proved for separable configurations and verified through d=7.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages23

Reading Time58 min

Introduction

The height-function reduction

Vertex counts

arXiv :2607 .05567v1 [math .CO] 6 Jul 2026 One construction for the Miura-ori flip-graph degree sequence Chakshu Gupta College of Computing, Georgia Institute of Technology [cgupta65@gatech.edu](cgupta65@gatech.edu) Abstract The flip graph of an origami crease pattern has the flat-foldable mountain-valley assignments as vertices, and an edge joins two of them that differ by a single face flip. A basic invariant of this graph is the degree sequence, which counts the vertices of each degree. On the m × n Miura-ori, this sequence is known as a bivariate polynomial only for small degrees, each count obtained by a separate argument whose casework grows with the degree. This paper gives one uniform construction that expresses, for every degree d, the number of degree-d vertices as a single symmetric polynomial pd (m, n) for all sufficiently large m, n. Subject to a single degree bound, this polynomial has total degree d − 2, growing for d ≥ 5 as an explicit multiple of md−2 + nd−2; the bound is proved here when the count splits into independent row and column factors, and open otherwise. The region is m, n ≥ max(d − 1 , 2); through d = 7, the polynomials are computed in closed form and the bound is verified in every case. Below this region, the count departs from pd by a correction whose leading coefficient, through degree eleven, is −4 times a Baxter number. Each pd thus counts the Miura-ori’s flat-foldable assignments admitting exactly d single face flips. 1 Introduction A crease pattern’s flat-foldable mountain-valley assignments are the vertices of its origami flip graph OFG [HMNTS22], with an edge between two that differ by a single face flip [ADE+20] . A vertex’s degree is then the number of face flips it admits. For the m × n Miura-ori Mm,n [Miu94], a basic invariant of OFG(Mm,n) is its degree sequence, the number of vertices of each degree. The count is known for every d at m = 2 [CHO+25], and for d ≤ 5 at all sufficiently large m, n, where it is a symmetric polynomial in (m, n) of total degree d − 2 [Gup26] . Each was proved by a separate argument, the first only at m = 2 and the second only for d ≤ 5. Whether the count is a polynomial for every d, and whether one construction can prove it uniformly, are the questions taken up here. Both questions are answered by a three-part construction, built on the height-function reduction of Section 2. Under the Ginepro–Hull bijection [GH14] and the bipartite height-function lift [CvdHJ09], OFG(Mm,n) is identified with the integer height functions on the m × n grid, and a vertex’s degree equals its number of strict local extrema [Gup26] . First, the envelope encoding (Theorem 3.6) represents each height function by an integer configuration; counting the configurations with d extrema is then a parametric lattice-point problem, piecewise quasi-polynomial in (m, n) by the Barvinok–Woods theory [BW03, BW22](Theorem 5.1) . Second, this quasi-polynomial becomes a single symmetric polynomial pd(m, n) on m, n ≥ max(d−1, 2) (Theorem 8.9); this existence, symmetry, region, and per-axis degree are unconditional. Its total degree and leading term rest on a degree bound (Conjecture 7.1): subject to the bound, the total degree is d − 2, and for d ≥ 5 the top-degree part is the pure power 4/(d − 2)!(md−2 + nd−2) (Theorem 7.3) . Third, pd is computed in closed form for d ≤ 7 (Section 9); the degree bound (Conjecture 7.1) is proved for the separable configurations (Theorem 10.3), where the count splits into independent row and column factors, and verified in every case by direct enumeration through d = 7 in a self-contained codebase.1 Thenon-separable case remains open for d ≥ 8. 2 The height-function reduction By the Ginepro–Hull bijection [GH14] and the bipartite height-function lift [CvdHJ09], applied to Mm,n in [Gup26], the vertices of OFG(Mm,n) are integer height functions on the m × n grid. This grid, Gm,n, has cells (i, j), 1 ≤ i ≤ m, 1 ≤ j ≤ n, adjacent when they differ

FAQs

What does the degree sequence in the Miura-ori flip graph count?

It counts, for each degree d, how many flat-foldable mountain-valley assignments (vertices) admit exactly d single face flips.

How is the flip graph reformulated in this paper?

Using the Ginepro–Hull bijection and a bipartite height-function lift, the vertices correspond to integer height functions on an m×n grid, and vertex degree equals the number of strict local extrema.

What is the main result about the polynomial pd(m,n)?

For sufficiently large m,n, the number of degree-d vertices is given by a single symmetric polynomial pd(m,n) in m and n, with total degree d−2 and an explicit leading-term form under a degree bound.

Jul 16, 2026

Upload by Liam