Sylvester–Gallais sats

Tre av de vanliga linjerna i ett 4 × 4 rutnät av punkter

Sylvester –Gallais sats i geometri säger att varje ändlig uppsättning punkter i det euklidiska planet har en linje som går genom exakt två av punkterna eller en linje som går genom dem alla. Den är uppkallad efter James Joseph Sylvester , som ställde upp det som ett problem 1893, och Tibor Gallai , som publicerade ett av de första bevisen för detta teorem 1944.

En linje som innehåller exakt två av en uppsättning punkter kallas en vanlig linje . Ett annat sätt att uttrycka satsen är att varje ändlig uppsättning punkter som inte är kolinjär har en vanlig linje. Enligt en förstärkning av satsen har varje finit punktmängd (inte alla på en linje) åtminstone ett linjärt antal vanliga linjer. En algoritm kan hitta en vanlig linje i en uppsättning av $n$ punkter i tiden $O(n\log n)$ .

Historia

Sylvester–Gallais sats ställdes som ett problem av JJ Sylvester ( 1893 ). Kelly ( 1986 ) antyder att Sylvester kan ha motiverats av ett relaterat fenomen inom algebraisk geometri , där böjningspunkterna för en kubisk kurva i det komplexa projektiva planet bildar en konfiguration av nio punkter och tolv linjer ( Hessen-konfigurationen ) där varje linje som bestäms av två av punkterna innehåller en tredje punkt. Sylvester–Gallais sats antyder att det är omöjligt för alla dessa nio punkter att ha riktiga koordinater.

HJ Woodall ( 1893a , 1893b ) hävdade att han hade ett kort bevis på Sylvester–Gallais sats, men det noterades redan vid publiceringstillfället att det var ofullständigt. Eberhard Melchior ( 1941 ) bevisade satsen (och faktiskt ett något starkare resultat) i en likvärdig formulering, dess projektiva dubbla . Omedveten om Melchiors bevis, Paul Erdős ( 1943 ) återigen gissningen, som senare bevisades av Tibor Gallai och strax därefter av andra författare.

I en recension från 1951 kallade Erdős resultatet för "Gallais sats", men det kallades redan Sylvester–Gallais sats i en recension 1954 av Leonard Blumenthal . Det är ett av många matematiska ämnen uppkallat efter Sylvester .

Motsvarande versioner

Frågan om förekomsten av en vanlig linje kan också ställas för punkter i det verkliga projektiva planet RP ² istället för det euklidiska planet . Det projektiva planet kan bildas från det euklidiska planet genom att lägga till extra punkter "i oändligheten" där linjer som är parallella i det euklidiska planet skär varandra, och genom att lägga till en enda linje "i oändligheten" som innehåller alla adderade punkter. De ytterligare punkterna i det projektiva planet kan dock inte hjälpa till att skapa icke-euklidiska ändliga punktuppsättningar utan någon vanlig linje, eftersom vilken ändlig punktuppsättning som helst i det projektiva planet kan omvandlas till en euklidisk punktuppsättning med samma kombinatoriska mönster av punktlinjeincidenser . Därför finns alla mönster av ändligt många skärande punkter och linjer som finns i en av dessa två typer av plan också i den andra. Icke desto mindre tillåter den projektiva synvinkeln att vissa konfigurationer lättare kan beskrivas. I synnerhet tillåter det användningen av projektiv dualitet , där rollerna för punkter och linjer i uttalanden om projektiv geometri kan bytas ut mot varandra. Under projektiv dualitet är förekomsten av en vanlig linje för en uppsättning icke-kollinjära punkter i RP ² ekvivalent med förekomsten av en vanlig punkt i ett icke-trivialt arrangemang av ändligt många linjer. Ett arrangemang sägs vara trivialt när alla dess linjer passerar genom en gemensam punkt, och icke-trivialt annars; en vanlig punkt är en punkt som hör till exakt två linjer.

Den avlånga dodekaedern , en zonohedron . Dess åtta röda parallellogramytor motsvarar vanliga punkter i ett femradigt arrangemang; en likvärdig form av Sylvester-Gallais sats säger att varje zonohedron har minst en parallellogramyta.

