View Single Post
Old 09-01-2012, 10:34 AM
vsthakur vsthakur is offline
Join Date: Jun 2012
Posts: 14
Default Re: Problem 2.10

Originally Posted by yaser View Post
Actually, we also know the definition of growth functions, and this may be the key to answering the question.
I think i get it now. Let m_H(N)=k. Now, if we partition any set of 2N points into two sets of N points each, each of these two partitions will produce k dichotomies at best. If we now combine these two sets, then the maximum no. of dichotomies possible will be the cross product of the two sets of dichotomies (with N points each), i.e.,
m_H(2N) \le k^2 = m_h(N)^2

Thank you.
Reply With Quote