Let $H$ be a set-family (a set of sets). For every set $g$, define the *intersection set-family*:


$$ H\cap g := \{h\cap g| h\in H \}$$


For every set $g$, the family $H\cap g$ contains at most $2^{|g|}$ sets (the subsets of $g$). 


Call $H$ **simple** if, for all two-element sets $g = \{x,y\}$, the family $|H\cap g|$ contains at most $3$ sets.


(in other words, $H$ is simple iff its [VC dimension](https://en.wikipedia.org/wiki/VC_dimension) is at most $1$).


My goal is to characterize the combinatorial structure of simple set-families.


I found some sufficient conditions for simplicity of $H$. In all cases, I assume that $g=\{x,y\}$, and prove that $H\cap g$ cannot contain one of the four subsets of $g$.


1. If $H$ is a chain (each set of $H$ either contains or is contained in any other set of $H$) then $H$ is simple. *Proof*: Suppose $H\cap g$ contains the set $\{x\}$. Then some set $h\in H$ contains $x$ and not $y$. Every other set in $H$ either contains $h$ (so it also contains $x$), or is contained in $h$ (so it does not contain $y$). So, $H\cap g$ does not contain $\{y\}$.
2. More generally, if $H$ is a collection of disjoint chains, then $H$ is simple. The proof is similar: if some set $h\in H$ contains $x$ and not $y$, then every other set in $H$ either contains $h$ (so it also contains $x$), or is contained in $h$ (so it does not contain $y$) or is disjoint from $h$ (so it contains neither $x$ nor $y$). In all cases $H\cap g$ does not contain $\{y\}$.
3. More generally, suppose $H$ has the following tree structure: it contains the empty set as the "root"; this root has several children which are singletons; each singleton $\{z\}$ has as children several pairs that contain $z$; and so on. A set is a child of another set if it contains it; there are no intersections between sets except through the edges of the tree. Then, $H$ is simple. *Proof*: Suppose $H\cap g$ contains the set $\{x\}$. Then some set $h\in H$ contains $x$ and not $y$. If some other set $h'\in H$ contains $\{x,y\}$, then $h'$ must be a descendant of $h$ in the tree, so there is no other set which contains only $y$, so $H\cap g$ does not contain $\{y\}$.


These conditions are obviously not necessary. For example, the following set-family is simple:


$$ H = \{ \{1,2\}, \{2,3\}, \{3,1\} \}$$


since for every $g=\{x,y\}$, if $H\cap g$ contains the set $\{x,y\}$, then it does not contain the empty set.


**What is a simple combinatorial characterization of the simple set-families?**


cross-posted from [math.SE](https://math.stackexchange.com/q/2308693/29780)



Characterization of set-families with VC dimension at most 1
The four examples can be built by the following four operations on set systems, starting from empty systems on one-element set systems of type $(\{x\},\{\emptyset\})$:


I) **subsystem**: If $(A,H)$ is a set system and $H'\subset H$, we create a new set system $(A,H')$. 


II) **disjoint union**: If $(A\_1,H\_1)$ and $(A\_2,H\_2)$ are two set systems with $A\_1\cap A\_2=\emptyset$, we create a new set system $(A\_1\cup A\_2, H\_1 \cup H\_2)$.


III) **complementation**: If $(A,H)$ is a set system, we create a new set system $(A,H^\*)$ where $H^\*=\{h; A\setminus h\in H\}$.


IV) **adding an empty set if possible**: If $(A,H)$ is a set system of type 3), we create a new set system $(A,H\cup\{\emptyset\})$.


This creates a larger set of examples. Whether this is a complete characterization of set systems of $VC$-dimension 1 is not clear to me yet.


There is a finer version of operation III:


III\*) **switch of one element**: If $(A,H)$ is a set system and $a\in A$, we create a new set system $(A,H\_a)$ where $H\_a=\{h; a\in h, h\setminus \{a\}\in H\}\cup \{h; a\notin h, h\cup \{a\}\in H\}$.