Arrangemang av linjer har en kombinatorisk struktur som är nära förbunden med zonoedrar , polyedrar som bildas som Minkowskisumman av en finit uppsättning linjesegment , kallade generatorer. I detta sammanhang motsvarar varje par av motstående ytor av en zonoeder en korsningspunkt för ett arrangemang av linjer i det projektiva planet, med en linje för varje generator. Antalet sidor på varje yta är dubbelt så många linjer som korsar i arrangemanget. Till exempel är den långsträckta dodekaedern som visas en zonoeder med fem generatorer, två par motsatta hexagonytor och fyra par motsatta parallellogramytor. I motsvarande femradiga arrangemang korsar två trippel av linjer (motsvarande de två paren av motsatta hexagoner) och de återstående fyra paren av linjer korsar vid vanliga punkter (motsvarande de fyra paren av motsatta parallellogram). Ett likvärdigt uttalande av Sylvester-Gallais sats, när det gäller zonohedrar, är att varje zonohedron har minst en parallellogramyta (räkna rektanglar, romber och kvadrater som speciella fall av parallellogram). Mer starkt, när uppsättningar av $n$ punkter i planet kan garanteras att ha minst $t_{2}(n)$ vanliga linjer, zonoedrar med $n$ generatorer kan garanteras ha minst $2t_{2}(n)$ parallogramsidor.

Bevis

Sylvester–Gallais sats har bevisats på många olika sätt. Gallais bevis från 1944 växlar fram och tillbaka mellan euklidisk och projektiv geometri, för att omvandla punkterna till en likvärdig konfiguration där en vanlig linje kan hittas som en lutningslinje närmast noll; för detaljer, se Borwein & Moser (1990) . Beviset från 1941 av Melchior använder projektiv dualitet för att omvandla problemet till en likvärdig fråga om arrangemang av linjer, som kan besvaras med Eulers polyedriska formel . Ett annat bevis av Leroy Milton Kelly visar motsägelsefullt att förbindelselinjen med det minsta avståndet från noll till en annan punkt måste vara vanlig. Och, efter ett tidigare bevis av Steinberg, HSM Coxeter att de metriska begreppen lutning och avstånd som förekommer i Gallais och Kellys bevis är onödigt kraftfulla, istället för att bevisa satsen med enbart axiomen för ordnad geometri .

Kellys bevis

Notation för Kellys bevis

Detta bevis är av Leroy Milton Kelly . Aigner & Ziegler (2018) kallar det "helt enkelt det bästa" av de många bevisen för detta teorem.

Antag att en ändlig uppsättning $S$ av punkter inte alla är kolinjär. Definiera en förbindelselinje som en linje som innehåller minst två punkter i samlingen. Genom ändlighet $S$ ha en punkt $P$ och en förbindelselinje $\ell$ som är ett positivt avstånd från varandra men är närmare än alla andra punktlinjepar. Kelly bevisade att $\ell$ är vanlig, motsägelsefullt .

Antag att $\ell$ inte är vanlig. Sedan går den igenom minst tre punkter av $S$ . Minst två av dessa är på samma sida av $P'$ , den vinkelräta projektionen av $P$ på $\ell$ . Kalla dem $B$ och $C$ , där $B$ är närmast $P'$ (och eventuellt sammanfaller med det). Rita förbindelselinjen $m$ som går genom $P$ och $C$ och vinkelrät från $B$ till $B'$ på $m$ . Då $BB'$ kortare än $PP'$ . Detta följer av det faktum att $PP'C$ och $BB'C$ är likartade trianglar, den ena innesluten i den andra.

Detta motsäger dock den ursprungliga definitionen av $P$ och $\ell$ som punktlinjeparet med det minsta positiva avståndet. Så antagandet att $\ell$ inte är vanligt kan inte vara sant, QED.

Melchiors bevis

År 1941 (alltså innan Erdős publicerade frågan och Gallais efterföljande bevis) visade Melchior att varje icke-trivialt ändligt arrangemang av linjer i det projektiva planet har minst tre vanliga punkter. Genom dualitet säger detta resultat också att varje ändlig icke-trivial uppsättning punkter på planet har minst tre vanliga linjer.

Melchior observerade att för varje graf som är inbäddad i det verkliga projektiva planet, måste formeln ${\displaystyle V-E+F} vara lika med$$1$ , Euler- karakteristiken för det projektiva planet. Här är $V$ , $E$ och $F$ antalet hörn, kanter och ytor på grafen. Varje icke-trivialt linjearrangemang på det projektiva planet definierar en graf i vilken varje yta begränsas av åtminstone tre kanter, och varje kant avgränsar två ytor; så dubbelräkning ger den ytterligare olikheten $F\leq 2E/3$ . Att använda denna olikhet för att eliminera $F$ från Euler-karakteristiken leder till olikheten $E\leq 3V-3$ . Men om varje vertex i arrangemanget var korsningspunkten för tre eller fler linjer, så skulle det totala antalet kanter vara minst $3V$ , vilket motsäger denna olikhet. Därför måste vissa hörn vara korsningspunkten för endast två linjer, och som Melchiors mer noggranna analys visar behövs minst tre vanliga hörn för att tillfredsställa olikheten E ≤ 3 V − 3 {\ $3 }$ .

Som Aigner & Ziegler (2018) noterar, gavs samma argument för existensen av en vanlig vertex 1944 av Norman Steenrod , som uttryckligen tillämpade det på problemet med dubbla vanliga linjer.

Melchiors ojämlikhet

Genom ett liknande argument kunde Melchior bevisa ett mer allmänt resultat. För varje $k\geq 2$ , låt $t_{k}$ vara antalet punkter till vilka $k$ -linjerna faller in. Sedan

$\displaystyle \sum _{k\geq 2}(k-3)t_{k}\leq -3.$

eller motsvarande,

$\displaystyle t_{2}\geqslant 3+\sum _{k\geq 4}(k-3)t_{k}.$

Axiomatik

HSM Coxeter ( 1948 , 1969 ) skriver om Kellys bevis på att dess användning av euklidiskt avstånd är onödigt kraftfullt, "som att använda en slägga för att knäcka en mandel". Istället gav Coxeter ytterligare ett bevis på Sylvester-Gallais sats inom beställd geometri , en axiomatisering av geometrin i termer av mellanrum som inkluderar inte bara euklidisk geometri utan flera andra relaterade geometrier. Coxeters bevis är en variant av ett tidigare bevis från Steinberg 1944. Problemet med att hitta en minimal uppsättning axiom som behövs för att bevisa satsen hör till omvänd matematik ; se Pambuccian (2009) för en studie av denna fråga.

Det vanliga uttalandet i Sylvester-Gallais teorem är inte giltigt i konstruktiv analys , eftersom det antyder den mindre begränsade principen om allvetenhet, en försvagad form av lagen om utesluten mitt som förkastas som ett axiom för konstruktiv matematik. Ändå är det möjligt att formulera en version av Sylvester–Gallais sats som är giltig inom konstruktiv analyss axiom, och att anpassa Kellys bevis för satsen till att vara ett giltigt bevis under dessa axiom.

Att hitta en vanlig linje

Kellys bevis på att det finns en vanlig linje kan omvandlas till en algoritm som hittar en vanlig linje genom att söka efter det närmaste paret av en punkt och en linje genom två andra punkter. Mukhopadhyay & Greene (2012) rapporterar tiden för den här närmaste parsökningen som ${\displaystyle O(n^{3})} ,$ baserat på en brute-force-sökning av alla trippelpunkter, men en algoritm att hitta den närmaste givna punkten till varje linje genom två givna punkter, i tiden ${\displaystyle O(n^{2})} ,$ gavs tidigare av Edelsbrunner & Guibas (1989) , som en subrutin för att hitta triangeln med minsta area bestäms av tre av en given uppsättning punkter. Samma artikel av Edelsbrunner & Guibas (1989) visar också hur man konstruerar det dubbla arrangemanget av linjer till de givna punkterna (som används i Melchior och Steenrods bevis) på samma gång, $O(n^ {2})$ , från vilken det är möjligt att identifiera alla vanliga hörn och alla vanliga linjer. Mukhopadhyay, Agrawal & Hosabettu (1997) visade först hur man hittar en enda vanlig linje (inte nödvändigtvis den från Kellys bevis) i tiden $O(n\log n)$ , och en enklare algoritm med samma tidsbundna beskrevs av Mukhopadhyay & Greene (2012) .

Algoritmen från Mukhopadhyay & Greene (2012) är baserad på Coxeters bevis med hjälp av ordnad geometri. Den utför följande steg:

