Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The Sylvester–Gallai Theorem

futilitycloset.com

Post reply on HN
Print view View original

31–40 of 52 posts

Re: The Sylvester–Gallai Theorem

#31

Post by fxwin »

Sniffnoy wrote: post #10
hyperhello wrote: post #3

> Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points. I can't make out the point here (no pun). Of course a line can pass through any two points. It could pass through three if those points were collinear but the statement says they're not. So what is the new fact?

I think what's going on here is that you've misunderstood the theorem's hypothesis. The hypothesis isn't that no three of the points are collinear; rather, it's the weaker statement that there isn't any one single line that all the points lie on. It's true that with your version of the hypothesis the theorem would be trivial; but with the actual hypothesis it is is nontrivial.

> hypothesis

I think you meant premise?

Re: The Sylvester–Gallai Theorem

#32

Post by squirrel »

tzs wrote: post #6
hyperhello wrote: post #3

> Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points. I can't make out the point here (no pun). Of course a line can pass through any two points. It could pass through three if those points were collinear but the statement says they're not. So what is the new fact?

It can help to think about theorems like this by restating them as a puzzle asking for a counterexample. Given N points, N > 2, can you arrange them in a Euclidean plane so that (1) they are not all on the same line, and (2) every line that goes through two of the points must also go through at least one more of the points? The theorem says that you cannot do this.

Well put. A similar way to say it: ask the 9 year old to draw ALL of the possible lines connecting two points in the set — of course this is possible, just might take awhile. The theorem says that at least one of the lines drawn must hit ONLY the two points the 9 year old used when drawing that particular line, not any others.

Re: The Sylvester–Gallai Theorem

#33

Post by ky3 »

scythe wrote: post #9
glimshe wrote: post #7

Earlier quoted context omitted.

Try to come up with a set non-colinear points where NO line passes through two and ONLY TWO points and you'll see the value of the statement. You may think "I'm sure I can arrange these points in a way where EVERY line will cross three or more points" but you will fail if you try unless ALL points are colinear.

This is true for finite sets. For infinite sets, the Sierpinski triangle is a counterexample.

> the Sierpinski triangle is a counterexample

How so? It's bounded by the large initial triangle. The line containing any two of the vertices doesn't intersect any other point.

Re: The Sylvester–Gallai Theorem

#34

Post by fxwin »

hyperhello wrote: post #3

> Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points. I can't make out the point here (no pun). Of course a line can pass through any two points. It could pass through three if those points were collinear but the statement says they're not. So what is the new fact?

> It could pass through three if those points were collinear but the statement says they're not

The theorem doesn't presume that no three points are collinear, it presumes that the set as a whole isn't collinear, which is a much weaker statement.

Re: The Sylvester–Gallai Theorem

#35

Post by fxwin »

stackghost wrote: post #11

>Every finite set of points in the Euclidean plane that is not collinear has a line that passes through exactly two of the points. Isn't this a tautology? The problem definition states that the set of points is in Euclidean space, which from Euclid's Axioms means we can draw a line between any two points. The set of points is defined to be not collinear, thus we cannot draw a line passing through more than two of the…

> The set of points is defined to be not collinear, thus we cannot draw a line passing through more than two of them

This is wrong and you are misunderstanding what collinearity means. You could have a set of points where all but one are on the same line, and the set of a whole will be not collinear, while we can obviously draw a line that passes through more than two of them.

A different way of stating the theorem is that any finite set of points has either a line passing through all points (i.e. the set is collinear) or there exists a line that passes through exactly two points. This dichotomy (why two and not three? Why can't we construct a set where any line passes through at least three points?) is not immediately obvious.

Re: The Sylvester–Gallai Theorem

#36

Post by squirrel »

squirrel wrote: post #32
tzs wrote: post #6

Earlier quoted context omitted.

It can help to think about theorems like this by restating them as a puzzle asking for a counterexample. Given N points, N > 2, can you arrange them in a Euclidean plane so that (1) they are not all on the same line, and (2) every line that goes through two of the points must also go through at least one more of the points? The theorem says that you cannot do this.

Well put. A similar way to say it: ask the 9 year old to draw ALL of the possible lines connecting two points in the set — of course this is possible, just might take awhile. The theorem says that at least one of the lines drawn must hit ONLY the two points the 9 year old used when drawing that particular line, not any others.

I just thought of another way to restate. Suppose you give me any finite set of points, any finite set at all, and you also tell me that when the 9 year old draws any line through any two of them, she will always hit a third. Then I can immediately conclude all the points lie on a single line, that is, that any line the 9 year old draws will hit all the points.

Re: The Sylvester–Gallai Theorem

#37

Post by frotaur »

In the proof, it claims that "At least two of these must fall on the same side of P′, the perpendicular projection of P on ℓ.".

However, this is not true as it is possible that P'=B. However it seems the proof still goes through (at least as depicted in the image, haven't thought hard about the general case).

Re: The Sylvester–Gallai Theorem

#38

Post by cirpis »

frotaur wrote: post #37

In the proof, it claims that "At least two of these must fall on the same side of P′, the perpendicular projection of P on ℓ.". However, this is not true as it is possible that P'=B. However it seems the proof still goes through (at least as depicted in the image, haven't thought hard about the general case).

I dont think theres an issue, the point P' simply belongs to both sides of itself. With this convention in place it is still true that there are two points in the same side, and the proof goes through verbatim.

Its mostly a question of whether you count the line defining a half-plane as belonging to the half plane or not, and clearly they do here

Re: The Sylvester–Gallai Theorem

#39

Post by tzs »

scythe wrote: post #9
glimshe wrote: post #7

Earlier quoted context omitted.

Try to come up with a set non-colinear points where NO line passes through two and ONLY TWO points and you'll see the value of the statement. You may think "I'm sure I can arrange these points in a way where EVERY line will cross three or more points" but you will fail if you try unless ALL points are colinear.

This is true for finite sets. For infinite sets, the Sierpinski triangle is a counterexample.

That’s an uncountable set. If we want a counter example for uncountable sets a simpler example is a circular area.

Anyone happen to know if it is true for countably infinite sets?

Re: The Sylvester–Gallai Theorem

#40

Post by glimshe »

JetSetWilly wrote: post #28
glimshe wrote: post #7

Earlier quoted context omitted.

Try to come up with a set non-colinear points where NO line passes through two and ONLY TWO points and you'll see the value of the statement. You may think "I'm sure I can arrange these points in a way where EVERY line will cross three or more points" but you will fail if you try unless ALL points are colinear.

You can always find a line that passes between two points. Why would you even try to find a line that doesn’t pass between two points? What is the difficult part here.

The difficult part is that you may think that there's an arrangement where you could force every line to go through 3 or more points. The line extends to infinity, keep in mind.
Post reply on HN