Knowledge (XXG)

Happy ending problem

Source đź“ť

370: 188: 34: 738:
There is also the question of whether any sufficiently large set of points in general position has an "empty" convex quadrilateral, pentagon, etc., that is, one that contains no other input point. The original solution to the happy ending problem can be adapted to show that any five points in general
739:
position have an empty convex quadrilateral, as shown in the illustration, and any ten points in general position have an empty convex pentagon. However, there exist arbitrarily large sets of points in general position that contain no empty convex
443: 729: 649: 758:
proved that every sufficiently large point set in general position contains a convex empty hexagon. More specifically, Gerken showed that the number of points needed is no more than
840:
in sufficiently large planar point sets, by projecting the higher-dimensional point set into an arbitrary two-dimensional subspace. However, the number of points necessary to find
566: 982:. They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations. 500: 177: 1770: 1454: 1103:, Ex. 7.3.6, p. 126. This result follows by applying a Ramsey-theoretic argument similar to Szekeres's original proof together with Perles's result on the case 138: 1408: 782:(9). At least 30 points are needed; there exists a set of 29 points in general position with no empty convex hexagon. The question was finally answered by 1285:
Heule, Marijn J. H.; Scheucher, Manfred (2024), "Happy Ending: An Empty Hexagon in Every Set of 30 Points", in Finkbeiner, Bernd; Kovács, Laura (eds.),
848:
may be smaller in higher dimensions than it is in the plane, and it is possible to find subsets that are more highly constrained. In particular, in
1742:
Surveys on Discrete and Computational Geometry: Twenty Years Later: AMS-IMS-SIAM Joint Summer Research Conference, June 18-22, 2006, Snowbird, Utah
379: 116:
states precisely a more general relationship between the number of points in a general-position point set and its largest subset forming a convex
923: 292:; the more difficult part of the proof is to show that every set of nine points in general position contains the vertices of a convex pentagon. 1766: 1666: 1505: 1478: 1416: 1215: 1134: 658: 1813: 1750: 1263: 1709:, Mathematical Sciences Research Institute Publications, vol. 52, Cambridge University Press, pp. 557–568, archived from 1701: 1626: 573: 1531: 786:, who showed, using a SAT solving approach, that indeed every set of 30 points in general position contains an empty hexagon. 1828: 1554:(1994), "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability", 1357: 799: 224: 27: 1556: 511: 448: 37:
The happy ending problem: every set of five points in general position contains the vertices of a convex quadrilateral
1018: 1808: 120:, namely that the smallest number of points for which any general position arrangement contains a convex subset of 1435: 931: 93:
The happy ending theorem can be proven by a simple case analysis: if four or more points are vertices of the
1818: 1838: 1833: 1169: 20: 943:
In this context, general position means that no two points coincide and no three points are collinear.
1388: 1245: 1006: 1452:
Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey",
905: 1091:, Ex. 6.5.6, p.120. GrĂĽnbaum attributes this result to a private communication of Micha A. Perles. 1736: 1611: 1593: 1573: 1376: 1326: 1290: 101:
with two points inside it, the two inner points and one of the triangle sides can be chosen. See
1395:, Congressus Numerantium, vol. 1, Baton Rouge, La.: Louisiana State Univ., pp. 180–188 1237: 1688:
Tóth, G.; Valtr, P. (2005), "The Erdős-Szekeres theorem: upper bounds and related results", in
215:, any sufficiently large finite set of points in the plane in general position has a subset of 143: 1823: 1781: 1746: 1259: 97:, any four such points can be chosen. If on the other hand, the convex hull has the form of a 26:"ErdĹ‘s–Szekeres conjecture" redirects here. For their theorem on monotonic subsequences, see 1745:, Contemporary Mathematics, vol. 453, American Mathematical Society, pp. 433–442, 1728: 1689: 1675: 1640: 1603: 1565: 1514: 1487: 1463: 1425: 1366: 1336: 1300: 1249: 1224: 1143: 72: 1348: 1622: 1400: 1344: 1255: 1186: 1160: 927: 861: 845: 826: 818: 58: 54: 1710: 1650: 1631: 1547: 1527: 1289:, Lecture Notes in Computer Science, vol. 14570, Springer-Verlag, pp. 61–80, 1014: 1010: 807: 123: 76: 798:
points minimizing the number of convex quadrilaterals is equivalent to minimizing the
1802: 1785: 1732: 1693: 1500: 1380: 1314: 1201: 1182: 1156: 1129: 803: 766:
defined above, while Nicolás showed that the number of points needed is no more than
87: 79: 50: 1615: 1539: 187: 1551: 1404: 1468: 1164: 1305: 1241: 94: 42: 33: 774:
supplies a simplification of Gerken's proof that however requires more points,
1774: 1645: 1519: 1492: 1229: 833:
greater than the dimension: this follows immediately from existence of convex
363: 1790: 1697: 1125: 1371: 965:, this was first proved by E. Makai; the first published proof appeared in 810:. The number of quadrilaterals must be proportional to the fourth power of 740: 282: 98: 1340: 1317:; Tardos, Gábor (2020), "Two extensions of the Erdős–Szekeres problem", 369: 1680: 1607: 1577: 1430: 1148: 747: 209: 117: 1740: 1391:; Stanton, R.G. (1970), "A combinatorial problem on convex regions", 1213:
Gerken, Tobias (2008), "Empty convex hexagons in planar point sets",
1584:
Suk, Andrew (2016), "On the Erdős–Szekeres convex polygon problem",
1569: 86:
This was one of the original results that led to the development of
1598: 1331: 1295: 1664:
Tóth, G.; Valtr, P. (1998), "Note on the Erdős-Szekeres theorem",
1272:
Harborth, Heiko (1978), "Konvexe FĂĽnfecke in ebenen Punktmengen",
373:
A set of sixteen points in general position with no convex hexagon
368: 186: 1287:
Tools and Algorithms for the Construction and Analysis of Systems
191:
A set of eight points in general position with no convex pentagon
16:
Five coplanar points have a subset forming a convex quadrilateral
1393:
Proc. Louisiana Conf. Combinatorics, Graph Theory and Computing
1254:, Graduate Texts in Mathematics, vol. 221 (2nd ed.), 1503:(2003), "Finding sets of points without empty convex 6-gons", 966: 438:{\displaystyle f(N)=1+2^{N-2}\quad {\text{for all }}N\geq 3.} 1189:(1961), "On some extremum problems in elementary geometry", 856: + 3 points in general position have a subset of 445:
They proved later, by constructing explicit examples, that
1627:"Computer solution to the 17-point Erdős-Szekeres problem" 1355:
Horton, J. D. (1983), "Sets with no empty convex 7-gons",
821:, sufficiently large sets of points will have a subset of 817:
It is straightforward to show that, in higher-dimensional
179:. It remains unproven, but less precise bounds are known. 1030: 1476:
Nicolás, Carlos M. (2007), "The empty hexagon theorem",
75:
has a subset of four points that form the vertices of a
746:
For a long time the question of the existence of empty
952:
This was the original problem, proved by Esther Klein.
661: 576: 514: 451: 382: 223:
The proof appeared in the same paper that proves the
146: 126: 1771:
Ramsey-theoretic proof of the Erdős-Szekeres theorem
1564:(10), Mathematical Association of America: 939–943, 1319:
Journal of the European Mathematical Society (JEMS)
227:on monotonic subsequences in sequences of numbers. 219:points that form the vertices of a convex polygon. 1313:Holmsen, Andreas F.; Mojarrad, Hossein Nassajian; 860: + 2 points that form the vertices of a 724:{\displaystyle f(N)\leq 2^{N+O({\sqrt {NlogN}})}.} 723: 643: 560: 494: 437: 171: 132: 105:for an illustrated explanation of this proof, and 570:Suk actually proves, for N sufficiently large, 285:is shown in the illustration, demonstrating that 249:points in general position must contain a convex 1409:"Finding convex sets among points in the plane" 1077: 979: 783: 1455:Bulletin of the American Mathematical Society 1132:(1998), "Forced convex n-gons in the plane", 991: 967:Kalbfleisch, Kalbfleisch & Stanton (1970) 962: 900:) points in general position has a subset of 323: 195: 8: 1208:, Cambridge, MA: MIT Press, pp. 680–689 1191:Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 644:{\displaystyle f(N)\leq 2^{N+6N^{2/3}logN}.} 106: 924:A world of teaching and numbers - times two 202: 109:for a more detailed survey of the problem. 65: 1727:Valtr, P. (2008), "On empty hexagons", in 1679: 1644: 1597: 1518: 1491: 1467: 1429: 1370: 1330: 1304: 1294: 1228: 1147: 814:, but the precise constant is not known. 694: 681: 660: 614: 610: 596: 575: 534: 513: 477: 450: 421: 408: 381: 151: 145: 125: 1703:Combinatorial and Computational Geometry 1100: 1088: 1065: 1042: 102: 32: 916: 751: 281:. A set of eight points with no convex 71:any set of five points in the plane in 1206:The Art of Counting: Selected Writings 1054: 755: 1165:"A combinatorial problem in geometry" 771: 337:is known to be finite for all finite 198:proved the following generalisation: 7: 825:points that forms the vertices of a 561:{\displaystyle f(N)\leq 2^{N+o(N)}.} 347:On the basis of the known values of 1667:Discrete and Computational Geometry 1506:Discrete and Computational Geometry 1479:Discrete and Computational Geometry 1417:Discrete and Computational Geometry 1216:Discrete and Computational Geometry 1135:Discrete and Computational Geometry 1002: 904:points that form the vertices of a 653:This was subsequently improved to: 502:In 2016 Andrew Suk showed that for 495:{\displaystyle f(N)\geq 1+2^{N-2}.} 53:because it led to the marriage of 14: 362:= 3, 4 and 5, ErdĹ‘s and Szekeres 794:The problem of finding sets of 420: 1358:Canadian Mathematical Bulletin 934:, 2005-11-07, cited 2014-09-04 713: 691: 671: 665: 586: 580: 550: 544: 524: 518: 461: 455: 392: 386: 366:in their original paper that 61:) is the following statement: 19:For the Fred Frith album, see 1: 1557:American Mathematical Monthly 1469:10.1090/S0273-0979-00-00877-6 1078:Scheinerman & Wilf (1994) 1021:for the asymptotic expansion. 980:Szekeres & Peters (2006) 864:. More generally, for every 784:Heule & Scheucher (2024) 1306:10.1007/978-3-031-57246-3_5 1204:(1973), Spencer, J. (ed.), 1013:for notation used here and 992:ErdĹ‘s & Szekeres (1961) 963:ErdĹ‘s & Szekeres (1935) 324:ErdĹ‘s & Szekeres (1935) 196:ErdĹ‘s & Szekeres (1935) 1855: 762:(9) for the same function 107:Morris & Soltan (2000) 25: 18: 1646:10.1017/S144618110000300X 1520:10.1007/s00454-002-2829-x 1493:10.1007/s00454-007-1343-6 1230:10.1007/s00454-007-9018-x 932:The Sydney Morning Herald 888:) such that every set of 172:{\displaystyle 2^{n-2}+1} 114:ErdĹ‘s–Szekeres conjecture 1814:Euclidean plane geometry 1240:(2003), Kaibel, Volker; 1019:Stirling's approximation 978:This has been proved by 1274:Elemente der Mathematik 253:-gon. It is known that 1548:Scheinerman, Edward R. 1372:10.4153/CMB-1983-077-8 1170:Compositio Mathematica 876:there exists a number 725: 645: 562: 496: 439: 374: 225:ErdĹ‘s–Szekeres theorem 192: 173: 134: 38: 28:ErdĹ‘s–Szekeres theorem 1829:Mathematical problems 1625:; Peters, L. (2006), 1031:Holmsen et al. (2020) 734:Empty convex polygons 726: 646: 563: 497: 440: 372: 245:for which any set of 190: 174: 135: 36: 21:The Happy End Problem 1767:Happy ending problem 1532:"Planes of Budapest" 1007:binomial coefficient 659: 574: 512: 449: 380: 144: 124: 47:happy ending problem 1786:"Happy End Problem" 1586:J. Amer. Math. Soc. 1387:Kalbfleisch, J.D.; 906:neighborly polytope 802:in a straight-line 750:remained open, but 322:. By the result of 315:is unknown for all 241:denote the minimum 206: —  69: —  1782:Weisstein, Eric W. 1681:10.1007/PL00009363 1431:10.1007/PL00009358 1246:Ziegler, GĂĽnter M. 1149:10.1007/PL00009353 852:dimensions, every 721: 641: 558: 492: 435: 375: 204: 193: 169: 130: 67: 39: 1809:Discrete geometry 1729:Goodman, Jacob E. 1690:Goodman, Jacob E. 1389:Kalbfleisch, J.G. 1341:10.4171/jems/1000 1325:(12): 3981–3995, 711: 424: 208:for any positive 133:{\displaystyle n} 1846: 1795: 1794: 1755: 1737:Pollack, Richard 1723: 1722: 1721: 1715: 1708: 1684: 1683: 1660: 1659: 1658: 1649:, archived from 1648: 1618: 1608:10.1090/jams/869 1601: 1592:(4): 1047–1053, 1580: 1552:Wilf, Herbert S. 1543: 1538:, archived from 1523: 1522: 1496: 1495: 1472: 1471: 1448: 1447: 1446: 1440: 1434:, archived from 1433: 1413: 1396: 1383: 1374: 1351: 1334: 1309: 1308: 1298: 1281: 1268: 1251:Convex Polytopes 1238:GrĂĽnbaum, Branko 1233: 1232: 1223:(1–3): 239–272, 1209: 1198: 1178: 1152: 1151: 1112: 1098: 1092: 1086: 1080: 1075: 1069: 1063: 1057: 1052: 1046: 1040: 1034: 1028: 1022: 1000: 994: 989: 983: 976: 970: 959: 953: 950: 944: 941: 935: 921: 872: >  839: 819:Euclidean spaces 790:Related problems 778:(15) instead of 730: 728: 727: 722: 717: 716: 712: 695: 650: 648: 647: 642: 637: 636: 623: 622: 618: 567: 565: 564: 559: 554: 553: 508: 501: 499: 498: 493: 488: 487: 444: 442: 441: 436: 425: 422: 419: 418: 357: 342: 336: 321: 314: 300: 291: 280: 271: 262: 248: 244: 240: 218: 214: 207: 178: 176: 175: 170: 162: 161: 139: 137: 136: 131: 73:general position 70: 1854: 1853: 1849: 1848: 1847: 1845: 1844: 1843: 1799: 1798: 1780: 1779: 1763: 1758: 1753: 1726: 1719: 1717: 1713: 1706: 1687: 1663: 1656: 1654: 1621: 1583: 1570:10.2307/2975158 1546: 1528:Peterson, Ivars 1526: 1499: 1475: 1451: 1444: 1442: 1438: 1411: 1399: 1386: 1354: 1312: 1284: 1271: 1266: 1256:Springer-Verlag 1236: 1212: 1200: 1199:; reprinted in 1181: 1155: 1124: 1120: 1115: 1111: + 2. 1101:GrĂĽnbaum (2003) 1099: 1095: 1089:GrĂĽnbaum (2003) 1087: 1083: 1076: 1072: 1066:Overmars (2003) 1064: 1060: 1053: 1049: 1043:Harborth (1978) 1041: 1037: 1029: 1025: 1015:Catalan numbers 1001: 997: 990: 986: 977: 973: 960: 956: 951: 947: 942: 938: 928:Michael Cowling 922: 918: 914: 862:cyclic polytope 846:convex position 834: 827:convex polytope 800:crossing number 792: 736: 677: 657: 656: 606: 592: 572: 571: 530: 510: 509: 503: 473: 447: 446: 404: 378: 377: 348: 338: 327: 316: 305: 295: 286: 275: 266: 257: 246: 242: 231: 221: 216: 212: 205: 185: 183:Larger polygons 147: 142: 141: 122: 121: 103:Peterson (2000) 84: 68: 55:George Szekeres 49:" (so named by 31: 24: 17: 12: 11: 5: 1852: 1850: 1842: 1841: 1836: 1831: 1826: 1821: 1819:Quadrilaterals 1816: 1811: 1801: 1800: 1797: 1796: 1777: 1762: 1761:External links 1759: 1757: 1756: 1751: 1724: 1685: 1674:(3): 457–459, 1661: 1639:(2): 151–164, 1632:ANZIAM Journal 1619: 1581: 1544: 1524: 1513:(1): 153–158, 1497: 1486:(2): 389–397, 1473: 1462:(4): 437–458, 1449: 1424:(3): 405–410, 1401:Kleitman, D.J. 1397: 1384: 1365:(4): 482–484, 1352: 1310: 1282: 1269: 1264: 1234: 1210: 1179: 1153: 1142:(3): 367–371, 1121: 1119: 1116: 1114: 1113: 1093: 1081: 1070: 1058: 1047: 1035: 1023: 1011:big O notation 995: 984: 971: 954: 945: 936: 915: 913: 910: 808:complete graph 791: 788: 752:Nicolás (2007) 735: 732: 720: 715: 710: 707: 704: 701: 698: 693: 690: 687: 684: 680: 676: 673: 670: 667: 664: 640: 635: 632: 629: 626: 621: 617: 613: 609: 605: 602: 599: 595: 591: 588: 585: 582: 579: 557: 552: 549: 546: 543: 540: 537: 533: 529: 526: 523: 520: 517: 491: 486: 483: 480: 476: 472: 469: 466: 463: 460: 457: 454: 434: 431: 428: 417: 414: 411: 407: 403: 400: 397: 394: 391: 388: 385: 345: 344: 302: 293: 273: 264: 200: 184: 181: 168: 165: 160: 157: 154: 150: 129: 63: 15: 13: 10: 9: 6: 4: 3: 2: 1851: 1840: 1837: 1835: 1834:Ramsey theory 1832: 1830: 1827: 1825: 1822: 1820: 1817: 1815: 1812: 1810: 1807: 1806: 1804: 1793: 1792: 1787: 1783: 1778: 1776: 1772: 1768: 1765: 1764: 1760: 1754: 1752:9780821842393 1748: 1744: 1743: 1738: 1734: 1730: 1725: 1716:on 2019-07-28 1712: 1705: 1704: 1699: 1695: 1691: 1686: 1682: 1677: 1673: 1669: 1668: 1662: 1653:on 2019-12-13 1652: 1647: 1642: 1638: 1634: 1633: 1628: 1624: 1620: 1617: 1613: 1609: 1605: 1600: 1595: 1591: 1587: 1582: 1579: 1575: 1571: 1567: 1563: 1559: 1558: 1553: 1549: 1545: 1542:on 2013-07-02 1541: 1537: 1533: 1529: 1525: 1521: 1516: 1512: 1508: 1507: 1502: 1498: 1494: 1489: 1485: 1481: 1480: 1474: 1470: 1465: 1461: 1457: 1456: 1450: 1441:on 2022-02-04 1437: 1432: 1427: 1423: 1419: 1418: 1410: 1406: 1402: 1398: 1394: 1390: 1385: 1382: 1378: 1373: 1368: 1364: 1360: 1359: 1353: 1350: 1346: 1342: 1338: 1333: 1328: 1324: 1320: 1316: 1311: 1307: 1302: 1297: 1292: 1288: 1283: 1279: 1275: 1270: 1267: 1265:0-387-00424-6 1261: 1257: 1253: 1252: 1247: 1243: 1239: 1235: 1231: 1226: 1222: 1218: 1217: 1211: 1207: 1203: 1196: 1192: 1188: 1184: 1180: 1176: 1172: 1171: 1166: 1162: 1158: 1154: 1150: 1145: 1141: 1137: 1136: 1131: 1127: 1126:Chung, F.R.K. 1123: 1122: 1117: 1110: 1107: =  1106: 1102: 1097: 1094: 1090: 1085: 1082: 1079: 1074: 1071: 1067: 1062: 1059: 1056: 1055:Horton (1983) 1051: 1048: 1044: 1039: 1036: 1032: 1027: 1024: 1020: 1016: 1012: 1008: 1004: 999: 996: 993: 988: 985: 981: 975: 972: 968: 964: 961:According to 958: 955: 949: 946: 940: 937: 933: 929: 925: 920: 917: 911: 909: 907: 903: 899: 895: 891: 887: 883: 879: 875: 871: 867: 863: 859: 855: 851: 847: 843: 837: 832: 828: 824: 820: 815: 813: 809: 805: 801: 797: 789: 787: 785: 781: 777: 773: 769: 765: 761: 757: 756:Gerken (2008) 753: 749: 744: 742: 733: 731: 718: 708: 705: 702: 699: 696: 688: 685: 682: 678: 674: 668: 662: 654: 651: 638: 633: 630: 627: 624: 619: 615: 611: 607: 603: 600: 597: 593: 589: 583: 577: 568: 555: 547: 541: 538: 535: 531: 527: 521: 515: 506: 489: 484: 481: 478: 474: 470: 467: 464: 458: 452: 432: 429: 426: 423:for all  415: 412: 409: 405: 401: 398: 395: 389: 383: 371: 367: 365: 361: 355: 351: 341: 334: 330: 325: 319: 312: 308: 304:The value of 303: 298: 294: 289: 284: 278: 274: 269: 265: 260: 256: 255: 254: 252: 238: 234: 228: 226: 220: 211: 199: 197: 189: 182: 180: 166: 163: 158: 155: 152: 148: 127: 119: 115: 110: 108: 104: 100: 96: 91: 89: 88:Ramsey theory 83: 81: 80:quadrilateral 78: 74: 62: 60: 56: 52: 48: 44: 35: 29: 22: 1789: 1741: 1718:, retrieved 1711:the original 1702: 1671: 1665: 1655:, retrieved 1651:the original 1636: 1630: 1623:Szekeres, G. 1589: 1585: 1561: 1555: 1540:the original 1535: 1510: 1504: 1501:Overmars, M. 1483: 1477: 1459: 1453: 1443:, retrieved 1436:the original 1421: 1415: 1392: 1362: 1356: 1322: 1318: 1286: 1280:(5): 116–118 1277: 1273: 1250: 1242:Klee, Victor 1220: 1214: 1205: 1194: 1190: 1187:Szekeres, G. 1174: 1168: 1161:Szekeres, G. 1139: 1133: 1130:Graham, R.L. 1108: 1104: 1096: 1084: 1073: 1061: 1050: 1038: 1026: 998: 987: 974: 957: 948: 939: 919: 901: 897: 893: 889: 885: 881: 877: 873: 869: 865: 857: 853: 849: 841: 835: 830: 822: 816: 811: 795: 793: 779: 775: 772:Valtr (2008) 767: 763: 759: 745: 737: 655: 652: 569: 504: 376: 359: 353: 349: 346: 339: 332: 328: 317: 310: 306: 296: 287: 276: 267: 263:, trivially. 258: 250: 236: 232: 229: 222: 201: 194: 113: 111: 92: 85: 64: 59:Esther Klein 46: 40: 1733:Pach, János 1694:Pach, János 1405:Pachter, L. 1315:Pach, János 364:conjectured 95:convex hull 43:mathematics 1839:Paul ErdĹ‘s 1803:Categories 1775:PlanetMath 1720:2015-02-28 1698:Welzl, Emo 1657:2007-01-05 1599:1604.08657 1536:MAA Online 1445:2019-09-23 1332:1710.11415 1296:2403.00737 1118:References 1003:Suk (2016) 844:points in 829:, for any 290:(5) > 8 140:points is 51:Paul ErdĹ‘s 1791:MathWorld 1381:120267029 1202:ErdĹ‘s, P. 1183:ErdĹ‘s, P. 1177:: 463–470 1157:ErdĹ‘s, P. 675:≤ 590:≤ 528:≤ 482:− 465:≥ 430:≥ 413:− 156:− 1824:Polygons 1739:(eds.), 1700:(eds.), 1616:15732134 1530:(2000), 1407:(1998), 1248:(eds.), 1163:(1935), 748:hexagons 741:heptagon 299:(6) = 17 283:pentagon 99:triangle 1578:2975158 1349:4176784 1197:: 53–62 804:drawing 279:(5) = 9 270:(4) = 5 261:(3) = 3 210:integer 203:Theorem 118:polygon 66:Theorem 45:, the " 1749:  1614:  1576:  1379:  1347:  1262:  1005:. See 770:(25). 320:> 6 77:convex 1714:(PDF) 1707:(PDF) 1612:S2CID 1594:arXiv 1574:JSTOR 1439:(PDF) 1412:(PDF) 1377:S2CID 1327:arXiv 1291:arXiv 912:Notes 838:-gons 806:of a 1769:and 1747:ISBN 1260:ISBN 1009:and 868:and 754:and 358:for 230:Let 112:The 57:and 1773:on 1676:doi 1641:doi 1604:doi 1566:doi 1562:101 1515:doi 1488:doi 1464:doi 1426:doi 1367:doi 1337:doi 1301:doi 1225:doi 1195:3–4 1144:doi 1017:or 507:≥ 7 41:In 1805:: 1788:, 1784:, 1735:; 1731:; 1696:; 1692:; 1672:19 1670:, 1637:48 1635:, 1629:, 1610:, 1602:, 1590:30 1588:, 1572:, 1560:, 1550:; 1534:, 1511:29 1509:, 1484:38 1482:, 1460:37 1458:, 1422:19 1420:, 1414:, 1403:; 1375:, 1363:26 1361:, 1345:MR 1343:, 1335:, 1323:22 1321:, 1299:, 1278:33 1276:, 1258:, 1244:; 1221:39 1219:, 1193:, 1185:; 1173:, 1167:, 1159:; 1140:19 1138:, 1128:; 930:, 926:, 908:. 896:, 884:, 743:. 433:3. 326:, 90:. 82:. 1678:: 1643:: 1606:: 1596:: 1568:: 1517:: 1490:: 1466:: 1428:: 1369:: 1339:: 1329:: 1303:: 1293:: 1227:: 1175:2 1146:: 1109:d 1105:k 1068:. 1045:. 1033:. 969:. 902:k 898:k 894:d 892:( 890:m 886:k 882:d 880:( 878:m 874:d 870:k 866:d 858:d 854:d 850:d 842:k 836:k 831:k 823:k 812:n 796:n 780:f 776:f 768:f 764:f 760:f 719:. 714:) 709:N 706:g 703:o 700:l 697:N 692:( 689:O 686:+ 683:N 679:2 672:) 669:N 666:( 663:f 639:. 634:N 631:g 628:o 625:l 620:3 616:/ 612:2 608:N 604:6 601:+ 598:N 594:2 587:) 584:N 581:( 578:f 556:. 551:) 548:N 545:( 542:o 539:+ 536:N 532:2 525:) 522:N 519:( 516:f 505:N 490:. 485:2 479:N 475:2 471:+ 468:1 462:) 459:N 456:( 453:f 427:N 416:2 410:N 406:2 402:+ 399:1 396:= 393:) 390:N 387:( 384:f 360:N 356:) 354:N 352:( 350:f 343:. 340:N 335:) 333:N 331:( 329:f 318:N 313:) 311:N 309:( 307:f 301:. 297:f 288:f 277:f 272:. 268:f 259:f 251:N 247:M 243:M 239:) 237:N 235:( 233:f 217:N 213:N 167:1 164:+ 159:2 153:n 149:2 128:n 30:. 23:.

Index

The Happy End Problem
Erdős–Szekeres theorem

mathematics
Paul Erdős
George Szekeres
Esther Klein
general position
convex
quadrilateral
Ramsey theory
convex hull
triangle
Peterson (2000)
Morris & Soltan (2000)
polygon

Erdős & Szekeres (1935)
integer
Erdős–Szekeres theorem
pentagon
Erdős & Szekeres (1935)
conjectured
A set of sixteen points in general position with no convex hexagon
heptagon
hexagons
Nicolás (2007)
Gerken (2008)
Valtr (2008)
Heule & Scheucher (2024)

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

↑