1. Välj en punkt $p_{0}$ som är en vertex på det konvexa skrovet för de givna punkterna.
2. Konstruera en linje $\ell _{0}$ som går genom $p_{0}$ och annars stannar utanför det konvexa skrovet.
3. Sortera de andra givna punkterna efter vinkeln de skapar med $p_{0}$ , gruppera ihop punkter som bildar samma vinkel.
4. Om någon av punkterna är ensam i sin grupp, returnera den ordinarie linjen genom den punkten och $p_{0}$ .
5. För varje två på varandra följande grupper av punkter, i den sorterade sekvensen efter sina vinklar, bildar två linjer, som var och en går genom den närmaste punkten till $p_{0}$ i en grupp och den längsta punkten från $p_{0}$ i den andra gruppen.
6. För varje linje $\ell _{i}$ i uppsättningen linjer som bildas på detta sätt, hitta skärningspunkten för $\ell _{i}$ med $\ell _ {0}$
7. Returnera linjen $\ell _{i}$ vars skärningspunkt med $\ell _{0}$ är närmast $p_{0}$ .

Som författarna bevisar måste raden som returneras av denna algoritm vara vanlig. Beviset är antingen genom konstruktion om det returneras av steg 4, eller genom motsägelse om det returneras av steg 7: om raden som returnerades i steg 7 inte var vanlig, så bevisar författarna att det skulle finnas en vanlig linje mellan en av dess punkter och $p_{0}$ , men den här raden borde redan ha hittats och returnerats i steg 4.

Antalet vanliga rader

De två kända exemplen på punktuppsättningar med färre än $n/2$ vanliga linjer.

Medan Sylvester–Gallai-satsen säger att ett arrangemang av punkter, inte alla kolinjära, måste bestämma en vanlig linje, säger det inte hur många som måste bestämmas. Låt $t_{2}(n)$ vara det minsta antalet vanliga linjer som bestäms över varje uppsättning av $n$ icke-kollinjära punkter. Melchiors bevis visade att $t_{2}(n)\geq 3$ . de Bruijn och Erdős ( 1948) ställde frågan om $t_{2}(n)$ närmar sig oändligheten med $n$ . Theodore Motzkin ( 1951 ) bekräftade att det gör det genom att bevisa att $t_{2}(n)\geq {\sqrt {n}}$ . Gabriel Dirac ( 1951 ) antog att ${\displaystyle t_{2}\geq \lfloor n/2\rfloor } ,$ för alla värden på $n$ , en gissning som fortfarande står sig som från 2013. Detta kallas ofta Dirac-Motzkin-förmodan ; se till exempel Brass, Moser & Pach (2005 , s. 304). Kelly & Moser (1958) bevisade att $t_{2}(n)\geq 3n/7$ .

Exempel på Böröczkys (jämna) konfiguration med 10 punkter som bestämmer 5 vanliga linjer (figurens fem heldragna svarta linjer).

Diracs förmodade nedre gräns är asymptotiskt den bästa möjliga, eftersom de jämna talen $n$ större än fyra har en matchande övre gräns $t_{2}(n)\leq n /2$ . Konstruktionen, på grund av Károly Böröczky, som uppnår denna gräns består av hörn av en regelbunden $m$ -gon i det verkliga projektiva planet och ytterligare $m$ punkter (alltså ${\ displaystil n=2m}$ ) på linjen i oändligheten som motsvarar var och en av riktningarna som bestäms av par av hörn. Även om det finns $m(m-1)/2$ par av dessa punkter, bestämmer de endast $m$ distinkta riktningar. Detta arrangemang har bara $m$ vanliga linjer, linjerna som förbinder en vertex $v$ med punkten i oändligheten i linje med de två grannarna till $v$ . Som med alla ändliga konfigurationer i det verkliga projektiva planet, kan denna konstruktion störas så att alla punkter är ändliga, utan att ändra antalet vanliga linjer.

