The eliminability conjecture for shattering-extremal set systems

CEU Community + Invited Guests
Thursday, March 19, 2015 - 12:15pm
Add to Calendar
Thursday, March 19, 2015 - 12:15pm

We say that a set system \mathcal{F} \subseteq 2^[n] shatters a given set S \subseteq [n] if 2^S = \{F \cap S : F \in \mathcal{F} \}. The Sauer inequality states that in general, a set system \mathcal{F} shatters at least |\mathcal{F}| sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly |\mathcal{F}| sets. 

When examinig the structure of shattering-extremal set systems, the question naturally arises, whether one can always leave out a set from a shattering-extremal set systems, so that the reulting system is still extremal. We answer this question in the case of families of Vapnik-Chervonenkis dimension 2, by providing a characterization of such extremal set systems in terms of their
inclusion graphs. 

It is a joint work with Lajos Rónyai.