VC-Dimension and sample complexity dependent on size of subsets
No, you cannot. See Thm 2.1 of http://link.springer.com/article/10.1007%2FBF02187833 (it says that a random family gives an example, with appropriately chosen parameters).