3
$\begingroup$

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).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ You are more likely to get good answers here if (a) you define what you mean by Vapnik-Chervonenkis dimension, and (b) how you showed that the VC dimension of your hypergraph is at least 5. $\endgroup$
    – MTS
    Commented May 30, 2012 at 21:44
  • 1
    $\begingroup$ Posted a week ago to math.stackexchange, math.stackexchange.com/questions/149369/… $\endgroup$
    – Gerry Myerson
    Commented May 30, 2012 at 22:41

2 Answers 2

Reset to default
2
$\begingroup$

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 result).

Edit: According to P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Chapter 8.2 or MathSciNet, MR1274574, 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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Jan, I'm not so convinced by this dual picture, because it has the property that if you can pick a subset of points with a double wedge, then you can also pick it's complement. The original problem doesn't have this property. $\endgroup$
    – Gjergji Zaimi
    Commented Jun 3, 2012 at 22:54
  • $\begingroup$ I see... Thank you for pointing this out. The problem is that the wedges that are dual to the segments should not contain the origin. I am editing the answer accordingly. The dual version with arbitrary double-wedges would be equivalent to the original version for arrangements of lines in the projective plane. $\endgroup$
    – Jan Kyncl
    Commented Jun 4, 2012 at 0:09
  • $\begingroup$ The link to springerlink.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$
    – The Amplitwist
    Commented Apr 30, 2023 at 17:59
3
$\begingroup$

If you take six lines forming the Star of David, then it is impossible to split the lines forming one large triangle from the lines forming the other one.

EDIT. Oh sorry, I misunderstood the concept. If I do understand it correctly now, the dimension is at least 6: on the picture below the 6 lines can be split in any way.

6lines (source)

EDIT2. It is not an example, as Gjergji and Cain notice below.

Improve this answer
$\endgroup$
13
  • $\begingroup$ By the way, what happens in $d$ dimensions? The same example shows that $VC\leq 2d-1$... $\endgroup$
    – Ilya Bogdanov
    Commented May 31, 2012 at 9:44
  • 1
    $\begingroup$ Those six lines are a good example of a groupthat cannot be shattered. But in order to prove that the VC dimension is indeed bounded by 6, It is neccesary to show that every group of size 6 cannot be shattered. $\endgroup$
    – Cain
    Commented May 31, 2012 at 12:14
  • $\begingroup$ Sorry; I have added an example of a good 6-tuple of lines. $\endgroup$
    – Ilya Bogdanov
    Commented May 31, 2012 at 16:23
  • $\begingroup$ The obvious upper bound on the VC-dimension is 10. We have quite a gap here... $\endgroup$
    – Gjergji Zaimi
    Commented Jun 1, 2012 at 6:12
  • $\begingroup$ Btw, your example of six lines doesn't seem to work. How can you split the three lines which form the smallest triangle from the other three? $\endgroup$
    – Gjergji Zaimi
    Commented Jun 1, 2012 at 6:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .