Teorema de Sylvester-Could

Sylvester–Gallai theorem Three of the ordinary lines in a 4 × 4 grid of points The Sylvester–Gallai theorem in geometry states that every finite set of points in the Euclidean plane has a line that passes through exactly two of the points or a line that passes through all of them. É nomeado após James Joseph Sylvester, que colocou isso como um problema em 1893, e Tibor Gallai, que publicou uma das primeiras provas deste teorema em 1944.

Uma linha que contém exatamente dois de um conjunto de pontos é conhecida como uma linha comum. Outra maneira de enunciar o teorema é que todo conjunto finito de pontos que não é colinear tem uma linha comum. De acordo com um reforço do teorema, todo conjunto de pontos finitos (nem tudo em uma linha) tem pelo menos um número linear de linhas comuns. Um algoritmo pode encontrar uma linha comum em um conjunto de {estilo de exibição m} pontos no tempo {estilo de exibição O(aluguel m)} .

Conteúdo 1 História 2 Versões equivalentes 3 Provas 3.1 A prova de Kelly 3.2 A prova de Melchior 3.2.1 Desigualdade de Melchior 3.3 Axiomática 4 Encontrando uma linha comum 5 O número de linhas comuns 6 O número de linhas de conexão 7 Generalizações 7.1 Pontos coloridos 7.2 Coordenadas não reais 7.3 Matróides 7.4 Geometria de distância 8 Notas 9 Referências 10 External links History The Sylvester–Gallai theorem was posed as a problem by J. J. Silvestre (1893). Kelly (1986) sugere que Sylvester pode ter sido motivado por um fenômeno relacionado na geometria algébrica, em que os pontos de inflexão de uma curva cúbica no plano projetivo complexo formam uma configuração de nove pontos e doze linhas (a configuração de Hesse) em que cada linha determinada por dois dos pontos contém um terceiro ponto. O teorema de Sylvester-Gallai implica que é impossível que todos esses nove pontos tenham coordenadas reais.[1] H. J. Woodall (1893uma, 1893b) afirmou ter uma prova curta do teorema de Sylvester-Gallai, mas já foi notado estar incompleto no momento da publicação. Eberhard Melchior (1941) provou o teorema (e na verdade um resultado um pouco mais forte) em uma formulação equivalente, sua dupla projetiva. Desconhecendo a prova de Melchior,[2] Paul Erdős (1943) novamente afirmou a conjectura, que foi posteriormente provado por Tibor Gallai, e logo depois por outros autores.[3] Em um 1951 Reveja, Erdős chamou o resultado "Teorema de Could",[4] mas já foi chamado de teorema de Sylvester-Gallai em uma 1954 Revisão por Leonard Blumenthal.[5] É um dos muitos tópicos matemáticos com o nome de Sylvester.

Equivalent versions The question of the existence of an ordinary line can also be posed for points in the real projective plane RP2 instead of the Euclidean plane. O plano projetivo pode ser formado a partir do plano euclidiano adicionando pontos extras "no infinito" onde as linhas que são paralelas no plano euclidiano se cruzam, e adicionando uma única linha "no infinito" contendo todos os pontos adicionados. No entanto, os pontos adicionais do plano projetivo não podem ajudar a criar conjuntos de pontos finitos não euclidianos sem linha comum, como qualquer ponto finito definido no plano projetivo pode ser transformado em um ponto euclidiano com o mesmo padrão combinatório de incidências ponto-linha. Portanto, qualquer padrão de um número finito de pontos e linhas de interseção que existe em um desses dois tipos de plano também existe no outro. No entanto, o ponto de vista projetivo permite que certas configurações sejam descritas mais facilmente. Em particular, permite o uso da dualidade projetiva, em que os papéis de pontos e linhas em declarações de geometria projetiva podem ser trocados um pelo outro. Sob dualidade projetiva, a existência de uma linha comum para um conjunto de pontos não colineares em RP2 é equivalente à existência de um ponto comum em um arranjo não trivial de um número finito de linhas. Um arranjo é dito trivial quando todas as suas linhas passam por um ponto comum, e não trivial de outra forma; um ponto comum é um ponto que pertence a exatamente duas linhas.[2] O dodecaedro alongado, um zonedro. Suas oito faces vermelhas do paralelogramo correspondem a pontos comuns de um arranjo de cinco linhas; uma forma equivalente do teorema de Sylvester-Gallai afirma que todo zonoedro tem pelo menos uma face de paralelogramo.

