OFFSET
1,1
COMMENTS
A subset S of [n]^3 = {1,...,n}^3 with componentwise order is order-convex if whenever a, b in S with a <= c <= b, then c in S.
The growth rate log a(n) = Theta(n^2) is for all d >= 2 (the dimension law); the exponent 2 = d-1 for d=3 detects the spacetime dimension.
The 2-dimensional analog (square grid) is A393665.
REFERENCES
B. Barnette, W. Nichols, and T. Richmond, The number of convex sets in a product of totally ordered sets, Rocky Mountain J. Math., 49 (2019), no. 2, 369-385.
LINKS
Thomas DiFiore, Lean 4 formal verification.
Thomas DiFiore, Order-Convex Subsets of Grid Posets, Zenodo.
B. Barnette, W. Nichols, and T. Richmond, The number of convex sets in a product of totally ordered sets, Rocky Mountain J. Math. 49(2): 369-385 (2019).
FORMULA
a(m+n) >= a(m)*a(n) for all m, n >= 1 (supermultiplicativity).
a(n) <= C(2*n,n)^4 (ideal/filter injection).
log a(n) = Theta(n^2) (dimension law for d=3). The growth constant c_3 = lim log(a(n))/n^2 is conjectured to equal 16*log(2)/7 = 1.5842... based on c_2/c_3 = 7/4 to 4 significant figures (where c_2 = log(16) is the growth constant for d=2, A393665).
EXAMPLE
a(1) = 2: the empty set and {(1,1,1)}.
a(2) = 101: the order-convex subsets of the 8-element Boolean lattice [2]^3.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Thomas DiFiore, Mar 28 2026
STATUS
approved