För udda $n$ är endast två exempel kända som matchar Diracs nedre gränsförmodan, det vill säga med $t_{2}(n)=( n-1)/2$ Ett exempel, av Kelly & Moser (1958) , består av hörn, kantmittpunkter och tyngdpunkt i en liksidig triangel; dessa sju punkter bestämmer bara tre vanliga linjer. Konfigurationen i vilken dessa tre vanliga linjer ersätts av en enda linje kan inte realiseras i det euklidiska planet, utan bildar ett ändligt projektivt utrymme känt som Fano-planet . På grund av denna koppling har Kelly–Moser-exemplet också kallats icke-Fano-konfigurationen. Det andra motexemplet, på grund av McKee, består av två regelbundna femhörningar sammanfogade kant-till-kant tillsammans med mittpunkten av den delade kanten och fyra punkter på linjen i oändligheten i det projektiva planet ; dessa 13 punkter har bland dem 6 ordinarie linjer. Modifieringar av Böröczkys konstruktion leder till uppsättningar med udda antal punkter med $3\lfloor n/4\rfloor$ vanliga linjer.

Csima & Sawyer (1993) bevisade att $t_{2}(n)\geq \lceil 6n/13\rceil$ förutom när $n$ är sju . Asymptotiskt $n/2$ denna formel redan $\approx 92,3\%}$ av den beprövade övre gränsen. Fallet $n=7$ är ett undantag eftersom Kelly–Moser-konstruktionen annars skulle vara ett motexempel; deras konstruktion visar att $t(7)\leq 3$ . Men om Csima–Sawyer-bindningen var giltig för $n=7$ skulle den hävda att $t_{2}(7)\geq 4$ .

Ett närbesläktat resultat är Becks teorem , som anger en avvägning mellan antalet linjer med få punkter och antalet punkter på en enda linje.

Ben Green och Terence Tao visade att för alla tillräckligt stora punktuppsättningar (det vill säga $n>n_{0}$ för ett lämpligt val av ${\displaystyle n_{0}} )$ , antalet vanliga linjer är verkligen minst $n/2$ . Dessutom, när $n$ är udda , är antalet vanliga linjer minst $3n/4-C$ , för någon konstant $C$ . Därmed är Böröczkys konstruktioner för jämnt och udda (diskuterat ovan) bäst möjliga. Att minimera antalet vanliga linjer är nära relaterat till fruktodlingsplanteringsproblemet att maximera antalet trepunktslinjer, vilket Green och Tao också löste för alla tillräckligt stora punktuppsättningar.

Antalet anslutande linjer

Huvudartikel: De Bruijn–Erdős teorem (incidensgeometri)

Som Paul Erdős observerade, innebär Sylvester–Gallais sats omedelbart att varje uppsättning av $n$ punkter som inte är kolinjära bestämmer åtminstone $n$ olika linjer. Detta resultat är känt som De Bruijn-Erdős teorem . Som basfall är resultatet tydligt sant för $n=3$ . För vilket som helst större värde på $n$ , kan resultatet reduceras från $n$ punkter till $n-1$ punkter, genom att ta bort en vanlig linje och en av de två punkterna på det (var noga med att inte ta bort en punkt för vilken den återstående delmängden skulle ligga på en enda linje). Således följer det av matematisk induktion. Exemplet med en nästan penna, en uppsättning av $n-1$ kolinjära punkter tillsammans med en ytterligare punkt som inte är på samma linje som de andra punkterna, visar att denna gräns är snäv.

Generaliseringar

Sylvester-Gallais sats har generaliserats till färgade punktuppsättningar i det euklidiska planet, och till system av punkter och linjer definierade algebraiskt eller av avstånd i ett metriskt utrymme . I allmänhet beaktar dessa variationer av satsen endast ändliga uppsättningar av punkter, för att undvika exempel som mängden av alla punkter i det euklidiska planet, som inte har en vanlig linje.

Färgade punkter

En variant av Sylvesters problem, som ställdes i mitten av 1960-talet av Ronald Graham och populariserades av Donald J. Newman , betraktar ändliga plana uppsättningar av punkter (inte alla på en linje) som ges två färger, och frågar om varje sådan uppsättning har en linje genom två eller flera punkter som alla har samma färg. På språket för mängder och familjer av mängder är ett ekvivalent uttalande att familjen av de kolinjära delmängderna av en finit punktmängd (inte alla på en linje) inte kan ha egenskap B . Ett bevis på denna variation tillkännagavs av Theodore Motzkin men publicerades aldrig; det första publicerade beviset var av Chakerian (1970) .

Icke verkliga koordinater

