Distinct Volume Subsets

Abstract

Suppose that a and d are positive integers with a ≥ 2. Let h_(a,d)(n) be the largest integer t such that any set of n points in ℝ^d contains a subset of t points for which all the nonzero volumes of the [equaton; see abstract in PDF for details] subsets of order a are distinct. Beginning with Erdős in 1957, the function h_(2,d)(n) has been closely studied and is known to be at least a power of n. We improve the best known bound for h_(2,d)(n) and show that h_(a,d)(n) is at least a power of n for all a and d.

Additional Information

© 2015 Society for Industrial and Applied Mathematics. Received by the editors January 27, 2014; accepted for publication (in revised form) December 16, 2014; published electronically March 11, 2015. Conlon's research was supported by a Royal Society University Research Fellowship. Fox's research was supported by a Packard Fellowship, by a Simons Fellowship, by NSF grant DMS-1069197, by an Alfred P. Sloan Research Fellowship, and by an MIT NEC Corporation Award. The authors would like to thank Tucker Bane, Andrew Lohr, Jared Marx-Kuo, Joe Mileti, Jessica Shi, Srinivas Vasudevan, and Yufei Zhao for helpful discussions.

Attached Files

Submitted - 1401.6734.pdf

Published - 140954519.pdf

Files

Additional details