Arranjos de linhas têm uma estrutura combinatória intimamente ligada ao zonoedro, poliedros formados como a soma de Minkowski de um conjunto finito de segmentos de linha, chamados geradores. Nessa conexão, cada par de faces opostas de um zonoedro corresponde a um ponto de cruzamento de um arranjo de linhas no plano projetivo, com uma linha para cada gerador. O número de lados de cada face é o dobro do número de linhas que se cruzam no arranjo. Por exemplo, o dodecaedro alongado mostrado é um zonoedro com cinco geradores, dois pares de faces hexagonais opostas, e quatro pares de faces paralelas opostas do paralelogramo. No arranjo de cinco linhas correspondente, dois triplos de linhas se cruzam (correspondente aos dois pares de hexágonos opostos) e os quatro pares de linhas restantes se cruzam em pontos comuns (correspondente aos quatro pares de paralelogramos opostos). Uma declaração equivalente do teorema de Sylvester-Gallai, em termos de zonoedra, é que todo zonoedro tem pelo menos uma face de paralelogramo (contando retângulos, losangos, e quadrados como casos especiais de paralelogramos). Mais fortemente, sempre que conjuntos de {estilo de exibição m} pontos no plano podem ter pelo menos {estilo de exibição t_{2}(n)} linhas comuns, zonoedra com {estilo de exibição m} geradores podem ser garantidos para ter pelo menos {estilo de exibição 2t_{2}(n)} rostos de paralelogramo.[6] Proofs The Sylvester–Gallai theorem has been proved in many different ways. Poderia 1944 prova alterna entre geometria euclidiana e projetiva, a fim de transformar os pontos em uma configuração equivalente em que uma linha comum pode ser encontrada como uma linha de inclinação mais próxima de zero; para detalhes, see Borwein & Moser (1990). o 1941 prova de Melchior usa dualidade projetiva para converter o problema em uma questão equivalente sobre arranjos de linhas, que pode ser respondida usando a fórmula poliédrica de Euler. Outra prova de Leroy Milton Kelly mostra por contradição que a linha de conexão com a menor distância diferente de zero a outro ponto deve ser comum. E, seguindo uma prova anterior de Steinberg, H. S. M. Coxeter mostrou que os conceitos métricos de inclinação e distância que aparecem nas provas de Gallai e Kelly são desnecessariamente poderosos, em vez disso, provando o teorema usando apenas os axiomas da geometria ordenada.