Hessen -konfigurationen , där linjen genom varje par av punkter innehåller en tredje punkt. Sylvester–Gallais sats visar att det inte kan realiseras med raka linjer i det euklidiska planet, men det har en realisering i det komplexa projektiva planet .

Precis som det euklidiska planet eller det projektiva planet kan definieras genom att använda reella tal för koordinaterna för deras punkter ( kartesiska koordinater för det euklidiska planet och homogena koordinater för det projektiva planet), kan analoga abstrakta system av punkter och linjer definieras genom att använda andra talsystem som koordinater. Sylvester-Gallais sats gäller inte för geometrier definierade på detta sätt över ändliga fält : för vissa ändliga geometrier definierade på detta sätt, såsom Fano-planet , har mängden av alla punkter i geometrin inga vanliga linjer.

Sylvester–Gallai-satsen gäller inte heller direkt för geometrier där punkter har koordinater som är par av komplexa tal eller kvaternioner , men dessa geometrier har mer komplicerade analoger till satsen. Till exempel, i det komplexa projektiva planet finns det en konfiguration av nio punkter, Hesses konfiguration (böjningspunkterna för en kubisk kurva), där varje linje är icke-ordinär, vilket bryter mot Sylvester-Gallais sats. En sådan konfiguration är känd som en Sylvester-Gallai-konfiguration , och den kan inte realiseras av punkter och linjer på det euklidiska planet. Ett annat sätt att uttrycka Sylvester-Gallai-satsen är att närhelst punkterna i en Sylvester-Gallai-konfiguration är inbäddade i ett euklidiskt utrymme, och bevarar kolineariteter, måste punkterna alla ligga på en enda linje, och exemplet med Hessen-konfigurationen visar att detta är falskt för det komplexa projektiva planet . Kelly (1986) bevisade dock en analog till Sylvester–Gallais sats: närhelst punkterna i en Sylvester–Gallai-konfiguration är inbäddade i ett komplext projektivt utrymme, måste alla punkterna ligga i ett tvådimensionellt delrum. På motsvarande sätt måste en uppsättning punkter i tredimensionellt komplext utrymme vars affina skrov är hela utrymmet ha en vanlig linje, och måste faktiskt ha ett linjärt antal vanliga linjer. På liknande sätt Elkies, Pretorius & Swanepoel (2006) att närhelst en Sylvester-Gallai-konfiguration är inbäddad i ett utrymme som definieras över kvartjonerna, måste dess punkter ligga i ett tredimensionellt delrum.

Matroider

Varje uppsättning punkter i det euklidiska planet, och linjerna som förbinder dem, kan abstraheras som element och plattor i en rank-3- orienterad matroid . Punkterna och linjerna av geometrier som definieras med andra talsystem än de reella talen bildar också matroider , men inte nödvändigtvis orienterade matroider. I detta sammanhang kan resultatet av Kelly & Moser (1958) att nedre gränsa antalet vanliga linjer generaliseras till orienterade matroider: varje rank-3 orienterad matroid med $n$ element har minst ${ \displaystyle 3n/7}$ tvåpunktslinjer, eller motsvarande varje rank-3 matroid med färre tvåpunktslinjer måste vara icke-orienterbara. En matroid utan några tvåpunktslinjer kallas en Sylvester-matroid . Relativt sett bildar Kelly-Moser-konfigurationen med sju punkter och endast tre vanliga linjer en av de förbjudna minderåriga för GF(4)-representerbara matroider .

Avståndsgeometri

En annan generalisering av Sylvester-Gallais sats till godtyckliga metriska utrymmen antogs av Chvátal (2004) och bevisades av Chen (2006) . I denna generalisering definieras en trippel av punkter i ett metriskt utrymme som kolinjär när triangelolikheten för dessa punkter är en likhet, och en linje definieras från vilket par av punkter som helst genom att upprepade gånger inkludera ytterligare punkter som är kolinjära med punkter som redan lagts till till linjen, tills inga fler sådana punkter kan läggas till. Generaliseringen av Chvátal och Chen säger att varje ändligt metriskt utrymme har en linje som innehåller antingen alla punkter eller exakt två av punkterna.

Anteckningar

