On the number of corner cuts

U. Wagner, Advances in Applied Mathematics 29 (2002) 152–161.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Abstract
A corner cut in dimension d is a finite subset of N0d that can be separated from its complement in N0d by an affine hyperplane disjoint from N0d. Corner cuts were first investigated by Onn and Sturmfels [Adv. Appl. Math. 23 (1999) 29-48], their original motivation stemmed from computational commutative algebra. Let us write (Nd0k)cut for the set of corner cuts of cardinality k; in the computational geometer's terminology, these are the k-sets of N0d. Among other things, Onn and Sturmfels give an upper bound of O(k2d(d-1)/(d+1)) for the size of (Nd0k)cut when the dimension is fixed. In two dimensions, it is known (see [Corteel et al., Adv. Appl. Math. 23 (1) (1999) 49-53]) that #(Nd0k)cut = Θ(k log k). We will see that in general, for any fixed dimension d, the order of magnitude of #(Nd0k)cut is between kd-1 log k and (k log k)d-1. (It has been communicated to me that the same bounds have been found independently by G. Rémond.) In fact, the elements of (Nd0k)cut correspond to the vertices of a certain polytope, and what our proof shows is that the above upper bound holds for the total number of flags of that polytope.
Publishing Year
Date Published
2002-08-01
Journal Title
Advances in Applied Mathematics
Volume
29
Issue
2
Page
152 - 161
IST-REx-ID

Cite this

Wagner U. On the number of corner cuts. Advances in Applied Mathematics. 2002;29(2):152-161. doi:10.1016/S0196-8858(02)00014-3
Wagner, U. (2002). On the number of corner cuts. Advances in Applied Mathematics, 29(2), 152–161. https://doi.org/10.1016/S0196-8858(02)00014-3
Wagner, Uli. “On the Number of Corner Cuts.” Advances in Applied Mathematics 29, no. 2 (2002): 152–61. https://doi.org/10.1016/S0196-8858(02)00014-3.
U. Wagner, “On the number of corner cuts,” Advances in Applied Mathematics, vol. 29, no. 2, pp. 152–161, 2002.
Wagner U. 2002. On the number of corner cuts. Advances in Applied Mathematics. 29(2), 152–161.
Wagner, Uli. “On the Number of Corner Cuts.” Advances in Applied Mathematics, vol. 29, no. 2, ACM, 2002, pp. 152–61, doi:10.1016/S0196-8858(02)00014-3.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar