Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 parrlell 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, its a bit confusing to me).

Thanks a lot.

share|improve this question
1  
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. –  MTS May 30 '12 at 21:44
1  
Posted a week ago to math.stackexchange, math.stackexchange.com/questions/149369/… –  Gerry Myerson May 30 '12 at 22:41
    
You are right, thank you. –  Cain May 31 '12 at 12:24
add comment

2 Answers 2

up vote 2 down vote accepted

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, Harbort and Moller [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. Harbort and M. Moller, Esther Klein problem in projective plane, J. Combin. Math. Combin. Comput. 15 (1994), 171--179.

share|improve this answer
1  
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. –  Gjergji Zaimi Jun 3 '12 at 22:54
    
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. –  Jan Kyncl Jun 4 '12 at 0:09
add comment

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

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

share|improve this answer
    
By the way, what happens in $d$ dimensions? The same example shows that $VC\leq 2d-1$... –  Ilya Bogdanov May 31 '12 at 9:44
1  
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. –  Cain May 31 '12 at 12:14
    
Sorry; I have added an example of a good 6-tuple of lines. –  Ilya Bogdanov May 31 '12 at 16:23
    
The obvious upper bound on the VC-dimension is 10. We have quite a gap here... –  Gjergji Zaimi Jun 1 '12 at 6:12
    
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? –  Gjergji Zaimi Jun 1 '12 at 6:59
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.