I'm having some problems with this problem concerning VC dimensions (<http://en.wikipedia.org/wiki/VC_dimension>), I hope for some helping input.


Given a set $L$ of $n$ lines in the plane, define a hypergraph $H=(L,S)$ such that its vertices are the lines and a subset $l$ of $L$ belongs to $S$ iff there exist points $p$ and $q$ such that all lines in $l$ lie between $p$ and $q$, what is the VC dimension of $H$?


Now, I've managed to show the VC dimension is at least 5, I basically found a group of 5 lines with 4 of them being parallel to each other with differing lengths and the fifth being perpendicular to the four.
but I can't think of a solid proof why it shouldn't be more than 5 (it might be more, it's a bit confusing to me).



Vapnik-Chervonenkis dimension of lines in the plane
If I understand the question correctly, a subset $l$ of lines belongs to $S$ if and only if there is a straight-line segment crossing exactly the lines from $l$.


The problem is then equivalent to the following dual version:



> 
> What is the maximum VC-dimension of a finite set of points in the plane, with respect to the double-wedges that do not contain the origin?
> 
> 
> 


Where by "double-wedge" I mean the union of two opposite regions of the plane between two crossing lines.


It is easy to see that a set of $6$ points in convex position cannot be shattered. Since every set of $17$ points in convex position contains a convex $6$-gon, the VC-dimension is at most 16.


The next step could be investigating all configurations of $6$ points plus the origin if there is some configuration that can be shattered.


[The answer was edited after Gjergji's comment.]




---


One can, indeed, show that the VC-dimension is at most $10$ by a counting argument outlined by Gjergji.
A pair of faces containing the endpoints of the segment determines the subset $l$. For lines in general position, there are $${1+{n+1 \choose 2} \choose 2}$$
pairs of faces, which is still more than $2^n-1$ for $n=11$. But some of the subsets $l$ were overcounted: every $1$-element set was counted $n-1$ times and every $2$-element set at least twice, so we can subtract $3/2 \cdot n(n-1)$. In this way, we get an upper bound $2046$ for the number of subsets $l$ for $n=11$, which is just enough to show that the VC-dimension is at most $10$. Further improvements are possible, for example by considering overcounted triples or by considering the faces with more than $3$ vertices (using
[this](http://www.springerlink.com/content/gl3p7q16787p6428/) result).




---


**Edit:** According to [P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Chapter 8.2](https://doi.org/10.1007/0-387-29929-7_9 "zbMATH review at https://zbmath.org/1086.52001") or [MathSciNet, MR1274574](https://mathscinet.ams.org/mathscinet-getitem?mr=1274574),
Harborth and Möller [1] proved that every simple arrangement of $9$ pseudolines in the projective plane contains a subarrangement of six pseudolines with a hexagonal face. No such arrangement can be shattered: a triple of pseudolines determined by every other edge of the hexagonal face cannot be crossed by a pseudosegment that avoids the other three pseudolines. This shows that the VC-dimension is at most $8$, even in the stronger setting of pseudolines in the projective plane.


[1]: H. Harborth and M. Möller, Esther Klein problem in projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171--179. [Zbl 0807.51008](https://zbmath.org/0807.51008).


