Теорема Сильвестра – Галлаи в геометрии утверждает, что каждый конечный набор точек на евклидовой плоскости имеет прямую, проходящую ровно через две точки, или прямую, проходящую через все они. Он назван в честь Джеймса Джозефа Сильвестра , который поставил эту задачу как проблему в 1893 году, и Тибора Галлая , опубликовавшего одно из первых доказательств этой теоремы в 1944 году.
Линия, содержащая ровно две точки из набора, называется обычной линией . Согласно усилению теоремы, каждое конечное множество точек (не все на одной прямой) имеет по крайней мере линейное количество обычных прямых. Алгоритм может найти обычную строку в наборе моменты времени .
История
Теорема Сильвестра – Галлаи была поставлена как проблема Дж. Дж. Сильвестром ( 1893 г. ). Келли ( 1986 ) полагает , что Сильвестер может быть мотивирован родственномом явлением в алгебраической геометрии , в котором точка перегиба на виде кубической кривой в комплексной проективной плоскости образует конфигурацию из девяти точек и двенадцати линий ( конфигурации Гесса ) , в котором каждый Линия, определяемая двумя точками, содержит третью точку. Из теоремы Сильвестра – Галла следует, что все девять точек не могут иметь действительные координаты. [1]
Woodall (1893) ошибка harvtxt: несколько целей (2 ×): CITEREF Woodall1893 ( помощь ) утверждал, что у него есть краткое доказательство теоремы Сильвестра – Галлаи, но на момент публикации оно уже было отмечено как неполное. Эберхард Мельхиор ( 1941 ) доказал теорему (и на самом деле немного более сильный результат) в эквивалентной формулировке, ее проективно двойственной . Не зная о доказательстве Мельхиора [2] Пол Эрдеш ( 1943 ) снова высказал гипотезу, которая впоследствии была доказана Тибором Галлаи , а вскоре и другими авторами. [3]
В обзоре 1951 года Эрдеш назвал результат «теоремой Галлаи» [4], но он уже был назван теоремой Сильвестра – Галлаи в обзоре 1954 года Леонарда Блюменталя . [5] Это одна из многих математических тем, названных в честь Сильвестра .
Эквивалентные версии
Вопрос о существовании обыкновенной прямой также может быть поставлен для точек реальной проективной плоскости RP 2 вместо евклидовой плоскости . Проективная плоскость может быть образована из евклидовой плоскости путем добавления дополнительных точек «на бесконечности», где прямые, параллельные в евклидовой плоскости, пересекаются друг с другом, и путем добавления единственной линии «на бесконечности», содержащей все добавленные точки. Однако дополнительные точки проективной плоскости не могут помочь создать неевклидовы конечные наборы точек без обычной линии, поскольку любой конечный набор точек в проективной плоскости может быть преобразован в набор евклидовых точек с тем же комбинаторным шаблоном инцидентностей точечных линий. . Следовательно, любой образец конечного числа пересекающихся точек и линий, который существует в одном из этих двух типов плоскости, также существует в другом. Тем не менее, проективная точка зрения позволяет легче описывать определенные конфигурации. В частности, это позволяет использовать проективную двойственность , в которой роли точек и линий в утверждениях проективной геометрии могут быть заменены друг на друга. При проективной двойственности существование обычной прямой для набора неколлинеарных точек в RP 2 эквивалентно существованию обычной точки в нетривиальном расположении конечного числа прямых. Расположение называется тривиальным, если все его прямые проходят через общую точку, и нетривиальным в противном случае; обычная точка - это точка, которая принадлежит ровно двум прямым. [2]
Расположение прямых имеет комбинаторную структуру, тесно связанную с зоноэдрами , многогранниками, образованными как сумма Минковского конечного набора отрезков прямых , называемых образующими. В связи с этим каждая пара противоположных граней зоноэдра соответствует точке пересечения расположения прямых в проективной плоскости, с одной линией для каждой образующей. Количество сторон каждой грани в два раза превышает количество пересекающихся линий. Например, показанный удлиненный додекаэдр представляет собой зоноэдр с пятью образующими, двумя парами противоположных граней шестиугольника и четырьмя парами противоположных граней параллелограмма. В соответствующем расположении из пяти линий две тройки линий пересекаются (соответствующие двум парам противоположных шестиугольников), а остальные четыре пары линий пересекаются в обычных точках (соответствующих четырем парам противоположных параллелограммов). Эквивалентное утверждение теоремы Сильвестра – Галла в терминах зоноэдров состоит в том, что каждый зоноэдр имеет по крайней мере одну грань параллелограмма (прямоугольники, ромбы и квадраты считаются частными случаями параллелограммов). Более того, когда наборы точки на плоскости могут гарантированно иметь не менее обыкновенные линии, зоноэдры с генераторы могут иметь не менее паралограммы лиц. [6]
Доказательства
Теорема Сильвестра – Галлаи доказывалась множеством различных способов. Доказательство Галлая 1944 года переключается между евклидовой и проективной геометрией, чтобы преобразовать точки в эквивалентную конфигурацию, в которой обычная линия может быть найдена как линия наклона, ближайшая к нулю; подробнее см. Borwein & Moser (1990) . Доказательство Мельхиора 1941 года использует проективную двойственность, чтобы преобразовать проблему в эквивалентный вопрос о расположении линий, на который можно ответить, используя формулу полиэдра Эйлера . Другое доказательство Лероя Милтона Келли показывает от противного, что соединительная линия с наименьшим ненулевым расстоянием до другой точки должна быть обычной. И, следуя более раннему доказательству Стейнберга, HSM Coxeter показал, что метрические концепции наклона и расстояния, появляющиеся в доказательствах Галлаи и Келли, излишне мощны, вместо этого доказывая теорему, используя только аксиомы упорядоченной геометрии .
Доказательство Келли
Это доказательство принадлежит Лерою Милтону Келли . Айгнер и Зиглер (2018) называют его «просто лучшим» из многих доказательств этой теоремы. [7]
Предположим, что конечное множество точек не все коллинеарны. Определите соединительную линию как линию, содержащую как минимум две точки в коллекции. По конечности, должен иметь точку и соединительная линия которые находятся на положительном расстоянии друг от друга, но ближе, чем все другие пары точек-линий. Келли доказала, чтообыкновенно, от противного . [7]
Предположить, что не обычный. Затем проходит не менее трех точек. По крайней мере два из них находятся на одной стороне, перпендикулярная проекция на . Позвони им а также , с участием быть ближе всего к (и, возможно, совпадающий с ним). Проведите соединительную линию проходя через а также , а перпендикуляр из к на . потом короче чем . Это следует из того, что а также являются подобные треугольники , один содержится внутри другого. [7]
Однако это противоречит первоначальному определению а также как пара точка-линия с наименьшим положительным расстоянием. Итак, предположение, чтоНеобычно не может быть правдой, КЭД. [7]
Доказательство Мельхиора
В 1941 году (таким образом, до публикации вопроса Эрдешом и последующего доказательства Галлаи) Мельхиор показал, что любое нетривиальное конечное расположение прямых на проективной плоскости имеет по крайней мере три обычные точки. По двойственности этот результат также говорит о том, что любое конечное нетривиальное множество точек на плоскости имеет не менее трех обычных прямых. [8]
Мельхиор заметил, что для любого графа, вложенного в действительную проективную плоскость, формула должен равняться , эйлерова характеристика проективной плоскости. Здесь, , а также - количество вершин, ребер и граней графа соответственно. Любое нетривиальное расположение прямых на проективной плоскости определяет граф, в котором каждая грань ограничена по крайней мере тремя ребрами, а каждое ребро ограничивает две грани; Итак, двойной счет дает дополнительное неравенство. Используя это неравенство для исключения из эйлеровой характеристики приводит к неравенству . Но если бы каждая вершина в расположении была точкой пересечения трех или более линий, то общее количество ребер было бы не менее, что противоречит этому неравенству. Следовательно, некоторые вершины должны быть точкой пересечения только двух прямых, и, как показывает более тщательный анализ Мельхиора, необходимы как минимум три обычные вершины, чтобы удовлетворять неравенству. [8]
Как отмечают Айгнер и Зиглер (2018) , тот же аргумент в пользу существования обычной вершины был также приведен в 1944 году Норманом Стинродом , который явно применил его к двойственной задаче с обыкновенной прямой. [9]
Неравенство Мельхиора
С помощью аналогичного аргумента Мельхиор смог доказать более общий результат. Для каждого, позволять быть количеством точек, к которым линии инцидентны. Тогда [8]
или эквивалентно,
Аксиоматика
HSM Coxeter ( 1948 , 1969 ) пишет о доказательстве Келли, что использование им евклидова расстояния излишне мощно, «как использование кувалды, чтобы расколоть миндаль». Вместо этого Кокстер дал другое доказательство теоремы Сильвестра – Галлаи в рамках упорядоченной геометрии , аксиоматизацию геометрии с точки зрения промежуточности, которая включает не только евклидову геометрию, но и несколько других связанных геометрий. [10] Доказательство Кокстера является вариацией более раннего доказательства, данного Стейнбергом в 1944 году. [11] Проблема поиска минимального набора аксиом, необходимого для доказательства теоремы, принадлежит обратной математике ; см. Pambuccian (2009) для изучения этого вопроса.
Обычное утверждение теоремы Сильвестра – Галлаи неприменимо для конструктивного анализа , поскольку оно подразумевает менее ограниченный принцип всеведения , ослабленную форму закона исключенного третьего, который отвергается как аксиома конструктивной математики. Тем не менее, можно сформулировать версию теоремы Сильвестра – Галлаи, которая справедлива в рамках аксиом конструктивного анализа, и адаптировать доказательство теоремы Келли, чтобы оно было достоверным доказательством при этих аксиомах. [12]
Нахождение обычной линии
Доказательство Келли существования обычной линии можно превратить в алгоритм, который находит обычную линию путем поиска ближайшей пары точки и линии через две другие точки. Mukhopadhyay & Greene (2012) сообщают о времени для поиска ближайших пар следующим образом:, основанный на переборе всех троек точек, но алгоритм для поиска ближайшей заданной точки к каждой линии через две заданные точки во времени, была дана ранее Эдельсбруннером и Гибасом (1989) как подпрограмма для поиска треугольника минимальной площади, определяемого тремя точками из заданного набора. В той же статье Эдельсбруннера и Гибаса (1989) также показано, как построить двойное расположение прямых к заданным точкам (как используется в доказательстве Мельхиора и Стинрода) за одно и то же время,, из которого можно выделить все обычные вершины и все обычные прямые. Mukhopadhyay, Agrawal & Hosabettu (1997) впервые показали, как найти одну обычную строку (не обязательно из доказательства Келли) во времени., а более простой алгоритм с той же временной границей был описан Mukhopadhyay & Greene (2012) .
Алгоритм Mukhopadhyay & Greene (2012) основан на доказательстве Кокстера с использованием упорядоченной геометрии. Он выполняет следующие шаги:
- Выберите точку что является вершиной из выпуклой оболочки из заданных точек.
- Построить линию что проходит через и в противном случае остается вне выпуклой оболочки.
- Отсортируйте остальные заданные точки по углу, который они образуют. , объединяя точки, образующие один угол.
- Если какая-либо из точек одна в своей группе, верните обычную линию через эту точку и .
- Для каждых двух последовательных групп точек в отсортированной по углам последовательности образуют две линии, каждая из которых проходит через ближайшую к в одной группе и в самой дальней точке от в другой группе.
- Для каждой строки в образованном таким образом наборе прямых найти точку пересечения с участием
- Верните линию чья точка пересечения с ближе всего к .
Как доказывают авторы, строка, возвращаемая этим алгоритмом, должна быть обычной. Доказательство осуществляется либо путем построения, если оно возвращается на шаге 4, либо путем противоречия, если оно возвращается на шаге 7: если строка, возвращенная на шаге 7, не была обычной, то авторы доказывают, что между одним из них могла бы существовать обычная линия. его точки и, но эта строка уже должна была быть найдена и возвращена на шаге 4. [13]
Количество обычных линий
Хотя теорема Сильвестра – Галлаи утверждает, что расположение точек, не все коллинеарные, должно определять обычную линию, она не говорит, сколько точек должно быть определено. Позволять быть минимальным количеством обычных линий, определенным для каждого набора неколлинеарные точки. Доказательство Мельхиора показало, что. де Брюйн и Эрдеш ( 1948 ) подняли вопрос о том, можно ли приближается к бесконечности с . Теодор Моцкин ( 1951 ) подтвердил это, доказав, что. Габриэль Дирак ( 1951 ) предположил, что, для всех значений , предположение, которое остается в силе по состоянию на 2013 год.[Обновить]. Это часто называют гипотезой Дирака – Моцкина ; см., например, Brass, Moser & Pach (2005 , с. 304). Келли и Мозер (1958) доказали, что.
Предполагаемая нижняя граница Дирака является асимптотически наилучшей возможной, поскольку четные числа больше четырех имеют совпадающую верхнюю границу . Конструкция Кароли Бёрёчки , которая достигает этой оценки, состоит из вершин правильного-угольник в реальной проективной плоскости и другой очков (таким образом, ) на бесконечно удаленной прямой, соответствующей каждому из направлений, определяемых парами вершин. Хотя есть пары этих точек, они определяют только четкие направления. В этом расположении есть только обычные линии, линии, соединяющие вершину с бесконечно удаленной точкой, коллинеарной с двумя соседями . Как и в случае любой конечной конфигурации на реальной проективной плоскости, эту конструкцию можно изменить так, чтобы все точки были конечными, без изменения количества обычных прямых. [14]
Для нечетных известны только два примера, которые соответствуют гипотезе Дирака о нижней оценке, то есть с Один из примеров, предложенный Келли и Мозером (1958) , состоит из вершин, средних точек ребер и центроида равностороннего треугольника; эти семь точек определяют только три обычные линии. Конфигурация , в которой эти три простые линии заменены одной линии не может быть реализован в евклидовой плоскости, но образует конечное проективное пространство , известное как плоскости Фано . Из-за этой связи пример Келли – Мозера также называют конфигурацией нефано. [15] Другой контрпример, принадлежащий Макки, [14] состоит из двух правильных пятиугольников, соединенных ребром к ребру вместе со средней точкой общего ребра, и четырьмя точками на бесконечно удаленной прямой в проективной плоскости ; эти 13 точек имеют среди них 6 обычных линий. Модификации конструкции Бёрёчки приводят к наборам нечетного числа точек собычные линии. [16]
Csima & Sawyer (1993) доказали, что кроме тех случаев, когда семь. Асимптотически эта формула уже проверенных верхняя граница. Вслучай является исключением, поскольку в противном случае конструкция Келли – Мозера была бы контрпримером; их конструкция показывает, что. Однако действительна ли граница Чима – Сойера для, он будет утверждать, что .
Близким результатом является теорема Бека , устанавливающая компромисс между количеством линий с несколькими точками и количеством точек на одной линии. [17]
Бен Грин и Теренс Тао показали, что для всех достаточно больших точечных множеств (т. Е. для некоторого подходящего выбора ) число обычных линий действительно не менее . Кроме того, когдаэто нечетное число обычных линий, по крайней мере, для некоторой постоянной . Таким образом, конструкции Бёрёчки для четных и нечетных чисел (обсуждаемые выше) являются наилучшими из возможных. Минимизация количества обычных линий тесно связана с проблемой садоводства по максимизации количества трехточечных линий, которую Грин и Тао также решили для всех достаточно больших наборов точек. [18]
Количество соединительных линий
Как заметил Пол Эрдеш , из теоремы Сильвестра – Галла сразу следует, что любой набор точки, которые не являются коллинеарными, определяет по крайней мере разные линии. Этот результат известен как теорема Де Брейна – Эрдеша . В качестве базового случая результат явно верен для. Для любого большего значения, результат можно уменьшить с указывает на точек, удалив обычную линию и одну из двух точек на ней (стараясь не удалить точку, для которой оставшееся подмножество будет лежать на одной линии). Таким образом, следует по математической индукции. Пример почти карандаша, набораколлинеарные точки вместе с одной дополнительной точкой, которая не находится на той же линии, что и другие точки, показывает, что эта граница жесткая. [16]
Обобщения
Теорема Сильвестра – Галла была обобщена на цветные точечные множества на евклидовой плоскости, а также на системы точек и прямых, определенные алгебраически или расстояниями в метрическом пространстве . В общем, эти варианты теоремы рассматривают только конечные наборы точек, чтобы избежать таких примеров, как набор всех точек на евклидовой плоскости, который не имеет обычной линии.
Цветные точки
Вариант задачи Сильвестра, поставленный в середине 1960-х годов Рональдом Грэхэмом и популяризированный Дональдом Дж. Ньюманом , рассматривает конечные плоские множества точек (не все в линию), которым присвоены два цвета, и спрашивает, имеет ли каждый такой набор проведите линию через две или более точек одного цвета. На языке множеств и семейства множеств , эквивалентное утверждение о том , что семейство коллинеарных подмножеств конечного множества точек (не все на одной линии) не может иметь свойство Б . Доказательство этой вариации было объявлено Теодором Моцкиным, но так и не опубликовано; первое опубликованное доказательство было Чакерианом (1970) . [19]
Неверные координаты
Подобно тому, как евклидова плоскость или проективная плоскость могут быть определены с использованием вещественных чисел для координат их точек ( декартовы координаты для евклидовой плоскости и однородные координаты для проективной плоскости), аналогичные абстрактные системы точек и линий могут быть определены с использованием других системы счисления как координаты. Теорема Сильвестра – Галла не верна для геометрий, определенных таким образом над конечными полями : для некоторых конечных геометрий, определенных таким образом, таких как плоскость Фано , множество всех точек в геометрии не имеет обычных линий. [7]
Теорема Сильвестра – Галла также не применяется напрямую к геометриям, в которых точки имеют координаты, которые являются парами комплексных чисел или кватернионов , но эти геометрии имеют более сложные аналоги теоремы. Например, в комплексной проективной плоскости существует конфигурация из девяти точек, конфигурация Гессе (точки перегиба кубической кривой), в которой каждая прямая необычна, что нарушает теорему Сильвестра – Галлаи. Такая конфигурация известна как конфигурация Сильвестра – Галлаи , и она не может быть реализована точками и линиями евклидовой плоскости. Другой способ сформулировать теорему Сильвестра – Галлаи состоит в том, что всякий раз, когда точки конфигурации Сильвестра – Галла вкладываются в евклидово пространство с сохранением коллинеарности, все точки должны лежать на одной прямой, и пример конфигурации Гессе показывает, что это неверно для комплексной проективной плоскости . Однако Келли (1986) доказал аналог теоремы Сильвестра – Галлаи для комплексных чисел: всякий раз, когда точки конфигурации Сильвестра – Галлаи вложены в комплексное проективное пространство, все точки должны лежать в двумерном подпространстве. Эквивалентно, набор точек в трехмерном комплексном пространстве, чья аффинная оболочка представляет собой все пространство, должен иметь обычную линию и фактически должен иметь линейное количество обычных линий. [20] Аналогичным образом, Элкис, Преториус и Свейнпол (2006) показали, что всякий раз, когда конфигурация Сильвестра – Галлаи вкладывается в пространство, определенное над кватернионами, ее точки должны лежать в трехмерном подпространстве.
Матроиды
Каждый набор точек на евклидовой плоскости и линии, соединяющие их, могут быть абстрагированы как элементы и плоскости ориентированного матроида ранга 3 . Точки и линии геометрии, определенные с использованием других систем счисления, чем действительные числа, также образуют матроиды , но не обязательно ориентированные матроиды. В этом контексте результат Келли и Мозера (1958) об оценке снизу числа обычных линий может быть обобщен на ориентированные матроиды: каждый ориентированный матроид ранга 3 с элементов имеет как минимум двухточечные прямые или, что то же самое, любой матроид ранга 3 с меньшим количеством двухточечных прямых должен быть неориентируемым. [21] Матроид без двухточечных прямых называется матроидом Сильвестра . Соответственно, конфигурация Келли – Мозера с семью точками и только тремя обычными линиями образует один из запрещенных миноров для GF (4) -представимых матроидов . [15]
Геометрия расстояния
Другое обобщение теоремы Сильвестра – Галлаи на произвольные метрические пространства было высказано Хваталем (2004) и доказано Ченом (2006) . В этом обобщении тройка точек в метрическом пространстве определяется как коллинеарная, когда неравенство треугольника для этих точек является равенством, а линия определяется из любой пары точек путем повторного включения дополнительных точек, которые коллинеарны с уже добавленными точками. на линию, пока больше не удастся добавить такие точки. Обобщение Хватала и Чена утверждает, что каждое конечное метрическое пространство имеет прямую, содержащую либо все точки, либо ровно две точки. [22]
Заметки
- ^ Elkies, Преториус и Свейнпол (2006) .
- ^ а б Borwein & Moser (1990) .
- ^ Steinberg et al. (1944) ; Эрдеш (1982) .
- ^ MR 0041447
- ^ MR0056941
- ^ Шепард (1968) .
- ^ а б в г д Aigner & Ziegler (2018) .
- ^ a b c Мельхиор (1941) .
- ↑ Aigner & Ziegler (2018 , p. 92); Доказательство Стинрода было кратко изложено в Steinberg et al. (1944) .
- ^ Aigner & Ziegler (2018) ; Памбуччиан (2009) .
- ^ Кокстер (1948) ; Памбуччиан (2009) . Для доказательства Стейнберга см. Steinberg et al. (1944) .
- ^ Манделькерна (2016) .
- ^ Mukhopadhyay & Greene (2012) .
- ^ а б Кроу и Макки (1968) .
- ^ a b Гилен, Джерардс и Капур (2000) .
- ^ a b Пах и Шарир (2009)
- ^ Бек (1983) .
- Перейти ↑ Green & Tao (2013) .
- ^ Историю этого варианта задачи см. Также Grünbaum (1999).
- ^ Basit et al. (2019) .
- ^ Björner et al. (1993) .
- ^ Chvátal (2004) ; Чен (2006) ; Pambuccian (2009)
Рекомендации
- Айгнер, Мартин ; Зиглер, Гюнтер М. (2018), «Глава 11. Прямые на плоскости и разложение графов», Доказательства из КНИГИ (6-е изд.), Springer, теорема 1, стр. 77–78, doi : 10.1007 / 978- 3-662-57265-8_11 , ISBN 978-3-662-57265-8
- Басит, Абдул; Двир, Зеев; Сараф, Шубханги; Вольф, Чарльз (2019), «О количестве обычных линий, определяемых множествами в комплексном пространстве», Дискретная и вычислительная геометрия , 61 (4): 778–808, arXiv : 1611.08740 , doi : 10.1007 / s00454-018-0039- 4 , Руководство по ремонту 3943495
- Бек, Йожеф (1983), "О свойстве решетки плоскости и некоторых задачах Дирака, Motzkin и Эрдеша в комбинаторной геометрии", Combinatorica , 3 : 281-297, DOI : 10.1007 / BF02579184 , МР 0729781
- Бьёрнер, Андерс ; Лас Вергнас, Мишель ; Штурмфельс, Бернд ; Белый, Нил; Циглер, Гюнтер М. (1993), Ориентированные матроиды , Энциклопедия математики и ее приложений, 46 , Кембридж: Издательство Кембриджского университета, стр. 273 , ISBN 0-521-41836-4, Руководство по ремонту 1226888
- Borwein, P .; Moser, WOJ (1990), "Исследование задачи Сильвестра и его обобщений", Aequationes Mathematicae , 40 (1): 111-135, DOI : 10.1007 / BF02112289 , МР 1069788
- Брасс, Питер; Мозер, Уильям; Пах, Янош (2005), Исследовательские проблемы дискретной геометрии , Берлин: Springer, ISBN 0-387-23815-8
- de Bruijn, NG ; Эрдеш, П. (1948), «Комбинированная [sic] проблема» (PDF) , Indagationes Mathematicae , 10 : 421–423, MR 0028289
- Chakerian, GD (1970), "Проблема Сильвестра на коллинеарных точках и относительной", American Mathematical Monthly , 77 : 164-167, DOI : 10,2307 / 2317330 , JSTOR 2317330 , MR 0258659
- Чен, Xiaomin (2006), "Теорема Сильвестра-Chvátal", дискретная и вычислительная геометрия , 35 (2): 193-199, DOI : 10.1007 / s00454-005-1216-9 , MR 2195050
- Chvátal, Vašek (2004), "Теорема Сильвестр и метрика промежуточность", Дискретная & Вычислительная геометрия , 31 (2): 175-195, DOI : 10.1007 / s00454-003-0795-6 , МР 2060634
- Косетер, HSM (1948), "Проблема коллинеарных точек", American Mathematical Monthly , 55 : 26-28, DOI : 10,2307 / 2305324 , JSTOR 2305324 , MR 0024137
- Кокстер, HSM (1969), «12.3 Проблема Сильвестра о коллинеарных точках», Введение в геометрию (2-е изд.), Нью-Йорк: John Wiley & Sons, стр. 181–182, ISBN 0-471-50458-0
- Кроу, DW; Макки, Т. (1968), "Проблема Сильвестра на коллинеарных точках", Математика Magazine , 41 (1): 30-34, DOI : 10,2307 / 2687957 , JSTOR 2687957 , MR 0235452
- Csima, J .; Сойер, Э. (1993), «Существуютобычные точки», Дискретный & Вычислительная геометрия , 9 : 187-202, DOI : 10.1007 / BF02189318 , МР 1194036
- Дирак, Г. (1951), "Свойства коллинеарности множеств точек", Quarterly Journal of Mathematics , 2 : 221–227, Bibcode : 1951QJMat ... 2..221D , doi : 10.1093 / qmath / 2.1.221 , MR 0043485
- Эдельсбруннер, Герберт ; Guibas Леонидас J. (1989), "топологически подметать расположение", журнал компьютерных и системных наук , 38 (1): 165-194, DOI : 10,1016 / 0022-0000 (89) 90038-X , MR 0990055
- Элкис, Ноам ; Преториус, Лу М .; Свейнпол, Конрад Дж. (2006), «Теоремы Сильвестра – Галлаи для комплексных чисел и кватернионов», Дискретная и вычислительная геометрия , 35 (3): 361–373, arXiv : math / 0403023 , doi : 10.1007 / s00454-005-1226 -7 , Руководство по ремонту 2202107
- Erdős, P. (1943), "Проблема 4065", задачи для решения: 4065-4069, American Mathematical Monthly , 50 (1): 65-66, DOI : 10,2307 / 2304011 , JSTOR 2304011
- Erdős, P. (1982), "Личные воспоминания и замечания по математической работе Тибор Галлаи" (PDF) , Combinatorica , 2 (3): 207-212, DOI : 10.1007 / BF02579228 , MR 0698647
- Geelen, JF ; Джерардс, AMH; Капур, A. (2000), "Исключенные несовершеннолетних для GF (4) -представимых матроиды" (PDF) , Журнал комбинаторной теории , серии B, 79 (2): 247-299, DOI : 10,1006 / jctb.2000.1963 , MR 1769191 , архивировано из оригинала (PDF) 24 сентября 2010 г.
- Грин, Бен ; Тао, Теренс (2013), «О множествах, определяющих несколько обычных линий», Дискретная и вычислительная геометрия , 50 (2): 409–468, arXiv : 1208.4714 , doi : 10.1007 / s00454-013-9518-9 , MR 3090525
- Грюнбаум, Бранко (1999), "Монохроматические точки пересечения в семействах цветных линий" (PDF) , Геомбинаторика , 9 (1): 3–9, MR 1698297
- Келли, Л. М. (1986), "Решение задачи Сильвестер-Галлаи из JP Серра", Дискретные и Вычислительная геометрия , 1 (2): 101-104, DOI : 10.1007 / BF02187687 , МР 0834051
- Келли, Л. М .; Мозер, WOJ (1958), «О количестве обычных линий, определяемыхточки», Canadian Journal математики , 10 : 210-219, DOI : 10,4153 / CJM-1958-024-6 , MR 0097014
- Манделькерна, Марк (2016), "конструктивный вариант Теорема Сильвестра", Acta Mathematica Hungarica , 150 : 121-130, DOI : 10.1007 / s10474-016-0624-г , МР 3542040
- Мельхиор, Э. (1941), "Über Vielseite der Projektive Ebene", Deutsche Mathematik , 5 : 461–475
- Моцкин, Т. (1951), "Линии и плоскости , соединяющих точки конечного множества", Труды Американского математического общества , 70 (3): 451-464, DOI : 10,2307 / 1990609 , JSTOR 1990609 , МР 0041447
- Mukhopadhyay, A .; Agrawal, A .; Хосабетту, Р.М. (1997), «О задаче с обыкновенной прямой в вычислительной геометрии», Nordic Journal of Computing , 4 (4): 330–341, MR 1607014
- Мухопадхьяй, Асиш; Грин, Евгений (2012), "Обычная проблема линия вновь", Вычислительная геометрия: теория и приложения , 45 (3): 127-130, DOI : 10.1016 / j.comgeo.2011.10.003 , МР 2853475
- Пах, Янош ; Шарир, Миха (2009), «Глава 1. Проблема Сильвестра – Галлая: Начало комбинаторной геометрии», Комбинаторная геометрия и ее алгоритмические приложения: Лекции Алкалы , Математические обзоры и монографии, 152 , Американское математическое общество , стр. 1–12
- Pambuccian, Виктора (2009), "Обратный анализ Теорема Сильвестра" , Нотр - Дам Журнал формальной логики , 50 (3): 245-260, DOI : 10,1215 / 00294527-2009-010 , МР 2572973
- Шеппард, GC (1968), "Проблемы Двадцать на выпуклых многогранников, часть I", Математическая газета , 52 : 136-156, DOI : 10,2307 / 3612678 , JSTOR 3612678 , MR 0231278
- Steinberg, R .; Бак, RC; Грюнвальд, Т .; Стинрод, NE (1944), "Три точки коллинеарности (решение проблемы 4065)", American Mathematical Monthly , 51 (3): 169-171, DOI : 10,2307 / 2303021 , JSTOR 2303021
- Сильвестр, Дж. Дж. (1893), «Математический вопрос 11851», The Educational Times , 46 (383): 156
- Woodall, HJ (1893), «Ответ на математический вопрос 11851», The Educational Times , 46 (385): 231
- Woodall, HJ (1893), «Ответ на математический вопрос 11851» , « Mathematical Questions and Solutions from the Educational Times» , 59 : 98
Внешние ссылки
- Малькевич, Джозеф (2003), "Дискретная геометрическая жемчужина" , колонка характеристик AMS , Американское математическое общество , архивировано с оригинала 10 октября 2006 г.
- Вайсштейн, Эрик В. , «Обычная линия» , MathWorld
- Доказательство презентации по Теренс Тао в 2013 Minerva Лекции