View Single Post
Old 09-03-2012, 06:54 AM
magdon's Avatar
magdon magdon is offline
Join Date: Aug 2009
Location: Troy, NY, USA.
Posts: 597
Default Re: Problem 2.10

Yes, well done.

Originally Posted by vsthakur View Post
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.
Have faith in probability
Reply With Quote