•   Aigner, Martin ; Ziegler, Günter M. (2018), "Chapter 11. Lines in the plane and decomposition of graphs", Proofs from THE BOOK (6th ed.), Springer, Theorem 1, s. 77–78, doi : 10.1007/978- 3-662-57265-8_11 , ISBN 978-3-662-57265-8
•    Basit, Abdul; Dvir, Zeev; Saraf, Shubhangi; Wolf, Charles (2019), "Om antalet vanliga linjer bestämt av mängder i komplext rum", Discrete & Computational Geometry , 61 (4): 778–808, arXiv : 1611.08740 , doi : 10.1007/s00454-39 4 , MR 3943495 , S2CID 125616042
•    Beck, József (1983), "Om planets galleregenskaper och några problem hos Dirac, Motzkin och Erdős i kombinatorisk geometri", Combinatorica , 3 (3–4): 281–297, doi : 10.1007/ BF02579184 , 0729781 , S2CID 31011939
•    Björner, Anders ; Las Vergnas, Michel ; Sturmfels, Bernd ; White, Neil; Ziegler, Günter M. (1993), Oriented matroids , Encyclopedia of Mathematics and its Applications, vol. 46, Cambridge: Cambridge University Press, sid. 273 , ISBN 0-521-41836-4 , MR 1226888
•   Borwein, P .; Moser, WOJ (1990) , "A survey of Sylvester's problem and its generalizations", Aequationes Mathematicae , 40 (1): 111–135, doi : 10.1007/BF02112289 , MR 1069788 , S20526172  
•   Brass, Peter; Moser, William; Pach, János (2005), Forskningsproblem i diskret geometri , Berlin: Springer, ISBN 0-387-23815-8
•   de Bruijn, NG ; Erdős, P. (1948), "A combinatioral [sic] problem" (PDF) , Indagationes Mathematicae , 10 : 421–423, MR 0028289
•    Chakerian, GD (1970), "Sylvesters problem on collinear points and a relative", American Mathematical Monthly , 77 (2): 164–167, doi : 10.2307/2317330 , JSTOR 2317330 , MR 0258659
•   Chen, Xiaomin (2006), "The Sylvester–Chvátal theorem", Discrete & Computational Geometry , 35 (2): 193–199, doi : 10.1007/s00454-005-1216-9 , MR 2195050
•   Chvátal, Vašek (2004), "Sylvester–Gallai theorem and metric betweenness", Discrete & Computational Geometry , 31 (2): 175–195, doi : 10.1007/s00454-003-0795-6 , MR 40600
•    Coxeter, HSM (1948), "A problem of collinear points", American Mathematical Monthly , 55 (1): 26–28, doi : 10.2307/2305324 , JSTOR 2305324 , MR 0024137
•   Coxeter, HSM (1969), "12.3 Sylvester's problem of collinear points", Introduction to Geometry (2nd ed.), New York: John Wiley & Sons, s. 181–182, ISBN 0-471-50458-0
•    Crowe, DW; McKee, TA (1968), "Sylvesters problem on collinear points", Mathematics Magazine , 41 (1): 30–34, doi : 10.2307/2687957 , JSTOR 2687957 , MR 0235452
•   Csima, J.; Sawyer, E. (1993), "Det finns $6n/13$ vanliga punkter", Discrete & Computational Geometry , 9 : 187–202, doi : 10.1007/BF02189318 , MR 3 619400
•   Dirac, G. (1951), "Collinearity properties of sets of points", Quarterly Journal of Mathematics , 2 : 221–227, Bibcode : 1951QJMat...2..221D , doi : 10.1093/qmath/2.1.221 , . 0043485
•   Edelsbrunner, Herbert ; Guibas, Leonidas J. (1989), "Topologically sweeping an arrangement", Journal of Computer and System Sciences , 38 (1): 165–194, doi : 10.1016/0022-0000(89)90038-X , MR 0990055
•    Elkies, Noam ; Pretorius, Lou M.; Swanepoel, Konrad J. (2006), "Sylvester–Gallai-satser för komplexa tal och kvaternioner", Discrete & Computational Geometry , 35 (3): 361–373, arXiv : math/0403023 , doi : 10.05074/s. -7 , MR 2202107 , S2CID 1647360
•   Erdős, P. (1943), "Problem 4065", Problem för lösning: 4065–4069, American Mathematical Monthly , 50 (1): 65–66, doi : 10.2307/2304011 , JSTOR 2304011
•    Erdős, P. (1982), "Personliga minnen och anmärkningar om Tibor Gallais matematiska arbete" ( PDF ) , Combinatorica , 2 (3): 207–212, doi : 10.1007/BF02579228 , 62579228 , 62CID 306 9, 62579228 , 62579229
•   Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), "The excluded minors for GF(4)-representable matroids" (PDF) , Journal of Combinatorial Theory , Series B, 79 (2): 247–299, doi : 10.1006/jctb.2000.1963 , MR 1769191 , arkiverad från originalet (PDF) 2010-09-24
•    Grön, Ben ; Tao, Terence (2013), "On sets defining few ordinary lines", Discrete & Computational Geometry , 50 (2): 409–468, arXiv : 1208.4714 , doi : 10.1007/s00454-013-905 , SID 3-013-905 , 5C 905 , 5C 15813230
•   Grünbaum, Branko (1999), "Monokromatiska skärningspunkter i familjer av färgade linjer" (PDF) , Geombinatorics , 9 (1): 3–9, MR 1698297
•   Kelly, LM (1986), "A resolution of the Sylvester–Gallai problem of JP Serre", Discrete and Computational Geometry , 1 (2): 101–104, doi : 10.1007/BF02187687 , MR 0834051
•    Kelly, LM ; Moser, WOJ (1958), "On the number of ordinary lines determined by $n$ points", Canadian Journal of Mathematics , 10 : 210–219, doi : 10.4153/CJM-1958-024-6 , MR 409701 , S2CID 123865536
•   Mandelkern, Mark (2016), "A constructive version of the Sylvester–Gallai theorem", Acta Mathematica Hungarica , 150 : 121–130, doi : 10.1007/s10474-016-0624 - z , MR 35420C 9354204C35420ID9  
• Melchior, E. (1941), "Über Vielseite der Projektive Ebene", Deutsche Mathematik , 5 : 461–475
•    Motzkin, Th. (1951), "The lines and planes connecting the points of a finite set", Transactions of the American Mathematical Society , 70 (3): 451–464, doi : 10.2307/1990609 , JSTOR 1990609 , MR 0041447
•   Mukhopadhyay, A.; Agrawal, A.; Hosabettu, RM (1997), "On the ordinary line problem in computational geometry", Nordic Journal of Computing , 4 (4): 330–341, MR 1607014
•   Mukhopadhyay, Asish; Greene, Eugene (2012), "The ordinary line problem revisited", Computational Geometry: Theory and Applications , 45 (3): 127–130, doi : 10.1016/j.comgeo.2011.10.003 , MR 2853475
• Pach, János ; Sharir, Micha (2009), "Kapitel 1. Sylvester–Gallai Problem: The Beginnings of Combinatorial Geometry", Combinatorial Geometry and its Algorithmic Applications: The Alcalá Lectures , Mathematical Surveys and Monographs, vol. 152, American Mathematical Society , s. 1–12
•   Pambuccian, Victor (2009), "A reverse analysis of the Sylvester–Gallai theorem" , Notre Dame Journal of Formal Logic , 50 (3): 245–260, doi : 10.1215/00294527-2009-010 , MR 35725
•     Shephard, GC (1968), "Twenty problems on convex polyhedra, part I", The Mathematical Gazette , 52 (380): 136–156, doi : 10.2307/3612678 , JSTOR 3612678 , MR 023124721 02312472 023124721 02312472
•   Steinberg, R.; Buck, RC; Grünwald, T. ; Steenrod, NE (1944), "Three point collinearity (solution to problem 4065)", American Mathematical Monthly , 51 (3): 169–171, doi : 10.2307/2303021 , JSTOR 2303021
• Sylvester, JJ (1893), "Matematisk fråga 11851", The Educational Times , 46 (383): 156
• Woodall, HJ (1893a), "Matematisk fråga 11851 besvarad", The Educational Times , 46 (385): 231
• Woodall, HJ (1893b), "Matematisk fråga 11851 besvarad" , Mathematical Questions and Solutions from the Educational Times , 59 : 98

externa länkar

• Malkevitch, Joseph (2003), "A discrete geometrical gem" , AMS Feature Column , American Mathematical Society , arkiverad från originalet 2006-10-10
• Weisstein, Eric W. , "Ordinary Line" , MathWorld
• Bevispresentation av Terence Tao vid 2013 års Minerva-föreläsningar