I know that the VC dimension for this problem is 3. My concern is about the growth function. The following bound is obtained using the VC dimension: $$m_{\mathcal{H}}(n)\le \sum_{k=0}^3\,{n\choose k}$$ When I simulate this hypothesis set up to $n= 10$, the maximum number of dichotomies I obtain is exactly $\sum_{k=0}^{3}\,{n\choose k}$. Is it by coincidence or is there a way to prove this?

  • $\begingroup$ Your question might be more suitable for math.stackexchange.com $\endgroup$
    – Jonathan
    Mar 4, 2020 at 7:39
  • $\begingroup$ Unfortunately your question is not clear! You have inequality and reach the maximum which satisfies it. You can count all possible dichotomies as well. What do you wanna prove here? $\endgroup$
    – OmG
    Apr 13, 2020 at 13:07
  • $\begingroup$ I reach the maximum for n up to 10, since I can count all possible dichotomies for n up to 10 (I cannot go beyond with my computer). I am asking help for a mathematical proof for all n>0. $\endgroup$
    – Ali Kara
    Apr 15, 2020 at 10:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.