VC-dimension?

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 {x₁,…,x_k} with some other set. And both sources upper bound this number by 2^k, 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.

Medieval Times

We sallied forth to Medieval Times this evening, and were duly apportioned to quaff our meals whilst championing the blue knight (Don Alberto del Mau).

Later in the evening, he was hit with a sword to the gut. Yowch. This must have hurt less than his overly expressive body language suggested, since a mere 10 minutes later, he was up on his horse again and waving his blue flag.

V. took photos of the fracas.

This post's theme word: mortmain, "the often stifling influence of the past on the present and the living," or "the perpetual ownership of property by institutions such as churches."