Characterization of set-families with VC dimension at most 1 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 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$.


*

*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\}$.

*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\}$.

*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
 A: There is a result published by Shai Ben-David which tries to characterize families with VC-dimension at most 1. It says that any family with VC-dimension at most 1 shares a common structure. Check this arxiv link out.
2 Notes on Classes with Vapnik-Chervonenkis Dimension 1
A: 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\}$.
A: There exists a very explicit characterisation of families with small VC dimension in terms of inclusion graph. But the characterisation is for a restricted family which is called s-extremal family or shattering extremal family. Let's define shattering extremal family first.
Define $Sh(\mathcal{F})$ as family of all shattered sets by $\mathcal{F}$.
Proposition: |$Sh(\mathcal{F})| \ge |\mathcal{F}|$ (Check the paper below)
Now the family $\mathcal{F}$ is called s-extremal when the above equation holds equality i.e. |$Sh(\mathcal{F})| = |\mathcal{F}|$.
Tamás Mészáros and Lajos Rónyai have come up with the characterisation for VC-dimension 1 families and also generalised for higher VC-dimension families.
Shattering-Extremal Set Systems of Small VC-Dimension