Kelly's proof Notation for Kelly's proof This proof is by Leroy Milton Kelly. Aigner & Ziegler (2018) chame-o "simplesmente o melhor" das muitas provas deste teorema.[7] Suponha que um conjunto finito {estilo de exibição S} de pontos não é tudo colinear. Defina uma linha de conexão como uma linha que contém pelo menos dois pontos na coleção. Por finitude, {estilo de exibição S} deve ter um ponto {estilo de exibição P} e uma linha de ligação {ell de estilo de exibição } que estão a uma distância positiva, mas estão mais próximos do que todos os outros pares de ponto-linha. Kelly provou que {ell de estilo de exibição } é comum, por contradição.[7] Assuma isso {ell de estilo de exibição } não é comum. Em seguida, ele passa por pelo menos três pontos de {estilo de exibição S} . Pelo menos dois deles estão do mesmo lado {estilo de exibição P'} , a projeção perpendicular de {estilo de exibição P} sobre {ell de estilo de exibição } . Chame-os {estilo de exibição B} e {estilo de exibição C} , com {estilo de exibição B} estar mais próximo de {estilo de exibição P'} (e possivelmente coincidindo com ele). Desenhe a linha de conexão {estilo de exibição m} passando através {estilo de exibição P} e {estilo de exibição C} , e a perpendicular de {estilo de exibição B} para {estilo de exibição B'} sobre {estilo de exibição m} . Então {estilo de exibição BB'} é mais curto do que {estilo de exibição PP'} . Isso decorre do fato de que {estilo de exibição PP'C} e {estilo de exibição BB'C} são triângulos semelhantes, um contido dentro do outro.[7] No entanto, isso contradiz a definição original de {estilo de exibição P} e {ell de estilo de exibição } como o par ponto-linha com a menor distância positiva. Então a suposição de que {ell de estilo de exibição } não é comum não pode ser verdade, É[7] Melchior's proof In 1941 (portanto, antes de Erdős publicar a pergunta e a prova subsequente de Gallai) Melchior mostrou que qualquer arranjo finito não trivial de linhas no plano projetivo tem pelo menos três pontos ordinários. Por dualidade, este resultado também diz que qualquer conjunto finito não trivial de pontos no plano tem pelo menos três linhas comuns.[8] Melchior observou que, para qualquer gráfico embutido no plano projetivo real, a fórmula {estilo de exibição V-E+F} deve ser igual {estilo de exibição 1} , a característica de Euler do plano projetivo. Aqui {estilo de exibição V} , {estilo de exibição E} , e {estilo de exibição F} são o número de vértices, arestas, e faces do gráfico, respectivamente. Qualquer arranjo de linhas não trivial no plano projetivo define um grafo no qual cada face é limitada por pelo menos três arestas., e cada aresta limita duas faces; assim, contagem dupla dá a desigualdade adicional {estilo de exibição Fleq 2E/3} . Usando esta desigualdade para eliminar {estilo de exibição F} da característica de Euler leva à desigualdade {exibir Eleq 3V-3} . Mas se cada vértice no arranjo fosse o ponto de cruzamento de três ou mais linhas, então o número total de arestas seria pelo menos {exibição 3V} , contrariando essa desigualdade. Portanto, alguns vértices devem ser o ponto de cruzamento de apenas duas linhas, e como mostra a análise mais cuidadosa de Melchior, pelo menos três vértices ordinários são necessários para satisfazer a desigualdade {exibir Eleq 3V-3} .[8] As Aigner & Ziegler (2018) Nota, o mesmo argumento para a existência de um vértice ordinário também foi dado em 1944 por Norman Steenrod, que o aplicou explicitamente ao problema da linha ordinária dupla.[9] Melchior's inequality By a similar argument, Melchior conseguiu provar um resultado mais geral. Para cada {estilo de exibição kgeq 2} , deixar {estilo de exibição t_{k}} ser o número de pontos para os quais {estilo de exibição k} as linhas são incidentes. Então[8] {soma de estilo de exibição de exibição _{kgeq 2}(k-3)t_{k}leq -3.} ou equivalente, {estilo de exibição estilo de exibição t_{2}geqslant 3+soma _{kgeq 4}(k-3)t_{k}.} Axiomatics H. S. M. Coxeter (1948, 1969) escreve sobre a prova de Kelly de que seu uso da distância euclidiana é desnecessariamente poderoso, "como usar uma marreta para quebrar uma amêndoa". Em vez de, Coxeter deu outra prova do teorema de Sylvester-Gallai dentro da geometria ordenada, uma axiomatização da geometria em termos de intermediação que inclui não apenas a geometria euclidiana, mas várias outras geometrias relacionadas.[10] A prova de Coxeter é uma variação de uma prova anterior dada por Steinberg em 1944.[11] O problema de encontrar um conjunto mínimo de axiomas necessários para provar o teorema pertence à matemática reversa; veja Pambuciano (2009) para um estudo desta questão.

A afirmação usual do teorema de Sylvester-Gallai não é válida na análise construtiva, pois implica o princípio menos limitado da onisciência, uma forma enfraquecida da lei do terceiro excluído que é rejeitada como um axioma da matemática construtiva. No entanto, é possível formular uma versão do teorema de Sylvester–Gallai que seja válida dentro dos axiomas da análise construtiva, e adaptar a prova do teorema de Kelly para ser uma prova válida sob esses axiomas.[12] Finding an ordinary line 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. Mukhopadhyay & Greene (2012) relatar o tempo para esta pesquisa de par mais próximo como {estilo de exibição O(n^{3})} , baseado em uma busca de força bruta de todos os triplos de pontos, mas um algoritmo para encontrar o ponto dado mais próximo de cada linha através de dois pontos dados, em tempo {estilo de exibição O(n^{2})} , was given earlier by Edelsbrunner & Guibas (1989), como uma sub-rotina para encontrar o triângulo de área mínima determinado por três de um determinado conjunto de pontos. The same paper of Edelsbrunner & Guibas (1989) também mostra como construir o arranjo dual de linhas para os pontos dados (como usado na prova de Melchior e Steenrod) ao mesmo tempo, {estilo de exibição O(n^{2})} , a partir do qual é possível identificar todos os vértices comuns e todas as linhas comuns. Mukhopadhyay, Agrawal & Hosabettu (1997) mostrou pela primeira vez como encontrar uma única linha comum (não necessariamente o da prova de Kelly) em tempo {estilo de exibição O(aluguel m)} , and a simpler algorithm with the same time bound was described by Mukhopadhyay & Greene (2012).

The algorithm of Mukhopadhyay & Greene (2012) é baseado na prova de Coxeter usando geometria ordenada. Ele executa os seguintes passos: Escolha um ponto {estilo de exibição p_{0}} que é um vértice do casco convexo dos pontos dados. Construir uma linha {estilo de exibição ell _{0}} que passa por {estilo de exibição p_{0}} e de outra forma fica fora do casco convexo. Ordene os outros pontos dados pelo ângulo que eles fazem com {estilo de exibição p_{0}} , agrupar pontos que formam o mesmo ângulo. Se algum dos pontos estiver sozinho em seu grupo, em seguida, retorne a linha comum por esse ponto e {estilo de exibição p_{0}} . Para cada dois grupos consecutivos de pontos, na sequência ordenada por seus ângulos, formar duas linhas, cada um dos quais passa pelo ponto mais próximo de {estilo de exibição p_{0}} em um grupo e o ponto mais distante de {estilo de exibição p_{0}} no outro grupo. Para cada linha {estilo de exibição ell _{eu}} no conjunto de linhas assim formadas, encontre o ponto de interseção de {estilo de exibição ell _{eu}} com {estilo de exibição ell _{0}} Devolva a linha {estilo de exibição ell _{eu}} cujo ponto de intersecção com {estilo de exibição ell _{0}} é o mais próximo de {estilo de exibição p_{0}} .

Como os autores provam, a linha retornada por este algoritmo deve ser comum. A prova é por construção se for retornada por passo 4, ou por contradição se for retornado por passo 7: se a linha retornou na etapa 7 não eram comuns, então os autores provam que existiria uma linha comum entre um de seus pontos e {estilo de exibição p_{0}} , mas esta linha já deve ter sido encontrada e retornada na etapa 4.[13] O número de linhas comuns Os dois exemplos conhecidos de conjuntos de pontos com menos de {estilo de exibição n/2} linhas comuns.

Enquanto o teorema de Sylvester-Gallai afirma que um arranjo de pontos, nem todos colineares, deve determinar uma linha comum, não diz quantos devem ser determinados. Deixar {estilo de exibição t_{2}(n)} ser o número mínimo de linhas ordinárias determinado sobre cada conjunto de {estilo de exibição m} pontos não colineares. A prova de Melchior mostrou que {estilo de exibição t_{2}(n)geq 3} . de Bruijn and Erdős (1948) levantou a questão de saber se {estilo de exibição t_{2}(n)} aproxima-se do infinito com {estilo de exibição m} . Theodore Motzkin (1951) confirmou que sim, provando que {estilo de exibição t_{2}(n)geq {quadrado {n}}} . Gabriel Dirac (1951) conjecturou que {estilo de exibição t_{2}geq lfloor n/2rfloor } , para todos os valores de {estilo de exibição m} , uma conjectura que ainda se mantém 2013. Isso é muitas vezes referido como a conjectura de Dirac-Motzkin; veja por exemplo Latão, Moser & Pach (2005, p. 304). Kelly & Moser (1958) provou que {estilo de exibição t_{2}(n)geq 3n/7} .

Exemplo de Böröczky (até) configuração com 10 pontos determinantes 5 linhas comuns (as cinco linhas pretas sólidas da figura).

O limite inferior conjecturado de Dirac é assintoticamente o melhor possível, como os números pares {estilo de exibição m} maior que quatro têm um limite superior correspondente {estilo de exibição t_{2}(n)leq n/2} . A construção, devido a Károly Böröczky, que atinge este limite consiste nos vértices de uma regular {estilo de exibição m} -ido no plano projetivo real e outro {estilo de exibição m} pontos (portanto, {estilo de exibição n=2m} ) na linha no infinito correspondente a cada uma das direções determinadas por pares de vértices. Apesar de haver {estilo de exibição m(m-1)/2} pares desses pontos, eles determinam apenas {estilo de exibição m} direções distintas. Este arranjo tem apenas {estilo de exibição m} linhas comuns, as linhas que ligam um vértice {estilo de exibição v} com o ponto no infinito colinear com os dois vizinhos de {estilo de exibição v} . Como em qualquer configuração finita no plano projetivo real, esta construção pode ser perturbada para que todos os pontos sejam finitos, sem alterar o número de linhas comuns.[14] Para ímpar {estilo de exibição m} , apenas dois exemplos são conhecidos que correspondem à conjectura do limite inferior de Dirac, isso é, com {estilo de exibição t_{2}(n)=(n-1)/2} Um exemplo, by Kelly & Moser (1958), consiste nos vértices, pontos médios da borda, e baricentro de um triângulo equilátero; esses sete pontos determinam apenas três linhas comuns. A configuração em que essas três linhas comuns são substituídas por uma única linha não pode ser realizada no plano euclidiano, mas forma um espaço projetivo finito conhecido como plano de Fano. Por causa desta ligação, o exemplo Kelly–Moser também foi chamado de configuração não Fano.[15] O outro contra-exemplo, devido a McKee,[14] consiste em dois pentágonos regulares unidos de ponta a ponta juntamente com o ponto médio da aresta compartilhada e quatro pontos na linha no infinito no plano projetivo; esses 13 pontos tem entre eles 6 linhas comuns. Modificações da construção de Böröczky levam a conjuntos de números ímpares de pontos com {displaystyle 3lfloor n/4rfloor } linhas comuns.[16] Csima & Sawyer (1993) provou que {estilo de exibição t_{2}(n)Geq lceil 6n/13rceil } exceto quando {estilo de exibição m} é sete. Assintoticamente, essa fórmula já {estilo de exibição 12/13 aprox 92.3%} do comprovado {estilo de exibição n/2} limite superior. o {estilo de exibição n=7} caso é uma exceção porque, caso contrário, a construção Kelly-Moser seria um contra-exemplo; sua construção mostra que {estilo de exibição t(7)leq 3} . No entanto, a ligação Csima-Sawyer era válida para {estilo de exibição n=7} , iria alegar que {estilo de exibição t_{2}(7)geq 4} .

Um resultado intimamente relacionado é o teorema de Beck, estabelecendo uma compensação entre o número de linhas com poucos pontos e o número de pontos em uma única linha.[17] Ben Green e Terence Tao mostraram que para todos os conjuntos de pontos suficientemente grandes (isso é, {displaystyle n>n_{0}} para alguma escolha adequada de {estilo de exibição n_{0}} ), o número de linhas comuns é de fato pelo menos {estilo de exibição n/2} . Além disso, quando {estilo de exibição m} é estranho, o número de linhas ordinárias é pelo menos {estilo de exibição 3n/4-C} , para alguma constante {estilo de exibição C} . Desta forma, as construções de Böröczky para pares e ímpares (discutido acima) são os melhores possíveis. Minimizar o número de linhas comuns está intimamente relacionado ao problema de plantio de pomares de maximizar o número de linhas de três pontos, que Green e Tao também resolveram para todos os conjuntos de pontos suficientemente grandes.[18] O número de linhas de conexão Ver artigo principal: Teorema de De Bruijn–Erdős (geometria de incidência) Como Paul Erdős observou, o teorema de Sylvester-Gallai imediatamente implica que qualquer conjunto de {estilo de exibição m} pontos que não são colineares determina pelo menos {estilo de exibição m} linhas diferentes. Este resultado é conhecido como o teorema de De Bruijn-Erdős. Como caso básico, o resultado é claramente verdadeiro para {estilo de exibição n=3} . Para qualquer valor maior de {estilo de exibição m} , o resultado pode ser reduzido de {estilo de exibição m} aponta para {estilo de exibição n-1} pontos, excluindo uma linha comum e um dos dois pontos nela (tomando cuidado para não excluir um ponto para o qual o subconjunto restante estaria em uma única linha). Desta forma, segue por indução matemática. O exemplo de um quase-lápis, um conjunto de {estilo de exibição n-1} pontos colineares juntamente com um ponto adicional que não está na mesma linha que os outros pontos, mostra que este limite é apertado.[16] Generalizations The Sylvester–Gallai theorem has been generalized to colored point sets in the Euclidean plane, e a sistemas de pontos e linhas definidos algebricamente ou por distâncias em um espaço métrico. No geral, essas variações do teorema consideram apenas conjuntos finitos de pontos, para evitar exemplos como o conjunto de todos os pontos no plano euclidiano, que não tem uma linha comum.

Colored points A variation of Sylvester's problem, posada em meados da década de 1960 por Ronald Graham e popularizada por Donald J. Novo homem, considera conjuntos planos finitos de pontos (nem tudo em uma linha) que recebem duas cores, e pergunta se cada conjunto tem uma linha através de dois ou mais pontos que são todos da mesma cor. Na linguagem de conjuntos e famílias de conjuntos, uma afirmação equivalente é que a família dos subconjuntos colineares de um conjunto de pontos finitos (nem tudo em uma linha) não pode ter Propriedade B. Uma prova dessa variação foi anunciada por Theodore Motzkin, mas nunca publicada; a primeira prova publicada foi por Chakerian (1970).[19] Coordenadas não reais A configuração de Hesse, em que a linha através de cada par de pontos contém um terceiro ponto. O teorema de Sylvester-Gallai mostra que não pode ser realizado por linhas retas no plano euclidiano, mas tem uma realização no plano projetivo complexo.

Assim como o plano euclidiano ou plano projetivo pode ser definido usando números reais para as coordenadas de seus pontos (Coordenadas cartesianas para o plano euclidiano e coordenadas homogêneas para o plano projetivo), sistemas abstratos análogos de pontos e linhas podem ser definidos usando outros sistemas numéricos como coordenadas. O teorema de Sylvester-Gallai não vale para geometrias definidas desta forma sobre corpos finitos: para algumas geometrias finitas definidas desta forma, como o avião Fano, o conjunto de todos os pontos na geometria não possui linhas comuns.[7] O teorema de Sylvester-Gallai também não se aplica diretamente a geometrias em que os pontos têm coordenadas que são pares de números complexos ou quatérnios, mas essas geometrias têm análogos mais complicados do teorema. Por exemplo, no plano projetivo complexo existe uma configuração de nove pontos, configuração de Hesse (os pontos de inflexão de uma curva cúbica), em que cada linha não é comum, violando o teorema de Sylvester-Gallai. Essa configuração é conhecida como configuração de Sylvester-Gallai, e não pode ser realizado por pontos e linhas do plano euclidiano. Outra maneira de enunciar o teorema de Sylvester-Gallai é que sempre que os pontos de uma configuração de Sylvester-Gallai são incorporados em um espaço euclidiano, preservando colinearidades, os pontos devem estar todos em uma única linha, e o exemplo da configuração de Hesse mostra que isso é falso para o plano projetivo complexo. No entanto, Kelly (1986) provou um análogo de número complexo do teorema de Sylvester-Gallai: sempre que os pontos de uma configuração Sylvester-Gallai são incorporados em um espaço projetivo complexo, os pontos devem estar todos em um subespaço bidimensional. Equivalentemente, um conjunto de pontos no espaço complexo tridimensional cuja casca afim é todo o espaço deve ter uma linha comum, e de fato deve ter um número linear de linhas comuns.[20] De forma similar, Elkies, Pretorius & Swanepoel (2006) mostrou que sempre que uma configuração de Sylvester-Gallai é inserida em um espaço definido sobre os quatérnions, seus pontos devem estar em um subespaço tridimensional.

Matroids Every set of points in the Euclidean plane, e as linhas que os ligam, pode ser abstraído como os elementos e planos de um matróide orientado de rank 3. Os pontos e linhas de geometrias definidas usando outros sistemas numéricos que os números reais também formam matróides, mas não necessariamente matróides orientados. Nesse contexto, the result of Kelly & Moser (1958) limitando o número de linhas comuns pode ser generalizado para matróides orientados: cada matróide orientado de nível 3 com {estilo de exibição m} elementos tem pelo menos {estilo de exibição 3n/7} linhas de dois pontos, ou equivalentemente, cada matróide de nível 3 com menos linhas de dois pontos deve ser não orientável.[21] Um matróide sem linhas de dois pontos é chamado de matróide Sylvester. Relacionado, a configuração Kelly-Moser com sete pontos e apenas três linhas ordinárias forma um dos menores proibidos para GF(4)-matróides representáveis.[15] Distance geometry Another generalization of the Sylvester–Gallai theorem to arbitrary metric spaces was conjectured by Chvátal (2004) e provado por Chen (2006). Nesta generalização, um triplo de pontos em um espaço métrico é definido como colinear quando a desigualdade triangular para esses pontos é uma igualdade, e uma linha é definida a partir de qualquer par de pontos incluindo repetidamente pontos adicionais que são colineares com pontos já adicionados à linha, até que nenhum mais desses pontos possa ser adicionado. A generalização de Chvátal e Chen afirma que todo espaço métrico finito tem uma linha que contém todos os pontos ou exatamente dois dos pontos.[22] Notas ^ Elkies, Pretorius & Swanepoel (2006). ^ Saltar para: a b Borwein & Moser (1990). ^ Steinberg e outros. (1944); Floresta (1982). ^ MR0041447 ^ MR0056941 ^ Shephard (1968). ^ Saltar para: a b c d e Aigner & Ziegler (2018). ^ Saltar para: a b c Melchior (1941). ^ Aigner & Ziegler (2018, p. 92); A prova de Steenrod foi resumida em Steinberg et al.. (1944). ^ Aigner & Ziegler (2018); pambucciano (2009). ^ Coxeter (1948); pambucciano (2009). Para a prova de Steinberg ver Steinberg et al. (1944). ^ Núcleo de amêndoa (2016). ^ Mukhopadhyay & Greene (2012). ^ Saltar para: a b Crowe & McKee (1968). ^ Saltar para: a b Geelen, Gerards & Kapoor (2000). ^ Saltar para: a b Pach & Sharir (2009) ^ Beck (1983). ^ Green & Tao (2013). ^ Para a história desta variação do problema, ver também Grünbaum (1999) ^ Basit e outros. (2019). ^ Björner et al. (1993). ^ Ele atirou (2004); Chen (2006); pambucciano (2009) Referências Aigner, Martinho; Ziegler, Gunter M. (2018), "Capítulo 11. Linhas no plano e decomposição de gráficos", Provas do LIVRO (6ª edição), Springer, Teorema 1, pp. 77-78, doi:10.1007/978-3-662-57265-8_11, ISBN 978-3-662-57265-8 Basit, Abdul; Dvir, Zeev; Nervos, Shubhangi; Lobo, Carlos (2019), "Sobre o número de linhas ordinárias determinadas por conjuntos no espaço complexo", Discrete & Computational Geometry, 61 (4): 778-808, arXiv:1611.08740, doi:10.1007/s00454-018-0039-4, MR 3943495, S2CID 125616042 Beck, Joseph (1983), "Sobre a propriedade de rede do plano e alguns problemas de Dirac, Motzkin, e Erdős em geometria combinatória", Combinatória, 3 (3-4): 281-297, doi:10.1007/BF02579184, MR 0729781, S2CID 31011939 Björner, Anders; Os Vergnas, Michel; rocha de tempestade, Bernd; Branco, Neil; Ziegler, Gunter M. (1993), Matróides orientados, Enciclopédia de Matemática e suas Aplicações, volume. 46, Cambridge: Cambridge University Press, p. 273, ISBN 0-521-41836-4, MR 1226888 Borwein, P.; Moser, C. O. J. (1990), "Um levantamento do problema de Sylvester e suas generalizações", Equações matemáticas, 40 (1): 111-135, doi:10.1007/BF02112289, MR 1069788, S2CID 122052678 Brass, Peter; Moser, William; O cheiro, John (2005), Problemas de pesquisa em geometria discreta, Berlim: Springer, ISBN 0-387-23815-8 de Bruijn, N. G.; Floresta, P. (1948), "Uma combinação [sic] problema" (PDF), Investigações matemáticas, 10: 421-423, MR 0028289 Chakerian, G. D. (1970), "O problema de Sylvester em pontos colineares e um relativo", Mensal de Matemática Americana, 77 (2): 164-167, doi:10.2307/2317330, JSTOR 2317330, MR 0258659 Chen, Xiaomin (2006), "O Sylvester-Ele pegou o teorema", Discrete & Computational Geometry, 35 (2): 193-199, doi:10.1007/s00454-005-1216-9, MR 2195050 Ele estava agarrando, Vasek (2004), "Teorema de Sylvester-Gallai e intermediação métrica", Discrete & Computational Geometry, 31 (2): 175-195, doi:10.1007/s00454-003-0795-6, MR 2060634 Coxeter, H. S. M. (1948), "Um problema de pontos colineares", Mensal de Matemática Americana, 55 (1): 26-28, doi:10.2307/2305324, JSTOR 2305324, MR 0024137 Coxeter, H. S. M. (1969), "12.3 O problema de pontos colineares de Sylvester", Introdução à Geometria (2ª edição), Nova york: John Wiley & Sons, pp. 181–182, ISBN 0-471-50458-0 Crowe, D. C.; McKee, T. UMA. (1968), "O problema de Sylvester em pontos colineares", Revista Matemática, 41 (1): 30-34, doi:10.2307/2687957, JSTOR 2687957, MR 0235452 Csima, J.; Serrador, E. (1993), "Existe {estilo de exibição 6n/13} pontos comuns", Discrete & Computational Geometry, 9: 187-202, doi:10.1007/BF02189318, MR 1194036 Dirac, G. (1951), "Propriedades de colinearidade de conjuntos de pontos", Revista Trimestral de Matemática, 2: 221-227, Bibcode:1951QJMat...2..221D, doi:10.1093/qmath/2.1.221, MR 0043485 Edelsbrunner, Herbert; Guibas, Leônidas J. (1989), "Varrendo topologicamente um arranjo", Revista de Ciências da Computação e Sistemas, 38 (1): 165-194, doi:10.1016/0022-0000(89)90038-X, MR 0990055 Elkies, Noam; Pretorius, Lou M.; Swanepoel, Konrad J. (2006), "Teoremas de Sylvester-Gallai para números complexos e quatérnios", Discrete & Computational Geometry, 35 (3): 361-373, arXiv:matemática/0403023, doi:10.1007/s00454-005-1226-7, MR 2202107, S2CID 1647360 Floresta, P. (1943), "Problema 4065", Problemas para solução: 4065–4069, Mensal de Matemática Americana, 50 (1): 65-66, doi:10.2307/2304011, JSTOR 2304011 Floresta, P. (1982), "Reminiscências pessoais e observações sobre o trabalho matemático de Tibor Gallai" (PDF), Combinatória, 2 (3): 207-212, doi:10.1007/BF02579228, MR 0698647, S2CID 1135308 Geelen, J. F.; Geraldos, UMA. M. H.; Kapoor, UMA. (2000), "Os menores excluídos para GF(4)-matróides representáveis" (PDF), Jornal de Teoria Combinatória, Série B, 79 (2): 247-299, doi:10.1006/jctb.2000.1963, MR 1769191, arquivado a partir do original (PDF) sobre 2010-09-24 Verde, Ben; Tao, Terêncio (2013), "Em conjuntos definindo poucas linhas comuns", Discrete & Computational Geometry, 50 (2): 409-468, arXiv:1208.4714, doi:10.1007/s00454-013-9518-9, MR 3090525, S2CID 15813230 Grünbaum, Branko (1999), "Pontos de interseção monocromáticos em famílias de linhas coloridas" (PDF), Geombinatória, 9 (1): 3-9, MR 1698297 Kelly, eu. M. (1986), "Uma resolução do problema Sylvester-Gallai de J. P. Apertado", Geometria Discreta e Computacional, 1 (2): 101-104, doi:10.1007/BF02187687, MR 0834051 Kelly, eu. M.; Moser, C. O. J. (1958), "Sobre o número de linhas ordinárias determinado por {estilo de exibição m} pontos", Revista Canadense de Matemática, 10: 210-219, doi:10.4153/CJM-1958-024-6, MR 0097014, S2CID 123865536 Mandelkern, Marca (2016), "Uma versão construtiva do teorema de Sylvester-Gallai", Revista Matemática Húngara, 150: 121-130, doi:10.1007/s10474-016-0624-z, MR 3542040, S2CID 124023963 Melchior, E. (1941), "Sobre a Versatilidade do Plano Projetivo", matemática alemã, 5: 461–475 Motzkin, º. (1951), "As linhas e planos que ligam os pontos de um conjunto finito", Transações da American Mathematical Society, 70 (3): 451-464, doi:10.2307/1990609, JSTOR 1990609, MR 0041447 Mukhopadhyay, UMA.; Agrawal, UMA.; Hosabetto, R. M. (1997), "Sobre o problema da linha comum em geometria computacional", Revista Nórdica de Computação, 4 (4): 330-341, MR 1607014 Mukhopadhyay, , coisas; Greene, Eugênio (2012), "O problema da linha comum revisitado", Geometria Computacional: Teoria e aplicações, 45 (3): 127-130, doi:10.1016/j.comgeo.2011.10.003, MR 2853475 O cheiro, John; Sharir, Miquéias (2009), "Capítulo 1. Sylvester-Pode ser um problema: Os primórdios da geometria combinatória", Geometria Combinatória e Suas Aplicações Algorítmicas: As Palestras de Alcalá, Pesquisas e Monografias Matemáticas, volume. 152, Sociedade Americana de Matemática, pp. 1–12 Pambuccian, Vencedor (2009), "Uma análise reversa do teorema de Sylvester-Gallai", Notre Dame Journal of Formal Logic, 50 (3): 245-260, doi:10.1215/00294527-2009-010, MR 2572973 Shephard, G. C. (1968), "Vinte problemas em poliedros convexos, parte I", A Gazeta Matemática, 52 (380): 136-156, doi:10.2307/3612678, JSTOR 3612678, MR 0231278 Steinberg, R.; bode, R. C.; Floresta verde, T.; Steenrod, N. E. (1944), "Colinearidade de três pontos (solução para problema 4065)", Mensal de Matemática Americana, 51 (3): 169-171, doi:10.2307/2303021, JSTOR 2303021 Silvestre, J. J. (1893), "Questão de matemática 11851", Os tempos educacionais, 46 (383): 156 Woodall, H. J. (1893uma), "Questão de matemática 11851 respondidas", Os tempos educacionais, 46 (385): 231 Woodall, H. J. (1893b), "Questão de matemática 11851 respondidas", Questões matemáticas e soluções dos tempos educacionais, 59: 98 Links externos Malkevitch, Joseph (2003), "Uma jóia geométrica discreta", Coluna de recursos AMS, Sociedade Americana de Matemática, arquivado a partir do original em 2006-10-10 Weisstein, Eric W., "Linha comum", Apresentação MathWorld Proof por Terence Tao no 2013 Minerva Lectures hide vte Incidence structures Representation Incidence matrixIncidence graph Fields Combinatorics Block designSteiner systemGeometry IncidenceProjective planeGraph theory HypergraphStatistics Blocking Configurations Complete quadrangleFano planeMöbius–Kantor configurationPappus configurationHesse configurationDesargues configurationReye configurationSchläfli double sixCremona–Richmond configurationKummer configurationGrünbaum–Rigby configurationKlein configurationDual Theorems Sylvester–Gallai theoremDe Bruijn–Erdős theoremSzemerédi–Trotter theoremBeck's theoremBruck–Ryser–Chowla theorem Applications Design of experimentsKirkman's schoolgirl problem Categories: Geometria do plano euclidianoTeoremas em geometria discretaMatroid theory