235:. The projective plane can be formed from the Euclidean plane by adding extra points "at infinity" where lines that are parallel in the Euclidean plane intersect each other, and by adding a single line "at infinity" containing all the added points. However, the additional points of the projective plane cannot help create non-Euclidean finite point sets with no ordinary line, as any finite point set in the projective plane can be transformed into a Euclidean point set with the same combinatorial pattern of point-line incidences. Therefore, any pattern of finitely many intersecting points and lines that exists in one of these two types of plane also exists in the other. Nevertheless, the projective viewpoint allows certain configurations to be described more easily. In particular, it allows the use of
436:
3844:
251:
2652:
2253:
22:
283:
ordinary points (corresponding to the four pairs of opposite parallelograms). An equivalent statement of the
Sylvester–Gallai theorem, in terms of zonohedra, is that every zonohedron has at least one parallelogram face (counting rectangles, rhombuses, and squares as special cases of parallelograms). More strongly, whenever sets of
278:, called generators. In this connection, each pair of opposite faces of a zonohedron corresponds to a crossing point of an arrangement of lines in the projective plane, with one line for each generator. The number of sides of each face is twice the number of lines that cross in the arrangement. For instance, the
4043:
for these points is an equality, and a line is defined from any pair of points by repeatedly including additional points that are collinear with points already added to the line, until no more such points can be added. The generalization of Chvátal and Chen states that every finite metric space has a
1623:, an axiomatization of geometry in terms of betweenness that includes not only Euclidean geometry but several other related geometries. Coxeter's proof is a variation of an earlier proof given by Steinberg in 1944. The problem of finding a minimal set of axioms needed to prove the theorem belongs to
406:
The
Sylvester–Gallai theorem has been proved in many different ways. Gallai's 1944 proof switches back and forth between Euclidean and projective geometry, in order to transform the points into an equivalent configuration in which an ordinary line can be found as a line of slope closest to zero; for
282:
shown is a zonohedron with five generators, two pairs of opposite hexagon faces, and four pairs of opposite parallelogram faces. In the corresponding five-line arrangement, two triples of lines cross (corresponding to the two pairs of opposite hexagons) and the remaining four pairs of lines cross at
1069:
In 1941 (thus, prior to Erdős publishing the question and Gallai's subsequent proof) Melchior showed that any nontrivial finite arrangement of lines in the projective plane has at least three ordinary points. By duality, this results also says that any finite nontrivial set of points on the plane
2216:
As the authors prove, the line returned by this algorithm must be ordinary. The proof is either by construction if it is returned by step 4, or by contradiction if it is returned by step 7: if the line returned in step 7 were not ordinary, then the authors prove that there would exist an ordinary
3927:
proved a complex-number analogue of the
Sylvester–Gallai theorem: whenever the points of a Sylvester–Gallai configuration are embedded into a complex projective space, the points must all lie in a two-dimensional subspace. Equivalently, a set of points in three-dimensional complex space whose
3540:
of maximizing the number of three-point lines, which Green and Tao also solved for all sufficiently large point sets. In the dual setting, where one is looking for ordinary points, one can consider the minimum number of ordinary points in an arrangement of pseudolines. In this context, the
3030:. Because of this connection, the Kelly–Moser example has also been called the non-Fano configuration. The other counterexample, due to McKee, consists of two regular pentagons joined edge-to-edge together with the midpoint of the shared edge and four points on the line at infinity in the
1646:
that is rejected as an axiom of constructive mathematics. Nevertheless, it is possible to formulate a version of the
Sylvester–Gallai theorem that is valid within the axioms of constructive analysis, and to adapt Kelly's proof of the theorem to be a valid proof under these axioms.
60:. Another way of stating the theorem is that every finite set of points that is not collinear has an ordinary line. According to a strengthening of the theorem, every finite point set (not all on one line) has at least a linear number of ordinary lines. An
3760:
points, by deleting an ordinary line and one of the two points on it (taking care not to delete a point for which the remaining subset would lie on a single line). Thus, it follows by mathematical induction. The example of a near-pencil, a set of
239:, in which the roles of points and lines in statements of projective geometry can be exchanged for each other. Under projective duality, the existence of an ordinary line for a set of non-collinear points in RP is equivalent to the existence of an
1193:
are the number of vertices, edges, and faces of the graph, respectively. Any nontrivial line arrangement on the projective plane defines a graph in which each face is bounded by at least three edges, and each edge bounds two faces; so,
3915:, and it cannot be realized by points and lines of the Euclidean plane. Another way of stating the Sylvester–Gallai theorem is that whenever the points of a Sylvester–Gallai configuration are embedded into a Euclidean space, preserving
1313:, contradicting this inequality. Therefore, some vertices must be the crossing point of only two lines, and as Melchior's more careful analysis shows, at least three ordinary vertices are needed in order to satisfy the inequality
3879:
for the projective plane), analogous abstract systems of points and lines can be defined by using other number systems as coordinates. The
Sylvester–Gallai theorem does not hold for geometries defined in this way over
1598:
3819:, considers finite planar sets of points (not all in a line) that are given two colors, and asks whether every such set has a line through two or more points that are all the same color. In the language of sets and
1619:) writes of Kelly's proof that its use of Euclidean distance is unnecessarily powerful, "like using a sledge hammer to crack an almond". Instead, Coxeter gave another proof of the Sylvester–Gallai theorem within
262:. Its eight red parallelogram faces correspond to ordinary points of a five-line arrangement; an equivalent form of the Sylvester–Gallai theorem states that every zonohedron has at least one parallelogram face.
3851:, in which the line through every pair of points contains a third point. The Sylvester–Gallai theorem shows that it cannot be realized by straight lines in the Euclidean plane, but it has a realization in the
1510:
247:
of finitely many lines. An arrangement is said to be trivial when all its lines pass through a common point, and nontrivial otherwise; an ordinary point is a point that belongs to exactly two lines.
1655:
Kelly's proof of the existence of an ordinary line can be turned into an algorithm that finds an ordinary line by searching for the closest pair of a point and a line through two other points.
3134:
170:) in which each line determined by two of the points contains a third point. The Sylvester–Gallai theorem implies that it is impossible for all nine of these points to have real coordinates.
2561:
2506:
3069:
3576:
3191:
2929:. As with any finite configuration in the real projective plane, this construction can be perturbed so that all points are finite, without changing the number of ordinary lines.
2646:
423:
showed that the metric concepts of slope and distance appearing in Gallai's and Kelly's proofs are unnecessarily powerful, instead proving the theorem using only the axioms of
3012:
2727:
3795:
The
Sylvester–Gallai theorem has been generalized to colored point sets in the Euclidean plane, and to systems of points and lines defined algebraically or by distances in a
2288:
While the
Sylvester–Gallai theorem states that an arrangement of points, not all collinear, must determine an ordinary line, it does not say how many must be determined. Let
3348:
2384:
3398:
3280:
1819:
1346:
1288:
1233:
120:
2183:
2156:
2127:
2100:
2073:
1899:
992:
961:
396:
2847:
2432:
2322:
1777:
1733:
1693:
930:
902:
337:
1391:
854:
749:
624:
3514:
4900:
3425:
2730:
2242:
2210:
2043:
2016:
1986:
1956:
1926:
1861:
1418:
1107:
1059:
1039:
664:
579:
552:
532:
419:
shows by contradiction that the connecting line with the smallest nonzero distance to another point must be ordinary. And, following an earlier proof by
Steinberg,
4005:
2804:
3936:
showed that whenever a
Sylvester–Gallai configuration is embedded into a space defined over the quaternions, its points must lie in a three-dimensional subspace.
3785:
3758:
3692:
3604:
3453:
3306:
3245:
3219:
2282:
1311:
411:. The 1941 proof by Melchior uses projective duality to convert the problem into an equivalent question about arrangements of lines, which can be answered using
5335:
3974:
3732:
3712:
3662:
3642:
3534:
3473:
3154:
2950:
2927:
2907:
2887:
2867:
2775:
2751:
2677:
2581:
2452:
2342:
1438:
1253:
1191:
1171:
1151:
1127:
1019:
874:
829:
809:
789:
769:
724:
704:
684:
644:
599:
512:
492:
472:
357:
301:
82:
3536:. Thus, the constructions of Böröczky for even and odd (discussed above) are best possible. Minimizing the number of ordinary lines is closely related to the
4007:
two-point lines, or equivalently every rank-3 matroid with fewer two-point lines must be non-orientable. A matroid without any two-point lines is called a
3911:(the inflection points of a cubic curve), in which every line is non-ordinary, violating the Sylvester–Gallai theorem. Such a configuration is known as a
6013:
3665:
3615:
5459:
1991:
For each two consecutive groups of points, in the sorted sequence by their angles, form two lines, each of which passes through the closest point to
216:
3018:, consists of the vertices, edge midpoints, and centroid of an equilateral triangle; these seven points determine only three ordinary lines. The
5570:
5821:
1521:
1743:
also shows how to construct the dual arrangement of lines to the given points (as used in
Melchior and Steenrod's proof) in the same time,
1290:. But if every vertex in the arrangement were the crossing point of three or more lines, then the total number of edges would be at least
474:
of points is not all collinear. Define a connecting line to be a line that contains at least two points in the collection. By finiteness,
5751:
5150:
4433:
Basit, Abdul; Dvir, Zeev; Saraf, Shubhangi; Wolf, Charles (2019), "On the number of ordinary lines determined by sets in complex space",
211:
In a 1951 review, Erdős called the result "Gallai's theorem", but it was already called the Sylvester–Gallai theorem in a 1954 review by
3034:; these 13 points have among them 6 ordinary lines. Modifications of Böröczky's construction lead to sets of odd numbers of points with
184:) claimed to have a short proof of the Sylvester–Gallai theorem, but it was already noted to be incomplete at the time of publication.
3787:
collinear points together with one additional point that is not on the same line as the other points, shows that this bound is tight.
1446:
3944:
Every set of points in the Euclidean plane, and the lines connecting them, may be abstracted as the elements and flats of a rank-3
2655:
Example of Böröczky's (even) configuration with 10 points determining 5 ordinary lines (the five solid black lines of the figure).
4984:
3022:
in which these three ordinary lines are replaced by a single line cannot be realized in the Euclidean plane, but forms a finite
6075:
3823:, an equivalent statement is that the family of the collinear subsets of a finite point set (not all on one line) cannot have
4424:
3247:
case is an exception because otherwise the Kelly–Moser construction would be a counterexample; their construction shows that
5019:
4904:
4743:
4708:
4435:
3891:
The Sylvester–Gallai theorem also does not directly apply to geometries in which points have coordinates that are pairs of
1699:
of all triples of points, but an algorithm to find the closest given point to each line through two given points, in time
5284:
4484:(1983), "On the lattice property of the plane and some problems of Dirac, Motzkin, and Erdős in combinatorial geometry",
534:
that are a positive distance apart such that no other point-line pair has a smaller positive distance. Kelly proved that
5982:
3956:
lower-bounding the number of ordinary lines can be generalized to oriented matroids: every rank-3 oriented matroid with
3919:, the points must all lie on a single line, and the example of the Hesse configuration shows that this is false for the
1739:, as a subroutine for finding the minimum-area triangle determined by three of a given set of points. The same paper of
6028:
5972:
5814:
5726:
5575:
3912:
5942:
3803:
of points, to avoid examples like the set of all points in the Euclidean plane, which does not have an ordinary line.
3080:
2806:) on the line at infinity corresponding to each of the directions determined by pairs of vertices. Although there are
45:
has a line that passes through exactly two of the points or a line that passes through all of them. It is named after
6070:
4824:
4623:
4552:
1195:
5519:
5017:; Pretorius, Lou M.; Swanepoel, Konrad J. (2006), "Sylvester–Gallai theorems for complex numbers and quaternions",
4939:
3932:
is the whole space must have an ordinary line, and in fact must have a linear number of ordinary lines. Similarly,
2519:
1639:
6018:
5497:
Mukhopadhyay, A.; Agrawal, A.; Hosabettu, R. M. (1997), "On the ordinary line problem in computational geometry",
6049:
5339:
5158:
4543:, Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge: Cambridge University Press, p.
4812:
4773:
1608:
420:
2465:
5992:
5807:
5759:
5662:
5561:
5070:
4670:
412:
4011:. Relatedly, the Kelly–Moser configuration with seven points and only three ordinary lines forms one of the
3357:, stating a tradeoff between the number of lines with few points and the number of points on a single line.
6023:
3354:
3037:
3544:
3159:
3948:. The points and lines of geometries defined using other number systems than the real numbers also form
5390:
2598:
2955:
2682:
5194:
4648:
4632:
3360:
2387:
1783:
first showed how to find a single ordinary line (not necessarily the one from Kelly's proof) in time
3311:
2347:
5924:
4574:
4039:. In this generalization, a triple of points in a metric space is defined to be collinear when the
3920:
3908:
3904:
3900:
3852:
3537:
3019:
163:
159:
6080:
5957:
5605:
3876:
1961:
If any of the points is alone in its group, then return the ordinary line through that point and
192:) proved the theorem (and actually a slightly stronger result) in an equivalent formulation, its
4544:
4538:
3370:
3250:
1786:
1316:
1258:
1201:
87:
2161:
2134:
2105:
2078:
2051:
1877:
1643:
555:
362:
279:
255:
131:
46:
5967:
5763:
5183:
2809:
2401:
2291:
1746:
1702:
1662:
306:
6044:
5912:
3872:
1635:
1370:
5380:
Sylvester-Gallai results and other contributions to combinatorial and computational geometry
3899:, but these geometries have more complicated analogues of the theorem. For instance, in the
3482:
5977:
5947:
5887:
5865:
5789:
5637:
5598:
5542:
5510:
5490:
5421:
5362:
5307:
5272:
5232:
5179:
5131:
5050:
5007:
4975:
4968:
4948:
4934:
4927:
4874:
4864:
4835:
4805:
4766:
4731:
4699:
4661:
4595:
4562:
4507:
4466:
4406:
4120:
4106:
4016:
3476:
3403:
2509:
2220:
2188:
2021:
1994:
1964:
1934:
1904:
1839:
1396:
1130:
1080:
1044:
1024:
649:
564:
537:
517:
244:
227:
The question of the existence of an ordinary line can also be posed for points in the real
4534:
4402:
3979:
2780:
1355:
note, the same argument for the existence of an ordinary vertex was also given in 1944 by
966:
935:
8:
5987:
5952:
5932:
5830:
5556:(2009), "Chapter 1. Sylvester–Gallai Problem: The Beginnings of Combinatorial Geometry",
5441:
4738:
4040:
3848:
3764:
3737:
3671:
3581:
3430:
3285:
3224:
3196:
3023:
2659:
Dirac's conjectured lower bound is asymptotically the best possible, as the even numbers
2259:
1624:
907:
879:
167:
5251:
4952:
3578:
lower bound is still valid, though it is not known whether the Green and Tao asymptotic
1293:
834:
729:
604:
5962:
5882:
5679:
5641:
5625:
5478:
5425:
5399:
5366:
5320:
5314:
5279:
5236:
5210:
5135:
5087:
5054:
5028:
4979:
4852:
4793:
4687:
4599:
4526:
4511:
4470:
4444:
3959:
3717:
3697:
3647:
3627:
3519:
3458:
3139:
2952:, only two examples are known that match Dirac's lower bound conjecture, that is, with
2935:
2912:
2892:
2872:
2852:
2760:
2736:
2662:
2566:
2437:
2327:
1696:
1423:
1238:
1176:
1156:
1136:
1112:
1004:
859:
814:
794:
774:
754:
709:
689:
669:
629:
584:
497:
477:
457:
444:
416:
342:
286:
236:
212:
193:
147:
139:
67:
5247:
1779:, from which it is possible to identify all ordinary vertices and all ordinary lines.
5772:
5645:
5436:
5429:
5370:
4998:
4820:
4619:
4603:
4572:; Moser, W. O. J. (1990), "A survey of Sylvester's problem and its generalizations",
4548:
4474:
4420:
4008:
1864:
1832:
is based on Coxeter's proof using ordered geometry. It performs the following steps:
185:
5240:
4522:
4515:
1367:
By a similar argument, Melchior was able to prove a more general result. For every
5892:
5844:
5671:
5617:
5584:
5528:
5517:
Mukhopadhyay, Asish; Greene, Eugene (2012), "The ordinary line problem revisited",
5468:
5454:
5409:
5388:
Mandelkern, Mark (2016), "A constructive version of the Sylvester–Gallai theorem",
5348:
5293:
5220:
5167:
5139:
5119:
5079:
5058:
5038:
4993:
4956:
4913:
4844:
4785:
4752:
4717:
4679:
4668:
Chakerian, G. D. (1970), "Sylvester's problem on collinear points and a relative",
4583:
4495:
4454:
4412:
3945:
3864:
3828:
3816:
3031:
2754:
2455:
1620:
1041:
as the point-line pair with the smallest positive distance. So the assumption that
995:
424:
228:
151:
5776:
5690:
5657:
5633:
5594:
5538:
5533:
5506:
5486:
5417:
5358:
5303:
5268:
5228:
5175:
5127:
5046:
5003:
4964:
4923:
4860:
4801:
4762:
4727:
4695:
4657:
4591:
4558:
4530:
4503:
4462:
4416:
4117:
4103:
3860:
1356:
1074:
232:
42:
250:
5875:
5259:
5102:
3892:
3820:
435:
5589:
5413:
5378:
5224:
5042:
4833:
Crowe, D. W.; McKee, T. A. (1968), "Sylvester's problem on collinear points",
4757:
4722:
4481:
4458:
6064:
5722:
5706:
5110:
5103:"Personal reminiscences and remarks on the mathematical work of Tibor Gallai"
4569:
4486:
4398:
4012:
3812:
271:
173:
146:) suggests that Sylvester may have been motivated by a related phenomenon in
5558:
Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures
5549:
5098:
5065:
4960:
4636:
4611:
3621:
2391:
197:
5870:
5653:
5553:
5353:
5171:
4640:
4028:
3881:
3796:
3624:
observed, the Sylvester–Gallai theorem immediately implies that any set of
275:
205:
50:
266:
Arrangements of lines have a combinatorial structure closely connected to
5793:
5317:; Moser, W. O. J. (1958), "On the number of ordinary lines determined by
5198:
5014:
3929:
3916:
3868:
3364:
1868:
1593:{\displaystyle \displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.}
155:
3952:, but not necessarily oriented matroids. In this context, the result of
5937:
5902:
5849:
5799:
5683:
5629:
5482:
5298:
5282:(1986), "A resolution of the Sylvester–Gallai problem of J. P. Serre",
5146:
5123:
5091:
4918:
4856:
4797:
4691:
4587:
4499:
3896:
3885:
3824:
3800:
3027:
2651:
2244:, but this line should have already been found and returned in step 4.
2075:
in the set of lines formed in this way, find the intersection point of
267:
259:
38:
5457:(1951), "The lines and planes connecting the points of a finite set",
4405:(2018), "Chapter 11. Lines in the plane and decomposition of graphs",
3843:
5781:
5033:
2324:
be the minimum number of ordinary lines determined over every set of
2252:
61:
5675:
5621:
5473:
5083:
4848:
4789:
4683:
4027:
Another generalization of the Sylvester–Gallai theorem to arbitrary
1821:, and a simpler algorithm with the same time bound was described by
1634:
The usual statement of the Sylvester–Gallai theorem is not valid in
25:
Three of the ordinary lines in a 4 × 4 grid of points
5404:
4819:(2nd ed.), New York: John Wiley & Sons, pp. 181–182,
4449:
4054:
4044:
line that contains either all points or exactly two of the points.
56:
A line that contains exactly two of a set of points is known as an
34:
5215:
3949:
2733:, that achieves this bound consists of the vertices of a regular
53:, who published one of the first proofs of this theorem in 1944.
21:
5252:"Monochromatic intersection points in families of colored lines"
4521:
4361:
204:) again stated the conjecture, which was subsequently proved by
5731:
Mathematical Questions and Solutions from the Educational Times
5660:(1944), "Three point collinearity (solution to problem 4065)",
3888:, the set of all points in the geometry has no ordinary lines.
2909:
with the point at infinity collinear with the two neighbors of
1505:{\displaystyle \displaystyle \sum _{k\geq 2}(k-3)t_{k}\leq -3.}
1359:, who explicitly applied it to the dual ordinary line problem.
581:
is not ordinary. Then it goes through at least three points of
4343:
4239:
3884:: for some finite geometries defined in this way, such as the
3811:
A variation of Sylvester's problem, posed in the mid-1960s by
451:
call it "simply the best" of the many proofs of this theorem.
5651:
4221:
4185:
4087:
5496:
3799:. In general, these variations of the theorem consider only
3367:
showed that for all sufficiently large point sets (that is,
1780:
751:(and possibly coinciding with it). Draw the connecting line
4741:(2004), "Sylvester–Gallai theorem and metric betweenness",
4337:
For the history of this variation of the problem, see also
4148:
4146:
4144:
4142:
4140:
5068:(1943), "Problem 4065", Problems for solution: 4065–4069,
4184:, p. 92); Steenrod's proof was briefly summarized in
4071:
4069:
5013:
4815:(1969), "12.3 Sylvester's problem of collinear points",
4137:
4060:
3933:
1931:
Sort the other given points by the angle they make with
5608:(1968), "Twenty problems on convex polyhedra, part I",
4706:
Chen, Xiaomin (2006), "The Sylvester–Chvátal theorem",
4066:
303:
points in the plane can be guaranteed to have at least
130:
The Sylvester–Gallai theorem was posed as a problem by
5770:
5560:, Mathematical Surveys and Monographs, vol. 152,
5151:"The excluded minors for GF(4)-representable matroids"
4227:
4165:
4163:
4161:
3831:
but never published; the first published proof was by
1255:
from the Euler characteristic leads to the inequality
5323:
4937:(1951), "Collinearity properties of sets of points",
4877:
3982:
3962:
3767:
3740:
3720:
3700:
3674:
3650:
3630:
3584:
3547:
3522:
3485:
3461:
3433:
3406:
3373:
3314:
3288:
3253:
3227:
3199:
3162:
3142:
3083:
3040:
2958:
2938:
2915:
2895:
2875:
2855:
2812:
2783:
2763:
2739:
2685:
2665:
2601:
2569:
2522:
2468:
2440:
2404:
2350:
2330:
2294:
2262:
2256:
The two known examples of point sets with fewer than
2223:
2191:
2164:
2137:
2108:
2081:
2054:
2024:
1997:
1967:
1937:
1907:
1880:
1842:
1789:
1749:
1705:
1665:
1525:
1524:
1450:
1449:
1426:
1399:
1373:
1319:
1296:
1261:
1241:
1204:
1179:
1159:
1139:
1115:
1083:
1047:
1027:
1007:
1001:
However, this contradicts the original definition of
969:
938:
910:
882:
862:
837:
817:
797:
777:
757:
732:
712:
692:
672:
652:
632:
607:
587:
567:
540:
520:
500:
480:
460:
365:
345:
309:
289:
90:
70:
5571:"A reverse analysis of the Sylvester–Gallai theorem"
4319:
4307:
1958:, grouping together points that form the same angle.
5145:
4275:
4158:
4125:
3427:), the number of ordinary lines is indeed at least
2344:non-collinear points. Melchior's proof showed that
5749:
5516:
5329:
4974:
4894:
4432:
4349:
4245:
3999:
3968:
3779:
3752:
3726:
3706:
3686:
3656:
3644:points that are not collinear determines at least
3636:
3598:
3570:
3528:
3508:
3467:
3447:
3419:
3392:
3342:
3300:
3274:
3239:
3213:
3185:
3156:is seven. Asymptotically, this formula is already
3148:
3128:
3063:
3006:
2944:
2921:
2901:
2881:
2861:
2841:
2798:
2769:
2745:
2721:
2671:
2640:
2575:
2555:
2500:
2446:
2426:
2378:
2336:
2316:
2276:
2236:
2204:
2177:
2150:
2121:
2094:
2067:
2037:
2010:
1980:
1950:
1920:
1893:
1855:
1829:
1822:
1813:
1771:
1740:
1736:
1727:
1687:
1656:
1592:
1504:
1432:
1412:
1385:
1340:
1305:
1282:
1247:
1227:
1185:
1165:
1145:
1121:
1101:
1053:
1033:
1013:
986:
955:
924:
896:
868:
848:
823:
803:
783:
763:
743:
718:
698:
678:
658:
638:
618:
593:
573:
546:
526:
506:
486:
466:
390:
351:
331:
295:
114:
76:
5709:(1893a), "Mathematical question 11851 answered",
5460:Transactions of the American Mathematical Society
4982:(1989), "Topologically sweeping an arrangement",
3668:. As a base case, the result is clearly true for
3609:
3282:. However, were the Csima–Sawyer bound valid for
6062:
4411:(6th ed.), Springer, Theorem 1, pp. 77–78,
4295:
3129:{\displaystyle t_{2}(n)\geq \lceil 6n/13\rceil }
2889:ordinary lines, the lines that connect a vertex
1659:report the time for this closest-pair search as
601:. At least two of these are on the same side of
5520:Computational Geometry: Theory and Applications
5439:(1941), "Über Vielseite der Projektive Ebene",
5201:(2013), "On sets defining few ordinary lines",
2869:distinct directions. This arrangement has only
2247:
1928:and otherwise stays outside of the convex hull.
4631:
4609:
2679:greater than four have a matching upper bound
2588:
2395:
359:generators can be guaranteed to have at least
5815:
4397:
4197:
4181:
4152:
3827:. A proof of this variation was announced by
3664:different lines. This result is known as the
2556:{\displaystyle t_{2}\geq \lfloor n/2\rfloor }
1352:
448:
4568:
4075:
3616:De Bruijn–Erdős theorem (incidence geometry)
3565:
3548:
3123:
3106:
3058:
3044:
2550:
2536:
1781:Mukhopadhyay, Agrawal & Hosabettu (1997)
408:
4871:Csima, J.; Sawyer, E. (1993), "There exist
4870:
3479:, the number of ordinary lines is at least
3074:
2849:pairs of these points, they determine only
1650:
5822:
5808:
5568:
5548:
5387:
5313:
4832:
4381:
4290:
4260:
4233:
4217:
4201:
3953:
3015:
2592:
1628:
1077:in the real projective plane, the formula
5689:
5588:
5532:
5472:
5403:
5352:
5297:
5214:
5032:
4997:
4917:
4776:(1948), "A problem of collinear points",
4756:
4721:
4667:
4448:
3832:
2462:) confirmed that it does by proving that
2018:in one group and the farthest point from
217:mathematical topics named after Sylvester
135:
49:, who posed it as a problem in 1893, and
5829:
5721:
5705:
5604:
5435:
5376:
5246:
5193:
5149:; Gerards, A. M. H.; Kapoor, A. (2000),
4338:
4325:
4313:
4271:
4269:
4169:
4131:
4061:Elkies, Pretorius & Swanepoel (2006)
3934:Elkies, Pretorius & Swanepoel (2006)
3842:
2650:
2501:{\displaystyle t_{2}(n)\geq {\sqrt {n}}}
2251:
1362:
434:
249:
208:, and soon afterwards by other authors.
189:
181:
177:
20:
5693:(1893), "Mathematical question 11851",
5453:
4985:Journal of Computer and System Sciences
4811:
4772:
4737:
4641:"A combinatioral [sic] problem"
4373:
4286:
4284:
4256:
4254:
4213:
4032:
3838:
2459:
1640:lesser limited principle of omniscience
1616:
1612:
6063:
5727:"Mathematical question 11851 answered"
4616:Research problems in discrete geometry
4081:
1073:Melchior observed that, for any graph
222:
64:can find an ordinary line in a set of
16:Existence of a line through two points
5803:
5771:
5278:
5203:Discrete & Computational Geometry
5097:
5064:
5020:Discrete & Computational Geometry
4933:
4905:Discrete & Computational Geometry
4744:Discrete & Computational Geometry
4709:Discrete & Computational Geometry
4436:Discrete & Computational Geometry
4266:
4091:
3924:
3871:for the coordinates of their points (
2513:
1235:. Using this inequality to eliminate
1061:is not ordinary cannot be true, QED.
201:
166:of nine points and twelve lines (the
143:
4705:
4480:
4377:
4301:
4281:
4251:
4036:
4022:
3064:{\displaystyle 3\lfloor n/4\rfloor }
2583:. This is often referred to as the
5285:Discrete and Computational Geometry
4276:Geelen, Gerards & Kapoor (2000)
3571:{\displaystyle \lceil 6n/13\rceil }
3186:{\displaystyle 12/13\approx 92.3\%}
2217:line between one of its points and
1070:has at least three ordinary lines.
1064:
13:
5576:Notre Dame Journal of Formal Logic
3790:
3180:
998:, one contained inside the other.
932:. This follows from the fact that
626:, the perpendicular projection of
14:
6092:
5743:
3806:
3714:, the result can be reduced from
2641:{\displaystyle t_{2}(n)\geq 3n/7}
2398:) raised the question of whether
1420:be the number of points to which
4940:Quarterly Journal of Mathematics
4246:Mukhopadhyay & Greene (2012)
3007:{\displaystyle t_{2}(n)=(n-1)/2}
2722:{\displaystyle t_{2}(n)\leq n/2}
1830:Mukhopadhyay & Greene (2012)
1823:Mukhopadhyay & Greene (2012)
1741:Edelsbrunner & Guibas (1989)
1737:Edelsbrunner & Guibas (1989)
1657:Mukhopadhyay & Greene (2012)
1198:gives the additional inequality
430:
196:. Unaware of Melchior's proof,
5340:Canadian Journal of Mathematics
5159:Journal of Combinatorial Theory
4367:
4355:
4331:
4207:
4191:
339:ordinary lines, zonohedra with
5973:Cremona–Richmond configuration
4610:Brass, Peter; Moser, William;
4175:
4111:
4097:
3913:Sylvester–Gallai configuration
3610:The number of connecting lines
3343:{\displaystyle t_{2}(7)\geq 4}
3331:
3325:
3263:
3257:
3100:
3094:
2993:
2981:
2975:
2969:
2828:
2816:
2702:
2696:
2618:
2612:
2485:
2479:
2421:
2415:
2379:{\displaystyle t_{2}(n)\geq 3}
2367:
2361:
2311:
2305:
2158:whose intersection point with
1808:
1793:
1766:
1753:
1722:
1709:
1682:
1669:
1631:for a study of this question.
1573:
1561:
1479:
1467:
1133:of the projective plane. Here
385:
379:
326:
320:
109:
94:
1:
6076:Theorems in discrete geometry
5760:American Mathematical Society
5663:American Mathematical Monthly
5562:American Mathematical Society
5071:American Mathematical Monthly
4778:American Mathematical Monthly
4671:American Mathematical Monthly
4390:
2589:Brass, Moser & Pach (2005
1603:
811:, and the perpendicular from
6050:Kirkman's schoolgirl problem
5983:Grünbaum–Rigby configuration
5796:at the 2013 Minerva Lectures
5752:"A discrete geometrical gem"
5652:Steinberg, R.; Buck, R. C.;
5534:10.1016/j.comgeo.2011.10.003
4999:10.1016/0022-0000(89)90038-X
4417:10.1007/978-3-662-57265-8_11
4220:. For Steinberg's proof see
4017:GF(4)-representable matroids
3875:for the Euclidean plane and
3400:for some suitable choice of
3353:A closely related result is
2248:The number of ordinary lines
7:
5943:Möbius–Kantor configuration
5750:Malkevitch, Joseph (2003),
5569:Pambuccian, Victor (2009),
5499:Nordic Journal of Computing
5377:Lenchner, Jonathan (2008).
4198:Aigner & Ziegler (2018)
4153:Aigner & Ziegler (2018)
3939:
2729:. The construction, due to
1353:Aigner & Ziegler (2018)
449:Aigner & Ziegler (2018)
10:
6097:
6029:Bruck–Ryser–Chowla theorem
5391:Acta Mathematica Hungarica
4182:Aigner & Ziegler (2018
4076:Borwein & Moser (1990)
3694:. For any larger value of
3613:
3393:{\displaystyle n>n_{0}}
3275:{\displaystyle t(7)\leq 3}
1814:{\displaystyle O(n\log n)}
1341:{\displaystyle E\leq 3V-3}
1283:{\displaystyle E\leq 3V-3}
1228:{\displaystyle F\leq 2E/3}
454:Suppose that a finite set
439:Notation for Kelly's proof
413:Euler's polyhedral formula
409:Borwein & Moser (1990)
270:, polyhedra formed as the
125:
115:{\displaystyle O(n\log n)}
6037:
6019:Szemerédi–Trotter theorem
6001:
5923:
5858:
5837:
5590:10.1215/00294527-2009-010
5414:10.1007/s10474-016-0624-z
5225:10.1007/s00454-013-9518-9
5043:10.1007/s00454-005-1226-7
4758:10.1007/s00454-003-0795-6
4723:10.1007/s00454-005-1216-9
4649:Indagationes Mathematicae
4459:10.1007/s00454-018-0039-4
3075:Csima & Sawyer (1993)
2434:approaches infinity with
2178:{\displaystyle \ell _{0}}
2151:{\displaystyle \ell _{i}}
2122:{\displaystyle \ell _{0}}
2095:{\displaystyle \ell _{i}}
2068:{\displaystyle \ell _{i}}
1894:{\displaystyle \ell _{0}}
1642:, a weakened form of the
1440:lines are incident. Then
401:
391:{\displaystyle 2t_{2}(n)}
6071:Euclidean plane geometry
6009:Sylvester–Gallai theorem
5610:The Mathematical Gazette
4817:Introduction to Geometry
4575:Aequationes Mathematicae
4291:Pach & Sharir (2009)
4261:Crowe & McKee (1968)
4047:
3954:Kelly & Moser (1958)
3921:complex projective plane
3901:complex projective plane
3867:can be defined by using
3853:complex projective plane
3538:orchard-planting problem
3016:Kelly & Moser (1958)
2842:{\displaystyle m(m-1)/2}
2593:Kelly & Moser (1958)
2585:Dirac–Motzkin conjecture
2427:{\displaystyle t_{2}(n)}
2317:{\displaystyle t_{2}(n)}
1772:{\displaystyle O(n^{2})}
1728:{\displaystyle O(n^{2})}
1688:{\displaystyle O(n^{3})}
1651:Finding an ordinary line
332:{\displaystyle t_{2}(n)}
160:complex projective plane
31:Sylvester–Gallai theorem
6014:De Bruijn–Erdős theorem
5958:Desargues configuration
4222:Steinberg et al. (1944)
4186:Steinberg et al. (1944)
4088:Steinberg et al. (1944)
3877:homogeneous coordinates
3666:De Bruijn–Erdős theorem
1735:, was given earlier by
1386:{\displaystyle k\geq 2}
5354:10.4153/CJM-1958-024-6
5331:
5172:10.1006/jctb.2000.1963
4896:
4314:Green & Tao (2013)
4001:
3976:elements has at least
3970:
3856:
3781:
3754:
3728:
3708:
3688:
3658:
3638:
3600:
3572:
3530:
3510:
3509:{\displaystyle 3n/4-C}
3469:
3449:
3421:
3394:
3344:
3308:, it would claim that
3302:
3276:
3241:
3215:
3187:
3150:
3130:
3065:
3008:
2946:
2923:
2903:
2883:
2863:
2843:
2800:
2771:
2747:
2723:
2673:
2656:
2642:
2577:
2557:
2502:
2448:
2428:
2380:
2338:
2318:
2285:
2278:
2238:
2206:
2179:
2152:
2123:
2096:
2069:
2039:
2012:
1982:
1952:
1922:
1895:
1857:
1815:
1773:
1729:
1689:
1644:law of excluded middle
1594:
1506:
1434:
1414:
1387:
1342:
1307:
1284:
1249:
1229:
1187:
1167:
1147:
1123:
1103:
1055:
1035:
1015:
988:
957:
926:
898:
870:
850:
825:
805:
785:
765:
745:
720:
700:
680:
660:
640:
620:
595:
575:
548:
528:
514:and a connecting line
508:
488:
468:
440:
392:
353:
333:
297:
280:elongated dodecahedron
263:
256:elongated dodecahedron
116:
78:
47:James Joseph Sylvester
26:
6045:Design of experiments
5711:The Educational Times
5695:The Educational Times
5332:
4976:Edelsbrunner, Herbert
4961:10.1093/qmath/2.1.221
4897:
4895:{\displaystyle 6n/13}
4362:Björner et al. (1993)
4002:
3971:
3909:Hesse's configuration
3873:Cartesian coordinates
3846:
3782:
3755:
3729:
3709:
3689:
3659:
3639:
3601:
3573:
3531:
3511:
3470:
3450:
3422:
3420:{\displaystyle n_{0}}
3395:
3345:
3303:
3277:
3242:
3216:
3188:
3151:
3131:
3066:
3009:
2947:
2924:
2904:
2884:
2864:
2844:
2801:
2772:
2748:
2724:
2674:
2654:
2643:
2578:
2558:
2503:
2449:
2429:
2381:
2339:
2319:
2279:
2255:
2239:
2237:{\displaystyle p_{0}}
2207:
2205:{\displaystyle p_{0}}
2180:
2153:
2124:
2097:
2070:
2040:
2038:{\displaystyle p_{0}}
2013:
2011:{\displaystyle p_{0}}
1983:
1981:{\displaystyle p_{0}}
1953:
1951:{\displaystyle p_{0}}
1923:
1921:{\displaystyle p_{0}}
1896:
1858:
1856:{\displaystyle p_{0}}
1816:
1774:
1730:
1690:
1636:constructive analysis
1595:
1507:
1435:
1415:
1413:{\displaystyle t_{k}}
1388:
1363:Melchior's inequality
1343:
1308:
1285:
1250:
1230:
1188:
1168:
1148:
1124:
1104:
1102:{\displaystyle V-E+F}
1056:
1054:{\displaystyle \ell }
1036:
1034:{\displaystyle \ell }
1016:
989:
958:
927:
899:
871:
851:
826:
806:
786:
766:
746:
721:
701:
681:
661:
659:{\displaystyle \ell }
641:
621:
596:
576:
574:{\displaystyle \ell }
549:
547:{\displaystyle \ell }
529:
527:{\displaystyle \ell }
509:
489:
469:
438:
398:parallelogram faces.
393:
354:
334:
298:
253:
186:Eberhard Melchior
117:
79:
24:
5978:Kummer configuration
5948:Pappus configuration
5831:Incidence structures
5321:
4875:
4836:Mathematics Magazine
4618:, Berlin: Springer,
4408:Proofs from THE BOOK
4000:{\displaystyle 3n/7}
3980:
3960:
3839:Non-real coordinates
3765:
3738:
3718:
3698:
3672:
3648:
3628:
3582:
3545:
3520:
3516:, for some constant
3483:
3459:
3455:. Furthermore, when
3431:
3404:
3371:
3312:
3286:
3251:
3225:
3197:
3160:
3140:
3081:
3038:
2956:
2936:
2913:
2893:
2873:
2853:
2810:
2799:{\displaystyle n=2m}
2781:
2761:
2737:
2683:
2663:
2599:
2567:
2563:, for all values of
2520:
2466:
2456:Theodore Motzkin
2438:
2402:
2348:
2328:
2292:
2260:
2221:
2189:
2162:
2135:
2106:
2079:
2052:
2022:
1995:
1965:
1935:
1905:
1901:that passes through
1878:
1871:of the given points.
1840:
1787:
1747:
1703:
1663:
1638:, as it implies the
1609:H. S. M. Coxeter
1522:
1447:
1424:
1397:
1371:
1317:
1294:
1259:
1239:
1202:
1177:
1157:
1137:
1131:Euler characteristic
1113:
1081:
1045:
1025:
1005:
987:{\displaystyle BB'C}
967:
956:{\displaystyle PP'C}
936:
908:
880:
860:
835:
815:
795:
775:
755:
730:
710:
690:
670:
650:
630:
605:
585:
565:
538:
518:
498:
478:
458:
363:
343:
307:
287:
215:. It is one of many
88:
68:
5988:Klein configuration
5968:Schläfli double six
5953:Hesse configuration
5933:Complete quadrangle
5442:Deutsche Mathematik
4980:Guibas, Leonidas J.
4953:1951QJMat...2..221D
4527:Las Vergnas, Michel
4350:Basit et al. (2019)
4041:triangle inequality
4031:was conjectured by
3849:Hesse configuration
3815:and popularized by
3780:{\displaystyle n-1}
3753:{\displaystyle n-1}
3687:{\displaystyle n=3}
3606:bound still holds.
3599:{\displaystyle n/2}
3448:{\displaystyle n/2}
3301:{\displaystyle n=7}
3240:{\displaystyle n=7}
3214:{\displaystyle n/2}
2516:) conjectured that
2277:{\displaystyle n/2}
2045:in the other group.
1625:reverse mathematics
925:{\displaystyle PP'}
897:{\displaystyle BB'}
415:. Another proof by
274:of a finite set of
223:Equivalent versions
168:Hesse configuration
132:J. J. Sylvester
5963:Reye configuration
5790:Proof presentation
5773:Weisstein, Eric W.
5756:AMS Feature Column
5327:
5299:10.1007/BF02187687
5124:10.1007/BF02579228
4919:10.1007/BF02189318
4902:ordinary points",
4892:
4588:10.1007/BF02112289
4535:Ziegler, Günter M.
4500:10.1007/BF02579184
4403:Ziegler, Günter M.
3997:
3966:
3857:
3777:
3750:
3724:
3704:
3684:
3654:
3634:
3596:
3568:
3526:
3506:
3465:
3445:
3417:
3390:
3340:
3298:
3272:
3237:
3211:
3183:
3146:
3126:
3061:
3004:
2942:
2919:
2899:
2879:
2859:
2839:
2796:
2767:
2743:
2719:
2669:
2657:
2638:
2587:; see for example
2573:
2553:
2498:
2444:
2424:
2376:
2334:
2314:
2286:
2274:
2234:
2202:
2185:is the closest to
2175:
2148:
2119:
2092:
2065:
2035:
2008:
1978:
1948:
1918:
1891:
1853:
1811:
1769:
1725:
1697:brute-force search
1685:
1590:
1589:
1560:
1502:
1501:
1466:
1430:
1410:
1383:
1338:
1306:{\displaystyle 3V}
1303:
1280:
1245:
1225:
1183:
1163:
1143:
1119:
1099:
1051:
1031:
1011:
984:
953:
922:
894:
866:
849:{\displaystyle B'}
846:
821:
801:
781:
761:
744:{\displaystyle P'}
741:
716:
696:
676:
656:
636:
619:{\displaystyle P'}
616:
591:
571:
544:
524:
504:
494:must have a point
484:
464:
445:Leroy Milton Kelly
441:
417:Leroy Milton Kelly
388:
349:
329:
293:
264:
237:projective duality
231:RP instead of the
213:Leonard Blumenthal
148:algebraic geometry
112:
74:
37:states that every
27:
6058:
6057:
5330:{\displaystyle n}
4813:Coxeter, H. S. M.
4774:Coxeter, H. S. M.
4540:Oriented matroids
4426:978-3-662-57265-8
4382:Pambuccian (2009)
4234:Mandelkern (2016)
4218:Pambuccian (2009)
4202:Pambuccian (2009)
4023:Distance geometry
4009:Sylvester matroid
3969:{\displaystyle n}
3727:{\displaystyle n}
3707:{\displaystyle n}
3657:{\displaystyle n}
3637:{\displaystyle n}
3529:{\displaystyle C}
3468:{\displaystyle n}
3221:upper bound. The
3149:{\displaystyle n}
2945:{\displaystyle n}
2922:{\displaystyle v}
2902:{\displaystyle v}
2882:{\displaystyle m}
2862:{\displaystyle m}
2770:{\displaystyle m}
2753:-gon in the real
2746:{\displaystyle m}
2672:{\displaystyle n}
2576:{\displaystyle n}
2510:Gabriel Dirac
2496:
2447:{\displaystyle n}
2337:{\displaystyle n}
1874:Construct a line
1828:The algorithm of
1629:Pambuccian (2009)
1545:
1515:or equivalently,
1451:
1433:{\displaystyle k}
1248:{\displaystyle F}
1186:{\displaystyle F}
1166:{\displaystyle E}
1146:{\displaystyle V}
1122:{\displaystyle 1}
1014:{\displaystyle P}
996:similar triangles
869:{\displaystyle m}
824:{\displaystyle B}
804:{\displaystyle C}
784:{\displaystyle P}
764:{\displaystyle m}
726:being closest to
719:{\displaystyle B}
699:{\displaystyle C}
679:{\displaystyle B}
639:{\displaystyle P}
594:{\displaystyle S}
507:{\displaystyle P}
487:{\displaystyle S}
467:{\displaystyle S}
443:This proof is by
352:{\displaystyle n}
296:{\displaystyle n}
174:H. J. Woodall
152:inflection points
77:{\displaystyle n}
41:of points in the
6088:
5893:Projective plane
5845:Incidence matrix
5824:
5817:
5810:
5801:
5800:
5786:
5785:
5767:
5762:, archived from
5738:
5718:
5702:
5691:Sylvester, J. J.
5686:
5648:
5616:(380): 136–156,
5601:
5592:
5565:
5545:
5536:
5513:
5493:
5476:
5450:
5432:
5407:
5384:
5373:
5356:
5336:
5334:
5333:
5328:
5310:
5301:
5275:
5256:
5248:Grünbaum, Branko
5243:
5218:
5190:
5188:
5182:, archived from
5155:
5142:
5107:
5094:
5061:
5036:
5010:
5001:
4971:
4930:
4921:
4901:
4899:
4898:
4893:
4888:
4867:
4829:
4808:
4769:
4760:
4734:
4725:
4702:
4664:
4645:
4633:de Bruijn, N. G.
4628:
4606:
4565:
4531:Sturmfels, Bernd
4518:
4494:(3–4): 281–297,
4477:
4452:
4429:
4384:
4371:
4365:
4359:
4353:
4347:
4341:
4335:
4329:
4323:
4317:
4311:
4305:
4299:
4293:
4288:
4279:
4273:
4264:
4258:
4249:
4243:
4237:
4231:
4225:
4211:
4205:
4195:
4189:
4179:
4173:
4167:
4156:
4150:
4135:
4129:
4123:
4115:
4109:
4101:
4095:
4085:
4079:
4073:
4064:
4058:
4013:forbidden minors
4006:
4004:
4003:
3998:
3993:
3975:
3973:
3972:
3967:
3946:oriented matroid
3907:of nine points,
3865:projective plane
3833:Chakerian (1970)
3829:Theodore Motzkin
3821:families of sets
3817:Donald J. Newman
3786:
3784:
3783:
3778:
3759:
3757:
3756:
3751:
3733:
3731:
3730:
3725:
3713:
3711:
3710:
3705:
3693:
3691:
3690:
3685:
3663:
3661:
3660:
3655:
3643:
3641:
3640:
3635:
3605:
3603:
3602:
3597:
3592:
3577:
3575:
3574:
3569:
3561:
3535:
3533:
3532:
3527:
3515:
3513:
3512:
3507:
3496:
3474:
3472:
3471:
3466:
3454:
3452:
3451:
3446:
3441:
3426:
3424:
3423:
3418:
3416:
3415:
3399:
3397:
3396:
3391:
3389:
3388:
3349:
3347:
3346:
3341:
3324:
3323:
3307:
3305:
3304:
3299:
3281:
3279:
3278:
3273:
3246:
3244:
3243:
3238:
3220:
3218:
3217:
3212:
3207:
3192:
3190:
3189:
3184:
3170:
3155:
3153:
3152:
3147:
3135:
3133:
3132:
3127:
3119:
3093:
3092:
3071:ordinary lines.
3070:
3068:
3067:
3062:
3054:
3032:projective plane
3024:projective space
3014:One example, by
3013:
3011:
3010:
3005:
3000:
2968:
2967:
2951:
2949:
2948:
2943:
2928:
2926:
2925:
2920:
2908:
2906:
2905:
2900:
2888:
2886:
2885:
2880:
2868:
2866:
2865:
2860:
2848:
2846:
2845:
2840:
2835:
2805:
2803:
2802:
2797:
2776:
2774:
2773:
2768:
2755:projective plane
2752:
2750:
2749:
2744:
2728:
2726:
2725:
2720:
2715:
2695:
2694:
2678:
2676:
2675:
2670:
2647:
2645:
2644:
2639:
2634:
2611:
2610:
2591:, p. 304).
2582:
2580:
2579:
2574:
2562:
2560:
2559:
2554:
2546:
2532:
2531:
2507:
2505:
2504:
2499:
2497:
2492:
2478:
2477:
2453:
2451:
2450:
2445:
2433:
2431:
2430:
2425:
2414:
2413:
2385:
2383:
2382:
2377:
2360:
2359:
2343:
2341:
2340:
2335:
2323:
2321:
2320:
2315:
2304:
2303:
2283:
2281:
2280:
2275:
2270:
2243:
2241:
2240:
2235:
2233:
2232:
2211:
2209:
2208:
2203:
2201:
2200:
2184:
2182:
2181:
2176:
2174:
2173:
2157:
2155:
2154:
2149:
2147:
2146:
2131:Return the line
2128:
2126:
2125:
2120:
2118:
2117:
2101:
2099:
2098:
2093:
2091:
2090:
2074:
2072:
2071:
2066:
2064:
2063:
2044:
2042:
2041:
2036:
2034:
2033:
2017:
2015:
2014:
2009:
2007:
2006:
1987:
1985:
1984:
1979:
1977:
1976:
1957:
1955:
1954:
1949:
1947:
1946:
1927:
1925:
1924:
1919:
1917:
1916:
1900:
1898:
1897:
1892:
1890:
1889:
1862:
1860:
1859:
1854:
1852:
1851:
1820:
1818:
1817:
1812:
1778:
1776:
1775:
1770:
1765:
1764:
1734:
1732:
1731:
1726:
1721:
1720:
1694:
1692:
1691:
1686:
1681:
1680:
1621:ordered geometry
1599:
1597:
1596:
1591:
1585:
1584:
1559:
1535:
1534:
1511:
1509:
1508:
1503:
1491:
1490:
1465:
1439:
1437:
1436:
1431:
1419:
1417:
1416:
1411:
1409:
1408:
1392:
1390:
1389:
1384:
1347:
1345:
1344:
1339:
1312:
1310:
1309:
1304:
1289:
1287:
1286:
1281:
1254:
1252:
1251:
1246:
1234:
1232:
1231:
1226:
1221:
1192:
1190:
1189:
1184:
1172:
1170:
1169:
1164:
1152:
1150:
1149:
1144:
1128:
1126:
1125:
1120:
1108:
1106:
1105:
1100:
1065:Melchior's proof
1060:
1058:
1057:
1052:
1040:
1038:
1037:
1032:
1020:
1018:
1017:
1012:
993:
991:
990:
985:
980:
962:
960:
959:
954:
949:
931:
929:
928:
923:
921:
904:is shorter than
903:
901:
900:
895:
893:
875:
873:
872:
867:
855:
853:
852:
847:
845:
830:
828:
827:
822:
810:
808:
807:
802:
790:
788:
787:
782:
771:passing through
770:
768:
767:
762:
750:
748:
747:
742:
740:
725:
723:
722:
717:
705:
703:
702:
697:
685:
683:
682:
677:
665:
663:
662:
657:
645:
643:
642:
637:
625:
623:
622:
617:
615:
600:
598:
597:
592:
580:
578:
577:
572:
556:by contradiction
553:
551:
550:
545:
533:
531:
530:
525:
513:
511:
510:
505:
493:
491:
490:
485:
473:
471:
470:
465:
425:ordered geometry
421:H. S. M. Coxeter
397:
395:
394:
389:
378:
377:
358:
356:
355:
350:
338:
336:
335:
330:
319:
318:
302:
300:
299:
294:
243:in a nontrivial
229:projective plane
121:
119:
118:
113:
83:
81:
80:
75:
6096:
6095:
6091:
6090:
6089:
6087:
6086:
6085:
6061:
6060:
6059:
6054:
6033:
5997:
5919:
5854:
5850:Incidence graph
5833:
5828:
5777:"Ordinary Line"
5746:
5741:
5676:10.2307/2303021
5658:Steenrod, N. E.
5622:10.2307/3612678
5606:Shephard, G. C.
5564:, pp. 1–12
5474:10.2307/1990609
5383:(Ph.D. Thesis).
5322:
5319:
5318:
5254:
5186:
5153:
5105:
5084:10.2307/2304011
4884:
4876:
4873:
4872:
4849:10.2307/2687957
4827:
4790:10.2307/2305324
4684:10.2307/2317330
4643:
4626:
4555:
4533:; White, Neil;
4523:Björner, Anders
4427:
4393:
4388:
4387:
4372:
4368:
4360:
4356:
4348:
4344:
4339:Grünbaum (1999)
4336:
4332:
4326:Lenchner (2008)
4324:
4320:
4312:
4308:
4300:
4296:
4289:
4282:
4274:
4267:
4259:
4252:
4244:
4240:
4232:
4228:
4212:
4208:
4196:
4192:
4180:
4176:
4170:Melchior (1941)
4168:
4159:
4151:
4138:
4132:Shephard (1968)
4130:
4126:
4116:
4112:
4102:
4098:
4086:
4082:
4074:
4067:
4059:
4055:
4050:
4025:
3989:
3981:
3978:
3977:
3961:
3958:
3957:
3942:
3903:there exists a
3893:complex numbers
3861:Euclidean plane
3841:
3809:
3793:
3791:Generalizations
3766:
3763:
3762:
3739:
3736:
3735:
3719:
3716:
3715:
3699:
3696:
3695:
3673:
3670:
3669:
3649:
3646:
3645:
3629:
3626:
3625:
3618:
3612:
3588:
3583:
3580:
3579:
3557:
3546:
3543:
3542:
3521:
3518:
3517:
3492:
3484:
3481:
3480:
3460:
3457:
3456:
3437:
3432:
3429:
3428:
3411:
3407:
3405:
3402:
3401:
3384:
3380:
3372:
3369:
3368:
3319:
3315:
3313:
3310:
3309:
3287:
3284:
3283:
3252:
3249:
3248:
3226:
3223:
3222:
3203:
3198:
3195:
3194:
3166:
3161:
3158:
3157:
3141:
3138:
3137:
3115:
3088:
3084:
3082:
3079:
3078:
3050:
3039:
3036:
3035:
2996:
2963:
2959:
2957:
2954:
2953:
2937:
2934:
2933:
2914:
2911:
2910:
2894:
2891:
2890:
2874:
2871:
2870:
2854:
2851:
2850:
2831:
2811:
2808:
2807:
2782:
2779:
2778:
2762:
2759:
2758:
2738:
2735:
2734:
2731:Károly Böröczky
2711:
2690:
2686:
2684:
2681:
2680:
2664:
2661:
2660:
2630:
2606:
2602:
2600:
2597:
2596:
2568:
2565:
2564:
2542:
2527:
2523:
2521:
2518:
2517:
2491:
2473:
2469:
2467:
2464:
2463:
2439:
2436:
2435:
2409:
2405:
2403:
2400:
2399:
2355:
2351:
2349:
2346:
2345:
2329:
2326:
2325:
2299:
2295:
2293:
2290:
2289:
2284:ordinary lines.
2266:
2261:
2258:
2257:
2250:
2228:
2224:
2222:
2219:
2218:
2196:
2192:
2190:
2187:
2186:
2169:
2165:
2163:
2160:
2159:
2142:
2138:
2136:
2133:
2132:
2113:
2109:
2107:
2104:
2103:
2086:
2082:
2080:
2077:
2076:
2059:
2055:
2053:
2050:
2049:
2029:
2025:
2023:
2020:
2019:
2002:
1998:
1996:
1993:
1992:
1972:
1968:
1966:
1963:
1962:
1942:
1938:
1936:
1933:
1932:
1912:
1908:
1906:
1903:
1902:
1885:
1881:
1879:
1876:
1875:
1847:
1843:
1841:
1838:
1837:
1836:Choose a point
1788:
1785:
1784:
1760:
1756:
1748:
1745:
1744:
1716:
1712:
1704:
1701:
1700:
1676:
1672:
1664:
1661:
1660:
1653:
1606:
1580:
1576:
1549:
1530:
1526:
1523:
1520:
1519:
1486:
1482:
1455:
1448:
1445:
1444:
1425:
1422:
1421:
1404:
1400:
1398:
1395:
1394:
1372:
1369:
1368:
1365:
1357:Norman Steenrod
1318:
1315:
1314:
1295:
1292:
1291:
1260:
1257:
1256:
1240:
1237:
1236:
1217:
1203:
1200:
1199:
1196:double counting
1178:
1175:
1174:
1158:
1155:
1154:
1138:
1135:
1134:
1114:
1111:
1110:
1082:
1079:
1078:
1067:
1046:
1043:
1042:
1026:
1023:
1022:
1006:
1003:
1002:
973:
968:
965:
964:
942:
937:
934:
933:
914:
909:
906:
905:
886:
881:
878:
877:
861:
858:
857:
838:
836:
833:
832:
816:
813:
812:
796:
793:
792:
776:
773:
772:
756:
753:
752:
733:
731:
728:
727:
711:
708:
707:
691:
688:
687:
671:
668:
667:
651:
648:
647:
631:
628:
627:
608:
606:
603:
602:
586:
583:
582:
566:
563:
562:
539:
536:
535:
519:
516:
515:
499:
496:
495:
479:
476:
475:
459:
456:
455:
433:
404:
373:
369:
364:
361:
360:
344:
341:
340:
314:
310:
308:
305:
304:
288:
285:
284:
233:Euclidean plane
225:
194:projective dual
150:, in which the
128:
89:
86:
85:
84:points in time
69:
66:
65:
43:Euclidean plane
17:
12:
11:
5:
6094:
6084:
6083:
6081:Matroid theory
6078:
6073:
6056:
6055:
6053:
6052:
6047:
6041:
6039:
6035:
6034:
6032:
6031:
6026:
6024:Beck's theorem
6021:
6016:
6011:
6005:
6003:
5999:
5998:
5996:
5995:
5990:
5985:
5980:
5975:
5970:
5965:
5960:
5955:
5950:
5945:
5940:
5935:
5929:
5927:
5925:Configurations
5921:
5920:
5918:
5917:
5916:
5915:
5907:
5906:
5905:
5897:
5896:
5895:
5890:
5880:
5879:
5878:
5876:Steiner system
5873:
5862:
5860:
5856:
5855:
5853:
5852:
5847:
5841:
5839:
5838:Representation
5835:
5834:
5827:
5826:
5819:
5812:
5804:
5798:
5797:
5787:
5768:
5745:
5744:External links
5742:
5740:
5739:
5723:Woodall, H. J.
5719:
5707:Woodall, H. J.
5703:
5687:
5670:(3): 169–171,
5649:
5602:
5583:(3): 245–260,
5566:
5546:
5527:(3): 127–130,
5514:
5505:(4): 330–341,
5494:
5467:(3): 451–464,
5451:
5433:
5385:
5374:
5326:
5311:
5292:(2): 101–104,
5276:
5260:Geombinatorics
5244:
5209:(2): 409–468,
5191:
5166:(2): 247–299,
5143:
5118:(3): 207–212,
5095:
5062:
5027:(3): 361–373,
5011:
4992:(1): 165–194,
4972:
4931:
4891:
4887:
4883:
4880:
4868:
4830:
4825:
4809:
4770:
4751:(2): 175–195,
4739:Chvátal, Vašek
4735:
4716:(2): 193–199,
4703:
4678:(2): 164–167,
4665:
4629:
4624:
4607:
4582:(1): 111–135,
4566:
4553:
4519:
4478:
4443:(4): 778–808,
4430:
4425:
4399:Aigner, Martin
4394:
4392:
4389:
4386:
4385:
4374:Chvátal (2004)
4366:
4354:
4342:
4330:
4318:
4306:
4294:
4280:
4265:
4250:
4238:
4226:
4214:Coxeter (1948)
4206:
4190:
4174:
4157:
4136:
4124:
4110:
4096:
4080:
4065:
4052:
4051:
4049:
4046:
4035:and proved by
4033:Chvátal (2004)
4024:
4021:
3996:
3992:
3988:
3985:
3965:
3941:
3938:
3840:
3837:
3808:
3807:Colored points
3805:
3792:
3789:
3776:
3773:
3770:
3749:
3746:
3743:
3723:
3703:
3683:
3680:
3677:
3653:
3633:
3614:Main article:
3611:
3608:
3595:
3591:
3587:
3567:
3564:
3560:
3556:
3553:
3550:
3525:
3505:
3502:
3499:
3495:
3491:
3488:
3464:
3444:
3440:
3436:
3414:
3410:
3387:
3383:
3379:
3376:
3355:Beck's theorem
3339:
3336:
3333:
3330:
3327:
3322:
3318:
3297:
3294:
3291:
3271:
3268:
3265:
3262:
3259:
3256:
3236:
3233:
3230:
3210:
3206:
3202:
3193:of the proven
3182:
3179:
3176:
3173:
3169:
3165:
3145:
3125:
3122:
3118:
3114:
3111:
3108:
3105:
3102:
3099:
3096:
3091:
3087:
3060:
3057:
3053:
3049:
3046:
3043:
3003:
2999:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2966:
2962:
2941:
2918:
2898:
2878:
2858:
2838:
2834:
2830:
2827:
2824:
2821:
2818:
2815:
2795:
2792:
2789:
2786:
2777:points (thus,
2766:
2742:
2718:
2714:
2710:
2707:
2704:
2701:
2698:
2693:
2689:
2668:
2637:
2633:
2629:
2626:
2623:
2620:
2617:
2614:
2609:
2605:
2572:
2552:
2549:
2545:
2541:
2538:
2535:
2530:
2526:
2495:
2490:
2487:
2484:
2481:
2476:
2472:
2443:
2423:
2420:
2417:
2412:
2408:
2375:
2372:
2369:
2366:
2363:
2358:
2354:
2333:
2313:
2310:
2307:
2302:
2298:
2273:
2269:
2265:
2249:
2246:
2231:
2227:
2214:
2213:
2199:
2195:
2172:
2168:
2145:
2141:
2129:
2116:
2112:
2089:
2085:
2062:
2058:
2048:For each line
2046:
2032:
2028:
2005:
2001:
1989:
1975:
1971:
1959:
1945:
1941:
1929:
1915:
1911:
1888:
1884:
1872:
1850:
1846:
1810:
1807:
1804:
1801:
1798:
1795:
1792:
1768:
1763:
1759:
1755:
1752:
1724:
1719:
1715:
1711:
1708:
1684:
1679:
1675:
1671:
1668:
1652:
1649:
1605:
1602:
1601:
1600:
1588:
1583:
1579:
1575:
1572:
1569:
1566:
1563:
1558:
1555:
1552:
1548:
1544:
1541:
1538:
1533:
1529:
1513:
1512:
1500:
1497:
1494:
1489:
1485:
1481:
1478:
1475:
1472:
1469:
1464:
1461:
1458:
1454:
1429:
1407:
1403:
1382:
1379:
1376:
1364:
1361:
1337:
1334:
1331:
1328:
1325:
1322:
1302:
1299:
1279:
1276:
1273:
1270:
1267:
1264:
1244:
1224:
1220:
1216:
1213:
1210:
1207:
1182:
1162:
1142:
1118:
1098:
1095:
1092:
1089:
1086:
1066:
1063:
1050:
1030:
1010:
983:
979:
976:
972:
952:
948:
945:
941:
920:
917:
913:
892:
889:
885:
865:
844:
841:
820:
800:
780:
760:
739:
736:
715:
695:
675:
655:
635:
614:
611:
590:
570:
543:
523:
503:
483:
463:
432:
429:
403:
400:
387:
384:
381:
376:
372:
368:
348:
328:
325:
322:
317:
313:
292:
241:ordinary point
224:
221:
198:Paul Erdős
127:
124:
111:
108:
105:
102:
99:
96:
93:
73:
15:
9:
6:
4:
3:
2:
6093:
6082:
6079:
6077:
6074:
6072:
6069:
6068:
6066:
6051:
6048:
6046:
6043:
6042:
6040:
6036:
6030:
6027:
6025:
6022:
6020:
6017:
6015:
6012:
6010:
6007:
6006:
6004:
6000:
5994:
5991:
5989:
5986:
5984:
5981:
5979:
5976:
5974:
5971:
5969:
5966:
5964:
5961:
5959:
5956:
5954:
5951:
5949:
5946:
5944:
5941:
5939:
5936:
5934:
5931:
5930:
5928:
5926:
5922:
5914:
5911:
5910:
5908:
5904:
5901:
5900:
5899:Graph theory
5898:
5894:
5891:
5889:
5886:
5885:
5884:
5881:
5877:
5874:
5872:
5869:
5868:
5867:
5866:Combinatorics
5864:
5863:
5861:
5857:
5851:
5848:
5846:
5843:
5842:
5840:
5836:
5832:
5825:
5820:
5818:
5813:
5811:
5806:
5805:
5802:
5795:
5791:
5788:
5784:
5783:
5778:
5774:
5769:
5766:on 2006-10-10
5765:
5761:
5757:
5753:
5748:
5747:
5736:
5732:
5728:
5724:
5720:
5716:
5712:
5708:
5704:
5700:
5696:
5692:
5688:
5685:
5681:
5677:
5673:
5669:
5665:
5664:
5659:
5655:
5650:
5647:
5643:
5639:
5635:
5631:
5627:
5623:
5619:
5615:
5611:
5607:
5603:
5600:
5596:
5591:
5586:
5582:
5578:
5577:
5572:
5567:
5563:
5559:
5555:
5554:Sharir, Micha
5551:
5547:
5544:
5540:
5535:
5530:
5526:
5522:
5521:
5515:
5512:
5508:
5504:
5500:
5495:
5492:
5488:
5484:
5480:
5475:
5470:
5466:
5462:
5461:
5456:
5452:
5448:
5444:
5443:
5438:
5434:
5431:
5427:
5423:
5419:
5415:
5411:
5406:
5401:
5397:
5393:
5392:
5386:
5382:
5381:
5375:
5372:
5368:
5364:
5360:
5355:
5350:
5346:
5342:
5341:
5324:
5316:
5312:
5309:
5305:
5300:
5295:
5291:
5287:
5286:
5281:
5277:
5274:
5270:
5266:
5262:
5261:
5253:
5249:
5245:
5242:
5238:
5234:
5230:
5226:
5222:
5217:
5212:
5208:
5204:
5200:
5196:
5192:
5189:on 2010-09-24
5185:
5181:
5177:
5173:
5169:
5165:
5161:
5160:
5152:
5148:
5147:Geelen, J. F.
5144:
5141:
5137:
5133:
5129:
5125:
5121:
5117:
5113:
5112:
5111:Combinatorica
5104:
5100:
5096:
5093:
5089:
5085:
5081:
5077:
5073:
5072:
5067:
5063:
5060:
5056:
5052:
5048:
5044:
5040:
5035:
5030:
5026:
5022:
5021:
5016:
5012:
5009:
5005:
5000:
4995:
4991:
4987:
4986:
4981:
4977:
4973:
4970:
4966:
4962:
4958:
4954:
4950:
4946:
4942:
4941:
4936:
4932:
4929:
4925:
4920:
4915:
4911:
4907:
4906:
4889:
4885:
4881:
4878:
4869:
4866:
4862:
4858:
4854:
4850:
4846:
4842:
4838:
4837:
4831:
4828:
4826:0-471-50458-0
4822:
4818:
4814:
4810:
4807:
4803:
4799:
4795:
4791:
4787:
4783:
4779:
4775:
4771:
4768:
4764:
4759:
4754:
4750:
4746:
4745:
4740:
4736:
4733:
4729:
4724:
4719:
4715:
4711:
4710:
4704:
4701:
4697:
4693:
4689:
4685:
4681:
4677:
4673:
4672:
4666:
4663:
4659:
4655:
4651:
4650:
4642:
4638:
4634:
4630:
4627:
4625:0-387-23815-8
4621:
4617:
4613:
4608:
4605:
4601:
4597:
4593:
4589:
4585:
4581:
4577:
4576:
4571:
4567:
4564:
4560:
4556:
4554:0-521-41836-4
4550:
4546:
4542:
4541:
4536:
4532:
4528:
4524:
4520:
4517:
4513:
4509:
4505:
4501:
4497:
4493:
4489:
4488:
4487:Combinatorica
4483:
4479:
4476:
4472:
4468:
4464:
4460:
4456:
4451:
4446:
4442:
4438:
4437:
4431:
4428:
4422:
4418:
4414:
4410:
4409:
4404:
4400:
4396:
4395:
4383:
4379:
4375:
4370:
4363:
4358:
4351:
4346:
4340:
4334:
4327:
4322:
4315:
4310:
4303:
4298:
4292:
4287:
4285:
4277:
4272:
4270:
4262:
4257:
4255:
4247:
4242:
4235:
4230:
4223:
4219:
4215:
4210:
4203:
4199:
4194:
4187:
4183:
4178:
4171:
4166:
4164:
4162:
4154:
4149:
4147:
4145:
4143:
4141:
4133:
4128:
4122:
4119:
4114:
4108:
4105:
4100:
4093:
4089:
4084:
4077:
4072:
4070:
4062:
4057:
4053:
4045:
4042:
4038:
4034:
4030:
4029:metric spaces
4020:
4018:
4014:
4010:
3994:
3990:
3986:
3983:
3963:
3955:
3951:
3947:
3937:
3935:
3931:
3926:
3922:
3918:
3917:colinearities
3914:
3910:
3906:
3905:configuration
3902:
3898:
3894:
3889:
3887:
3883:
3882:finite fields
3878:
3874:
3870:
3866:
3862:
3854:
3850:
3845:
3836:
3834:
3830:
3826:
3822:
3818:
3814:
3813:Ronald Graham
3804:
3802:
3798:
3788:
3774:
3771:
3768:
3747:
3744:
3741:
3721:
3701:
3681:
3678:
3675:
3667:
3651:
3631:
3623:
3617:
3607:
3593:
3589:
3585:
3562:
3558:
3554:
3551:
3541:Csima-Sawyer
3539:
3523:
3503:
3500:
3497:
3493:
3489:
3486:
3478:
3462:
3442:
3438:
3434:
3412:
3408:
3385:
3381:
3377:
3374:
3366:
3362:
3358:
3356:
3351:
3337:
3334:
3328:
3320:
3316:
3295:
3292:
3289:
3269:
3266:
3260:
3254:
3234:
3231:
3228:
3208:
3204:
3200:
3177:
3174:
3171:
3167:
3163:
3143:
3120:
3116:
3112:
3109:
3103:
3097:
3089:
3085:
3076:
3072:
3055:
3051:
3047:
3041:
3033:
3029:
3026:known as the
3025:
3021:
3020:configuration
3017:
3001:
2997:
2990:
2987:
2984:
2978:
2972:
2964:
2960:
2939:
2930:
2916:
2896:
2876:
2856:
2836:
2832:
2825:
2822:
2819:
2813:
2793:
2790:
2787:
2784:
2764:
2756:
2740:
2732:
2716:
2712:
2708:
2705:
2699:
2691:
2687:
2666:
2653:
2649:
2635:
2631:
2627:
2624:
2621:
2615:
2607:
2603:
2594:
2590:
2586:
2570:
2547:
2543:
2539:
2533:
2528:
2524:
2515:
2511:
2493:
2488:
2482:
2474:
2470:
2461:
2457:
2441:
2418:
2410:
2406:
2397:
2393:
2390: and
2389:
2373:
2370:
2364:
2356:
2352:
2331:
2308:
2300:
2296:
2271:
2267:
2263:
2254:
2245:
2229:
2225:
2197:
2193:
2170:
2166:
2143:
2139:
2130:
2114:
2110:
2087:
2083:
2060:
2056:
2047:
2030:
2026:
2003:
1999:
1990:
1973:
1969:
1960:
1943:
1939:
1930:
1913:
1909:
1886:
1882:
1873:
1870:
1866:
1848:
1844:
1835:
1834:
1833:
1831:
1826:
1824:
1805:
1802:
1799:
1796:
1790:
1782:
1761:
1757:
1750:
1742:
1738:
1717:
1713:
1706:
1698:
1695:, based on a
1677:
1673:
1666:
1658:
1648:
1645:
1641:
1637:
1632:
1630:
1626:
1622:
1618:
1614:
1610:
1586:
1581:
1577:
1570:
1567:
1564:
1556:
1553:
1550:
1546:
1542:
1539:
1536:
1531:
1527:
1518:
1517:
1516:
1498:
1495:
1492:
1487:
1483:
1476:
1473:
1470:
1462:
1459:
1456:
1452:
1443:
1442:
1441:
1427:
1405:
1401:
1380:
1377:
1374:
1360:
1358:
1354:
1349:
1335:
1332:
1329:
1326:
1323:
1320:
1300:
1297:
1277:
1274:
1271:
1268:
1265:
1262:
1242:
1222:
1218:
1214:
1211:
1208:
1205:
1197:
1180:
1160:
1140:
1132:
1116:
1096:
1093:
1090:
1087:
1084:
1076:
1071:
1062:
1048:
1028:
1008:
999:
997:
981:
977:
974:
970:
950:
946:
943:
939:
918:
915:
911:
890:
887:
883:
863:
842:
839:
818:
798:
778:
758:
737:
734:
713:
693:
673:
653:
633:
612:
609:
588:
568:
559:
557:
554:is ordinary,
541:
521:
501:
481:
461:
452:
450:
446:
437:
431:Kelly's proof
428:
426:
422:
418:
414:
410:
407:details, see
399:
382:
374:
370:
366:
346:
323:
315:
311:
290:
281:
277:
276:line segments
273:
272:Minkowski sum
269:
261:
257:
252:
248:
246:
242:
238:
234:
230:
220:
218:
214:
209:
207:
203:
199:
195:
191:
187:
183:
179:
175:
171:
169:
165:
164:configuration
161:
157:
153:
149:
145:
141:
137:
133:
123:
106:
103:
100:
97:
91:
71:
63:
59:
58:ordinary line
54:
52:
48:
44:
40:
36:
32:
23:
19:
6038:Applications
6008:
5871:Block design
5780:
5764:the original
5755:
5734:
5730:
5714:
5710:
5698:
5694:
5667:
5661:
5654:Grünwald, T.
5613:
5609:
5580:
5574:
5557:
5524:
5518:
5502:
5498:
5464:
5458:
5455:Motzkin, Th.
5446:
5440:
5437:Melchior, E.
5395:
5389:
5379:
5344:
5338:
5315:Kelly, L. M.
5289:
5283:
5280:Kelly, L. M.
5264:
5258:
5206:
5202:
5199:Tao, Terence
5184:the original
5163:
5162:, Series B,
5157:
5115:
5109:
5078:(1): 65–66,
5075:
5069:
5034:math/0403023
5024:
5018:
5015:Elkies, Noam
4989:
4983:
4944:
4938:
4909:
4903:
4843:(1): 30–34,
4840:
4834:
4816:
4784:(1): 26–28,
4781:
4777:
4748:
4742:
4713:
4707:
4675:
4669:
4653:
4647:
4615:
4579:
4573:
4539:
4491:
4485:
4482:Beck, József
4440:
4434:
4407:
4369:
4357:
4345:
4333:
4321:
4309:
4297:
4241:
4229:
4209:
4193:
4177:
4127:
4113:
4099:
4092:Erdős (1982)
4083:
4056:
4026:
3943:
3925:Kelly (1986)
3890:
3869:real numbers
3859:Just as the
3858:
3810:
3797:metric space
3794:
3619:
3359:
3352:
3136:except when
3077:proved that
3073:
2931:
2757:and another
2658:
2595:proved that
2584:
2287:
2215:
1827:
1654:
1633:
1607:
1514:
1366:
1350:
1072:
1068:
1000:
666:. Call them
561:Assume that
560:
453:
442:
405:
265:
240:
226:
210:
206:Tibor Gallai
172:
129:
57:
55:
51:Tibor Gallai
30:
28:
18:
5909:Statistics
5794:Terence Tao
5550:Pach, János
5398:: 121–130,
5347:: 210–219,
4947:: 221–227,
4912:: 187–202,
4656:: 421–423,
4612:Pach, János
4570:Borwein, P.
4378:Chen (2006)
4302:Beck (1983)
4037:Chen (2006)
3930:affine hull
3923:. However,
3897:quaternions
3801:finite sets
3365:Terence Tao
1869:convex hull
1109:must equal
245:arrangement
156:cubic curve
6065:Categories
5938:Fano plane
5903:Hypergraph
5717:(385): 231
5701:(383): 156
5405:2402.03662
5267:(1): 3–9,
5195:Green, Ben
4450:1611.08740
4391:References
3886:Fano plane
3825:Property B
3734:points to
3622:Paul Erdős
3028:Fano plane
1863:that is a
1604:Axiomatics
260:zonohedron
39:finite set
5888:Incidence
5782:MathWorld
5725:(1893b),
5646:250442107
5449:: 461–475
5430:124023963
5371:123865536
5337:points",
5216:1208.4714
5099:Erdős, P.
5066:Erdős, P.
4935:Dirac, G.
4637:Erdős, P.
4604:122052678
4475:125616042
3772:−
3745:−
3566:⌉
3549:⌈
3501:−
3361:Ben Green
3335:≥
3267:≤
3181:%
3175:≈
3124:⌉
3107:⌈
3104:≥
3059:⌋
3045:⌊
2988:−
2823:−
2706:≤
2622:≥
2551:⌋
2537:⌊
2534:≥
2489:≥
2388:de Bruijn
2371:≥
2167:ℓ
2140:ℓ
2111:ℓ
2084:ℓ
2057:ℓ
1883:ℓ
1803:
1568:−
1554:≥
1547:∑
1537:⩾
1496:−
1493:≤
1474:−
1460:≥
1453:∑
1378:≥
1333:−
1324:≤
1275:−
1266:≤
1209:≤
1088:−
1049:ℓ
1029:ℓ
654:ℓ
569:ℓ
542:ℓ
522:ℓ
268:zonohedra
104:
62:algorithm
6002:Theorems
5913:Blocking
5883:Geometry
5250:(1999),
5241:15813230
5101:(1982),
4639:(1948),
4614:(2005),
4537:(1993),
4516:31011939
3950:matroids
3940:Matroids
2932:For odd
1075:embedded
978:′
947:′
919:′
891:′
843:′
738:′
613:′
35:geometry
5684:2303021
5638:0231278
5630:3612678
5599:2572973
5543:2853475
5511:1607014
5491:0041447
5483:1990609
5422:3542040
5363:0097014
5308:0834051
5273:1698297
5233:3090525
5180:1769191
5140:1135308
5132:0698647
5092:2304011
5059:1647360
5051:2202107
5008:0990055
4969:0043485
4949:Bibcode
4928:1194036
4865:0235452
4857:2687957
4806:0024137
4798:2305324
4767:2060634
4732:2195050
4700:0258659
4692:2317330
4662:0028289
4596:1069788
4563:1226888
4508:0729781
4467:3943495
4121:0056941
4107:0041447
2512: (
2458: (
2394: (
1867:of the
1611: (
876:. Then
706:, with
200: (
188: (
176: (
162:form a
158:in the
142: (
134: (
126:History
5859:Fields
5682:
5644:
5636:
5628:
5597:
5541:
5509:
5489:
5481:
5428:
5420:
5369:
5361:
5306:
5271:
5239:
5231:
5178:
5138:
5130:
5090:
5057:
5049:
5006:
4967:
4926:
4863:
4855:
4823:
4804:
4796:
4765:
4730:
4698:
4690:
4660:
4622:
4602:
4594:
4561:
4551:
4514:
4506:
4473:
4465:
4423:
1865:vertex
1627:; see
1393:, let
1173:, and
1129:, the
402:Proofs
5680:JSTOR
5642:S2CID
5626:JSTOR
5479:JSTOR
5426:S2CID
5400:arXiv
5367:S2CID
5255:(PDF)
5237:S2CID
5211:arXiv
5187:(PDF)
5154:(PDF)
5136:S2CID
5106:(PDF)
5088:JSTOR
5055:S2CID
5029:arXiv
4853:JSTOR
4794:JSTOR
4688:JSTOR
4644:(PDF)
4600:S2CID
4512:S2CID
4471:S2CID
4445:arXiv
4048:Notes
2392:Erdős
2102:with
182:1893b
178:1893a
154:of a
140:Kelly
5993:Dual
5737:: 98
4821:ISBN
4620:ISBN
4549:ISBN
4421:ISBN
4015:for
3847:The
3378:>
3363:and
3178:92.3
2514:1951
2460:1951
2396:1948
1617:1969
1613:1948
1021:and
994:are
963:and
791:and
686:and
258:, a
254:The
202:1943
190:1941
144:1986
138:).
136:1893
29:The
5792:by
5672:doi
5618:doi
5585:doi
5529:doi
5469:doi
5410:doi
5396:150
5349:doi
5294:doi
5221:doi
5168:doi
5120:doi
5080:doi
5039:doi
4994:doi
4957:doi
4914:doi
4845:doi
4786:doi
4753:doi
4718:doi
4680:doi
4584:doi
4545:273
4496:doi
4455:doi
4413:doi
3895:or
3863:or
3620:As
3477:odd
3475:is
2508:.
1800:log
1351:As
856:on
831:to
646:on
101:log
33:in
6067::
5779:,
5775:,
5758:,
5754:,
5735:59
5733:,
5729:,
5715:46
5713:,
5699:46
5697:,
5678:,
5668:51
5666:,
5656:;
5640:,
5634:MR
5632:,
5624:,
5614:52
5612:,
5595:MR
5593:,
5581:50
5579:,
5573:,
5552:;
5539:MR
5537:,
5525:45
5523:,
5507:MR
5501:,
5487:MR
5485:,
5477:,
5465:70
5463:,
5445:,
5424:,
5418:MR
5416:,
5408:,
5394:,
5365:,
5359:MR
5357:,
5345:10
5343:,
5304:MR
5302:,
5288:,
5269:MR
5263:,
5257:,
5235:,
5229:MR
5227:,
5219:,
5207:50
5205:,
5197:;
5176:MR
5174:,
5164:79
5156:,
5134:,
5128:MR
5126:,
5114:,
5108:,
5086:,
5076:50
5074:,
5053:,
5047:MR
5045:,
5037:,
5025:35
5023:,
5004:MR
5002:,
4990:38
4988:,
4978:;
4965:MR
4963:,
4955:,
4943:,
4924:MR
4922:,
4908:,
4890:13
4861:MR
4859:,
4851:,
4841:41
4839:,
4802:MR
4800:,
4792:,
4782:55
4780:,
4763:MR
4761:,
4749:31
4747:,
4728:MR
4726:,
4714:35
4712:,
4696:MR
4694:,
4686:,
4676:77
4674:,
4658:MR
4654:10
4652:,
4646:,
4635:;
4598:,
4592:MR
4590:,
4580:40
4578:,
4559:MR
4557:,
4547:,
4529:;
4525:;
4510:,
4504:MR
4502:,
4490:,
4469:,
4463:MR
4461:,
4453:,
4441:61
4439:,
4419:,
4401:;
4380:;
4376:;
4283:^
4268:^
4253:^
4216:;
4200:;
4160:^
4139:^
4118:MR
4104:MR
4090:;
4068:^
4019:.
3835:.
3563:13
3350:.
3172:13
3164:12
3121:13
2648:.
2454:.
2386:.
1825:.
1615:,
1499:3.
1348:.
1153:,
558:.
447:.
427:.
219:.
180:,
122:.
5823:e
5816:t
5809:v
5674::
5620::
5587::
5531::
5503:4
5471::
5447:5
5412::
5402::
5351::
5325:n
5296::
5290:1
5265:9
5223::
5213::
5170::
5122::
5116:2
5082::
5041::
5031::
4996::
4959::
4951::
4945:2
4916::
4910:9
4886:/
4882:n
4879:6
4847::
4788::
4755::
4720::
4682::
4586::
4498::
4492:3
4457::
4447::
4415::
4364:.
4352:.
4328:.
4316:.
4304:.
4278:.
4263:.
4248:.
4236:.
4224:.
4204:.
4188:.
4172:.
4155:.
4134:.
4094:.
4078:.
4063:.
3995:7
3991:/
3987:n
3984:3
3964:n
3855:.
3775:1
3769:n
3748:1
3742:n
3722:n
3702:n
3682:3
3679:=
3676:n
3652:n
3632:n
3594:2
3590:/
3586:n
3559:/
3555:n
3552:6
3524:C
3504:C
3498:4
3494:/
3490:n
3487:3
3463:n
3443:2
3439:/
3435:n
3413:0
3409:n
3386:0
3382:n
3375:n
3338:4
3332:)
3329:7
3326:(
3321:2
3317:t
3296:7
3293:=
3290:n
3270:3
3264:)
3261:7
3258:(
3255:t
3235:7
3232:=
3229:n
3209:2
3205:/
3201:n
3168:/
3144:n
3117:/
3113:n
3110:6
3101:)
3098:n
3095:(
3090:2
3086:t
3056:4
3052:/
3048:n
3042:3
3002:2
2998:/
2994:)
2991:1
2985:n
2982:(
2979:=
2976:)
2973:n
2970:(
2965:2
2961:t
2940:n
2917:v
2897:v
2877:m
2857:m
2837:2
2833:/
2829:)
2826:1
2820:m
2817:(
2814:m
2794:m
2791:2
2788:=
2785:n
2765:m
2741:m
2717:2
2713:/
2709:n
2703:)
2700:n
2697:(
2692:2
2688:t
2667:n
2636:7
2632:/
2628:n
2625:3
2619:)
2616:n
2613:(
2608:2
2604:t
2571:n
2548:2
2544:/
2540:n
2529:2
2525:t
2494:n
2486:)
2483:n
2480:(
2475:2
2471:t
2442:n
2422:)
2419:n
2416:(
2411:2
2407:t
2374:3
2368:)
2365:n
2362:(
2357:2
2353:t
2332:n
2312:)
2309:n
2306:(
2301:2
2297:t
2272:2
2268:/
2264:n
2230:0
2226:p
2212:.
2198:0
2194:p
2171:0
2144:i
2115:0
2088:i
2061:i
2031:0
2027:p
2004:0
2000:p
1988:.
1974:0
1970:p
1944:0
1940:p
1914:0
1910:p
1887:0
1849:0
1845:p
1809:)
1806:n
1797:n
1794:(
1791:O
1767:)
1762:2
1758:n
1754:(
1751:O
1723:)
1718:2
1714:n
1710:(
1707:O
1683:)
1678:3
1674:n
1670:(
1667:O
1587:.
1582:k
1578:t
1574:)
1571:3
1565:k
1562:(
1557:4
1551:k
1543:+
1540:3
1532:2
1528:t
1488:k
1484:t
1480:)
1477:3
1471:k
1468:(
1463:2
1457:k
1428:k
1406:k
1402:t
1381:2
1375:k
1336:3
1330:V
1327:3
1321:E
1301:V
1298:3
1278:3
1272:V
1269:3
1263:E
1243:F
1223:3
1219:/
1215:E
1212:2
1206:F
1181:F
1161:E
1141:V
1117:1
1097:F
1094:+
1091:E
1085:V
1009:P
982:C
975:B
971:B
951:C
944:P
940:P
916:P
912:P
888:B
884:B
864:m
840:B
819:B
799:C
779:P
759:m
735:P
714:B
694:C
674:B
634:P
610:P
589:S
502:P
482:S
462:S
386:)
383:n
380:(
375:2
371:t
367:2
347:n
327:)
324:n
321:(
316:2
312:t
291:n
110:)
107:n
98:n
95:(
92:O
72:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
