Order-Convex Subsets of Grid Posets: A New Exponential Combinatorial Class with Structural Classication, Transfer-Matrix Enumeration, and a Supermultiplicativity Theorem
Fuente:
Zenodo
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Recurso digital |
| Pubblicazione: |
Zenodo
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866901962237149184 |
|---|---|
| author | DiFiore, Thomas |
| author_facet | DiFiore, Thomas |
| contents | <p>We study the number |CC([m]²)| of order-convex subsets of the m×m grid poset. The sequence 2, 13, 114, 1146, 12578, 146581, ... has growth constant ρ = 16 exactly, proved via a Lindström-type domain-splitting injection that bounds crossing pairs of antitone boundary functions, combined with a Fekete squeeze argument. The upper bound ρ ≤ 16 follows from the ideal/filter injection into pairs of antitone functions counted by C(2m,m). The lower bound |CC([m]²)| ≥ C(2m,m)²/(2(m+1)) closes the gap. For d-dimensional grids with d ≥ 3, the 1/m normalization diverges; the correct normalization is c_d = lim log|CC([m]^d)|/m^{d-1}, which exists by Fekete's lemma applied to the superadditive sequence. The dimension law log|CC([m]^d)| = Θ(m^{d-1}) is proved for all d ≥ 2 via an antichain tiling construction. A transfer-matrix dynamic program with O(n²) boundary parameters enables computation of 50 exact terms. The generating function is likely not D-finite (no recurrence of order ≤ 5 with polynomial coefficients of degree ≤ 4 found). Since ρ = 16 > 6⁶/5⁵ ≈ 14.93, this sequence does not belong to the (6,2) generalized Fuss-Catalan family despite matching its first three terms. All structural and asymptotic results are formally verified in Lean 4 (zero sorry). Part II of a four-paper series on causal-algebraic geometry.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_5281_zenodo_19324414 |
| institution | Zenodo |
| language | |
| publishDate | 2026 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | Order-Convex Subsets of Grid Posets: A New Exponential Combinatorial Class with Structural Classication, Transfer-Matrix Enumeration, and a Supermultiplicativity Theorem DiFiore, Thomas order-convex subset, product poset grid poset growth constant Fekete's lemma supermultiplicativity transfer matrix Dilworth theorem dimension law combinatorial class Fuss-Catalan numbers formal verification Lean <p>We study the number |CC([m]²)| of order-convex subsets of the m×m grid poset. The sequence 2, 13, 114, 1146, 12578, 146581, ... has growth constant ρ = 16 exactly, proved via a Lindström-type domain-splitting injection that bounds crossing pairs of antitone boundary functions, combined with a Fekete squeeze argument. The upper bound ρ ≤ 16 follows from the ideal/filter injection into pairs of antitone functions counted by C(2m,m). The lower bound |CC([m]²)| ≥ C(2m,m)²/(2(m+1)) closes the gap. For d-dimensional grids with d ≥ 3, the 1/m normalization diverges; the correct normalization is c_d = lim log|CC([m]^d)|/m^{d-1}, which exists by Fekete's lemma applied to the superadditive sequence. The dimension law log|CC([m]^d)| = Θ(m^{d-1}) is proved for all d ≥ 2 via an antichain tiling construction. A transfer-matrix dynamic program with O(n²) boundary parameters enables computation of 50 exact terms. The generating function is likely not D-finite (no recurrence of order ≤ 5 with polynomial coefficients of degree ≤ 4 found). Since ρ = 16 > 6⁶/5⁵ ≈ 14.93, this sequence does not belong to the (6,2) generalized Fuss-Catalan family despite matching its first three terms. All structural and asymptotic results are formally verified in Lean 4 (zero sorry). Part II of a four-paper series on causal-algebraic geometry.</p> |
| title | Order-Convex Subsets of Grid Posets: A New Exponential Combinatorial Class with Structural Classication, Transfer-Matrix Enumeration, and a Supermultiplicativity Theorem |
| topic | order-convex subset, product poset grid poset growth constant Fekete's lemma supermultiplicativity transfer matrix Dilworth theorem dimension law combinatorial class Fuss-Catalan numbers formal verification Lean |
| url | https://doi.org/10.5281/zenodo.19324414 |