Tuesday, April 20, 2010


Do you know anything about computing VC-dimension? Or about the Sauer-Shelah lemma?

Both Wikipedia and the CC blog state the lemma in a way that I do not understand. Namely, they define the VC-dimension as, at some point, determined by the cardinality of the intersection of the set {x1,…,xk} with some other set. And both sources upper bound this number by 2k, which seems absurd: how can it possibly be more than k? We have indexed the set; it has exactly k elements; set intersection is a strictly nonincreasing function in terms of set size.

It also seems unlikely to me that both these sources would have typos. So I must be misunderstanding something.

If you know something about VC-dimension, the Sauer-Shelah lemma, or related combinatorics, please send me an email and I shall grill you with my questions (seasoned with confusion... and paprika, if you like).

Update: I figured it out with the help of these lecture notes. It was an issue of misunderstood notation. (My bad, as usual.)

This post's theme word: curtilage, "an area of land encompassing a dwelling and its surrounding yard, considered as enclosed whether fenced or not." In my present frame of mind, it relates to set theory.

No comments: