WikiDer > Теорема Сильвестра – Галлаи

Три обычные линии в сетке точек 4 × 4

В Теорема Сильвестра – Галлаи в геометрия заявляет, что каждый конечный набор очков в Евклидова плоскость имеет линию, проходящую ровно через две точки, или линию, проходящую через все из них. Он назван в честь Джеймс Джозеф Сильвестр, который сформулировал это как проблему в 1893 году, и Тибор Галлай, опубликовавший одно из первых доказательств этой теоремы в 1944 г.

Линия, содержащая ровно две точки из набора, называется обычная линия. Согласно усилению теоремы, каждое конечное множество точек (не все на одной прямой) имеет по крайней мере линейное количество обычных прямых. An алгоритм можно найти обычную строку в наборе ${ displaystyle n}$ моменты времени ${ Displaystyle О (п журнал п)}$.

История

Теорема Сильвестра – Галлаи была поставлена ​​как проблема Дж. Дж. Сильвестр (1893). Келли (1986) предполагает, что Сильвестр мог быть мотивирован связанным феноменом в алгебраическая геометрия, в которой точки перегиба из кубическая кривая в комплексная проективная плоскость сформировать конфигурация из девяти точек и двенадцати линий ( Конфигурация Гессен), в котором каждая линия, определяемая двумя точками, содержит третью точку. Теорема Сильвестра – Галлаи означает, что все девять точек не могут иметь действительные координаты.^[1]

Вудолл (1893) Ошибка harvtxt: несколько целей (2 ×): CITEREFWoodall1893 (Помогите) утверждал, что у него есть краткое доказательство теоремы Сильвестра – Галлаи, но оно уже было отмечено как неполное на момент публикации. Эберхард Мельхиор (1941) доказал теорему (и фактически немного более сильный результат) в эквивалентной формулировке, ее проективный дуальный. Не зная о доказательствах Мельхиора,^[2] Пол Эрдёш (1943) снова высказал гипотезу, которая впоследствии была доказана Тибор Галлай, а вскоре и другими авторами.^[3]

В обзоре 1951 года Эрдеш назвал результат «теоремой Галлая»,^[4] но она уже была названа теоремой Сильвестра – Галлаи в обзоре 1954 г. Леонард Блюменталь.^[5] Это один из многих математические темы имени Сильвестра.

Эквивалентные версии

Вопрос о существовании обыкновенной линии может быть поставлен и для точек в реальном проективная плоскость RP² вместо Евклидова плоскость. Проективная плоскость может быть образована из евклидовой плоскости путем добавления дополнительных точек «на бесконечности», где прямые, параллельные в евклидовой плоскости, пересекаются друг с другом, и путем добавления единственной линии «на бесконечности», содержащей все добавленные точки. Однако дополнительные точки проективной плоскости не могут помочь создать неевклидовы конечные наборы точек без обычных линий, поскольку любой конечный набор точек в проективной плоскости может быть преобразован в набор евклидовых точек с тем же комбинаторным шаблоном инцидентностей точечных линий. . Следовательно, любой образец конечного числа пересекающихся точек и линий, который существует в одном из этих двух типов плоскости, также существует в другом. Тем не менее, проективная точка зрения позволяет легче описывать определенные конфигурации. В частности, это позволяет использовать проективная двойственность, в котором роли точек и линий в утверждениях проективной геометрии могут быть заменены друг на друга. При проективной двойственности существование обыкновенной прямой для множества неколлинеарных точек в RP² эквивалентно существованию обычная точка в нетривиальном договоренность конечного числа строк. Расположение называется тривиальным, если все его прямые проходят через общую точку, и нетривиальным в противном случае; обычная точка - это точка, которая принадлежит ровно двум прямым.^[2]

В удлиненный додекаэдр, а зоноэдр. Его восемь красных граней параллелограмма соответствуют обычным точкам пятистрочного расположения; эквивалентная форма теоремы Сильвестра – Галлаи утверждает, что каждый зоноэдр имеет хотя бы одну грань параллелограмма.

Расположение линий имеет комбинаторную структуру, тесно связанную с зоноэдры, многогранники, образованные Сумма Минковского конечного набора отрезки линии, называемые генераторами. В связи с этим каждая пара противоположных граней зоноэдра соответствует точке пересечения расположения прямых в проективной плоскости, с одной линией для каждой образующей. Количество сторон каждой грани в два раза превышает количество пересекающихся линий. Например, удлиненный додекаэдр показан зоноэдр с пятью образующими, двумя парами противоположных граней шестиугольника и четырьмя парами противоположных граней параллелограмма. В соответствующем пятистрочном расположении пересекаются две тройки прямых (соответствующие двум парам противоположных шестиугольников), а остальные четыре пары прямых пересекаются в обычных точках (соответствующих четырем парам противоположных параллелограммов). Эквивалентное утверждение теоремы Сильвестра – Галла в терминах зоноэдров состоит в том, что каждый зоноэдр имеет хотя бы одну грань параллелограмма (прямоугольники, ромбы и квадраты считаются частными случаями параллелограммов). Более того, когда наборы ${ displaystyle n}$ точки на плоскости могут гарантированно иметь не менее ${ displaystyle t_ {2} (п)}$ обыкновенные линии, зоноэдры с ${ displaystyle n}$ генераторы могут иметь не менее ${ Displaystyle 2t_ {2} (п)}$ паралограммы лиц.^[6]

Доказательства

Теорема Сильвестра – Галла была доказана множеством различных способов. Доказательство Галлая 1944 года переключается между евклидовой и проективной геометрией, чтобы преобразовать точки в эквивалентную конфигурацию, в которой обычная линия может быть найдена как линия наклона, ближайшая к нулю; подробности см. Борвейн и Мозер (1990). Доказательство Мельхиора 1941 года использует проективную двойственность, чтобы преобразовать проблему в эквивалентный вопрос о расположении линий, на который можно ответить, используя Формула полиэдра Эйлера. Еще одно доказательство Лерой Милтон Келли показывает от противного, что соединительная линия с наименьшим ненулевым расстоянием до другой точки должна быть обычной. И, следуя более раннему доказательству Стейнберга, Х. С. М. Коксетер показал, что метрические концепции наклона и расстояния, фигурирующие в доказательствах Галлая и Келли, являются излишне мощными, вместо этого доказывая теорему, используя только аксиомы упорядоченная геометрия.

Доказательство Келли

Обозначения для доказательства Келли

Это доказательство Лерой Милтон Келли. Айгнер и Циглер (2018) назовем его «просто лучшим» из многих доказательств этой теоремы.^[7]

Предположим, что конечное множество ${ displaystyle S}$ точек не все коллинеарны. Определите соединительную линию как линию, содержащую как минимум две точки в коллекции. По конечности, ${ displaystyle S}$ должен иметь точку ${ displaystyle P}$ и соединительная линия ${ displaystyle ell}$ которые находятся на положительном расстоянии друг от друга, но ближе, чем все другие пары точек-линий. Келли доказал, что ${ displaystyle ell}$ обычный, от противного.^[7]

Предположить, что ${ displaystyle ell}$ не обычный. Затем проходит не менее трех точек ${ displaystyle S}$. По крайней мере два из них находятся на одной стороне ${ displaystyle P '}$, перпендикулярная проекция ${ displaystyle P}$ на ${ displaystyle ell}$. Позвони им ${ displaystyle B}$ и ${ displaystyle C}$, с участием ${ displaystyle B}$ быть ближе всего к ${ displaystyle P '}$ (и, возможно, совпадающий с ним). Проведите соединительную линию ${ displaystyle m}$ проходя через ${ displaystyle P}$ и ${ displaystyle C}$, а перпендикуляр из ${ displaystyle B}$ к ${ displaystyle B '}$ на ${ displaystyle m}$ . потом ${ displaystyle BB '}$ короче чем ${ displaystyle PP '}$. Это следует из того, что ${ displaystyle PP'C}$ и ${ displaystyle BB'C}$ находятся похожие треугольники, одно содержится внутри другого.^[7]

Однако это противоречит первоначальному определению ${ displaystyle P}$ и ${ displaystyle ell}$ как пара точка-линия с наименьшим положительным расстоянием. Итак, предположение, что ${ displaystyle ell}$ Необычно не может быть правдой, КЭД.^[7]

Доказательство Мельхиора

В 1941 году (таким образом, до того, как Эрдеш опубликовал этот вопрос и последующее доказательство Галлая), Мельхиор показал, что любое нетривиальное конечное расположение прямых в проективной плоскости имеет по крайней мере три обычные точки. По двойственности этот результат также говорит о том, что любое конечное нетривиальное множество точек на плоскости имеет по крайней мере три обычные прямые.^[8]

Мельхиор заметил, что для любого графика встроенный в реальной проективной плоскости формула ${ Displaystyle V-E + F}$ должен равняться ${ displaystyle 1}$, то Эйлерова характеристика проективной плоскости. Здесь ${ displaystyle V}$, ${ displaystyle E}$, и ${ displaystyle F}$ - количество вершин, ребер и граней графа соответственно. Любое нетривиальное расположение прямых на проективной плоскости определяет граф, в котором каждая грань ограничена по крайней мере тремя ребрами, а каждое ребро ограничивает две грани; так, двойной счет дает дополнительное неравенство ${ Displaystyle F leq 2E / 3}$. Используя это неравенство для исключения ${ displaystyle F}$ из эйлеровой характеристики приводит к неравенству ${ Displaystyle E leq 3V-3}$. Но если бы каждая вершина в расположении была точкой пересечения трех или более линий, то общее количество ребер было бы не менее ${ displaystyle 3V}$, что противоречит этому неравенству. Следовательно, некоторые вершины должны быть точкой пересечения только двух прямых, и, как показывает более тщательный анализ Мельхиора, необходимы по крайней мере три обычные вершины, чтобы удовлетворять неравенству ${ Displaystyle E leq 3V-3}$.^[8]

В качестве Айгнер и Циглер (2018) заметим, тот же аргумент в пользу существования обычной вершины был дан в 1944 г. Норман Стинрод, который явно применил его к двойственной задаче обыкновенной прямой.^[9]

Неравенство Мельхиора

С помощью аналогичного аргумента Мельхиор смог доказать более общий результат. Для каждого ${ Displaystyle к geq 2}$, позволять ${ displaystyle t_ {k}}$ быть количеством точек, к которым ${ displaystyle k}$ линии инцидентны. потом^[8]

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

или эквивалентно,

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

Аксиоматика

Х. С. М. Коксетер (1948, 1969) пишет о доказательстве Келли о том, что использование им евклидова расстояния излишне мощно, «как использование кувалды, чтобы расколоть миндаль». Вместо этого Кокстер дал еще одно доказательство теоремы Сильвестра – Галлаи в рамках упорядоченная геометрия, аксиоматизация геометрии с точки зрения промежуточности, которая включает не только евклидову геометрию, но и несколько других связанных геометрий.^[10] Доказательство Кокстера - это вариант более раннего доказательства, данного Стейнбергом в 1944 году.^[11] Проблема нахождения минимального набора аксиом, необходимого для доказательства теоремы, принадлежит обратная математика; видеть Памбуччиец (2009) для изучения этого вопроса.

Обычное утверждение теоремы Сильвестра – Галлаи неверно в конструктивный анализ, поскольку это подразумевает менее ограниченный принцип всеведения, ослабленная форма закон исключенного среднего это отвергается как аксиома конструктивной математики. Тем не менее, можно сформулировать версию теоремы Сильвестра – Галлаи, которая справедлива в рамках аксиом конструктивного анализа, и адаптировать доказательство теоремы Келли, чтобы оно было достоверным доказательством при этих аксиомах.^[12]

Нахождение обычной линии

Доказательство Келли существования обыкновенной линии можно превратить в алгоритм, который находит обычную линию путем поиска ближайшей пары точки и линии через две другие точки. Мухопадхьяй и Грин (2012) сообщить время для поиска ближайшей пары как ${ Displaystyle О (п ^ {3})}$, на основе перебор всех троек точек, но алгоритм поиска ближайшей заданной точки к каждой линии через две заданные точки во времени ${ Displaystyle О (п ^ {2})}$, был предоставлен ранее Эдельсбруннер и Гибас (1989), как подпрограмма для поиска треугольника минимальной площади, определяемого тремя точками из заданного набора. Та же статья Эдельсбруннер и Гибас (1989) также показывает, как построить двойное расположение прямых к заданным точкам (как используется в доказательстве Мельхиора и Стинрода) за одно и то же время, ${ Displaystyle О (п ^ {2})}$, из которого можно выделить все обычные вершины и все обычные прямые. Мукхопадхьяй, Агравал и Хосабетту (1997) впервые показал, как найти единственную обыкновенную линию (не обязательно из доказательства Келли) во времени ${ Displaystyle О (п журнал п)}$, а более простой алгоритм с той же временной границей был описан Мухопадхьяй и Грин (2012).

Алгоритм Мухопадхьяй и Грин (2012) основан на доказательстве Кокстера с использованием упорядоченной геометрии. Он выполняет следующие шаги:

1. Выберите точку ${ displaystyle p_ {0}}$ это вершина из выпуклый корпус из данных точек.
2. Построить линию ${ displaystyle ell _ {0}}$ что проходит через ${ displaystyle p_ {0}}$ и в противном случае остается вне выпуклой оболочки.
3. Отсортируйте остальные заданные точки по углу, который они образуют с ${ displaystyle p_ {0}}$, объединяя точки, образующие один угол.
4. Если какая-либо из точек одна в своей группе, верните обычную линию через эту точку и ${ displaystyle p_ {0}}$.
5. Для каждых двух последовательных групп точек в отсортированной по углам последовательности образуют две линии, каждая из которых проходит через ближайшую к ${ displaystyle p_ {0}}$ в одной группе и в самой дальней точке от ${ displaystyle p_ {0}}$ в другой группе.
6. Для каждой строки ${ displaystyle ell _ {i}}$ в образованном таким образом наборе прямых найти точку пересечения ${ displaystyle ell _ {i}}$ с ${ displaystyle ell _ {0}}$
7. Верните линию ${ displaystyle ell _ {i}}$ чья точка пересечения с ${ displaystyle ell _ {0}}$ ближе всего к ${ displaystyle p_ {0}}$.

Как доказывают авторы, строка, возвращаемая этим алгоритмом, должна быть обычной. Доказательство осуществляется либо путем построения, если оно возвращается на шаге 4, либо путем противоречия, если оно возвращается на шаге 7: если строка, возвращенная на шаге 7, не была обычной, то авторы доказывают, что между одним из них может существовать обычная линия. его точки и ${ displaystyle p_ {0}}$, но эта строка уже должна была быть найдена и возвращена на шаге 4.^[13]

Количество обычных линий

Два известных примера точечных множеств с меньшим, чем ${ displaystyle n / 2}$ обычные линии.

Хотя теорема Сильвестра – Галлаи утверждает, что расположение точек, не все коллинеарные, должно определять обычную линию, она не говорит, сколько точек должно быть определено. Позволять ${ Displaystyle t_ {2} (п)}$ быть минимальным количеством обычных линий, определенным для каждого набора ${ displaystyle n}$ неколлинеарные точки. Доказательство Мельхиора показало, что ${ Displaystyle т_ {2} (п) geq 3}$. де Брюйн и Erds (1948) поднял вопрос о том, ${ Displaystyle t_ {2} (п)}$ приближается к бесконечности с ${ displaystyle n}$. Теодор Моцкин (1951) подтвердил это, доказав, что ${ Displaystyle т_ {2} (п) geq { sqrt {n}}}$. Габриэль Дирак (1951) предположил, что ${ Displaystyle т_ {2} geq lfloor n / 2 rfloor}$, для всех значений ${ displaystyle n}$, предположение, которое все еще актуально по состоянию на 2013 год.^{[Обновить]}. Это часто называют Гипотеза Дирака – Моцкина; см. например Латунь, Мозер и Пах (2005), п. 304). Келли и Мозер (1958) доказал, что ${ Displaystyle т_ {2} (п) geq 3n / 7}$.

Пример (четной) конфигурации Бёрёчки с 10 точками, определяющими 5 обычных линий (пять сплошных черных линий на рисунке).

Предполагаемая нижняя граница Дирака является асимптотически наилучшей возможной, поскольку четные числа ${ displaystyle n}$ больше четырех имеют соответствующую верхнюю границу ${ Displaystyle т_ {2} (п) leq п / 2}$. Строительство, благодаря Кароли Бёрёчки, который достигает этой границы, состоит из вершин регулярного ${ displaystyle m}$-гон в реальном проективная плоскость и другой ${ displaystyle m}$ очков (таким образом, ${ displaystyle n = 2m}$) на бесконечно удаленной прямой, соответствующей каждому из направлений, определяемых парами вершин. Хотя есть ${ Displaystyle м (м-1) / 2}$ пары этих точек, они определяют только ${ displaystyle m}$ четкие направления. В этой договоренности есть только ${ displaystyle m}$ обычные линии, линии, соединяющие вершину ${ displaystyle v}$ с бесконечно удаленной точкой, коллинеарной двум соседям ${ displaystyle v}$. Как и в случае любой конечной конфигурации на реальной проективной плоскости, эту конструкцию можно изменить так, чтобы все точки были конечными, без изменения количества обычных прямых.^[14]

Для нечетных ${ displaystyle n}$, известны только два примера, которые соответствуют гипотезе Дирака о нижней оценке, т.е. ${ Displaystyle т_ {2} (п) = (п-1) / 2}$ Один пример, автор Келли и Мозер (1958), состоит из вершин, середин ребер и центроида равностороннего треугольника; эти семь точек определяют только три обычные линии. В конфигурация в котором эти три обычные линии заменены единственной линией, не может быть реализована на евклидовой плоскости, но образует конечную проективное пространство известный как Самолет Фано. Из-за этой связи пример Келли – Мозера также называют конфигурацией нефано.^[15] Другой контрпример, приведенный Макки,^[14] состоит из двух правильных пятиугольников, соединенных между собой ребром, вместе со средней точкой общего ребра и четырех точек на бесконечной линии в проективная плоскость; эти 13 точек имеют среди них 6 обычных линий. Модификации конструкции Бёрёчки приводят к наборам нечетного числа точек с ${ Displaystyle 3 lfloor п / 4 rfloor}$ обычные линии.^[16]

Чима и Сойер (1993) доказал, что ${ Displaystyle т_ {2} (п) geq lceil 6n / 13 rceil}$ кроме тех случаев, когда ${ displaystyle n}$ семь. Асимптотически эта формула уже ${ displaystyle 12/13 приблизительно 92,3 \%}$ проверенных ${ displaystyle n / 2}$ верхняя граница. В ${ displaystyle n = 7}$ случай является исключением, поскольку иначе конструкция Келли – Мозера была бы контрпримером; их конструкция показывает, что ${ Displaystyle т (7) leq 3}$. Однако действительна ли граница Чима – Сойера для ${ displaystyle n = 7}$, он будет утверждать, что ${ displaystyle t_ {2} (7) geq 4}$.

Близкий результат Теорема Бека, устанавливая компромисс между количеством линий с несколькими точками и количеством точек на одной строке.^[17]

Бен Грин и Теренс Тао показал, что для всех достаточно больших точечных множеств (т. е. ${ displaystyle n> n_ {0}}$ для подходящего выбора ${ displaystyle n_ {0}}$) число обычных строк действительно не менее ${ displaystyle n / 2}$. Кроме того, когда ${ displaystyle n}$ является странный, количество обычных строк не менее ${ displaystyle 3n / 4-C}$, для некоторой постоянной ${ displaystyle C}$. Таким образом, конструкции Бёрёчки для четных и нечетных чисел (обсуждаемые выше) являются наилучшими из возможных. Сведение к минимуму количества обычных строк тесно связано с проблема садоводства максимизации числа трехточечных прямых, которую Грин и Тао также решили для всех достаточно больших точечных множеств.^[18]

Количество соединительных линий

В качестве Пол Эрдёш Как уже отмечалось, из теоремы Сильвестра – Галла сразу следует, что любой набор ${ displaystyle n}$ точки, которые не коллинеарны, определяет по крайней мере ${ displaystyle n}$ разные строки. Этот результат известен как Теорема Де Брейна – Эрдеша. В базовом случае результат явно верен для ${ displaystyle n = 3}$. Для любого большего значения ${ displaystyle n}$, результат можно уменьшить с ${ displaystyle n}$ указывает на ${ displaystyle n-1}$ точек, удалив обычную линию и одну из двух точек на ней (стараясь не удалить точку, для которой оставшееся подмножество будет лежать на одной линии). Таким образом, следует по математической индукции. Пример почти карандаша, набора ${ displaystyle n-1}$ коллинеарные точки вместе с одной дополнительной точкой, которая не находится на той же линии, что и другие точки, показывает, что эта граница жесткая.^[16]

Обобщения

Теорема Сильвестра – Галла была обобщена на цветные точечные множества на евклидовой плоскости, а также на системы точек и прямых, определенные алгебраически или расстояниями в метрическое пространство. Вообще говоря, эти варианты теоремы рассматривают только конечные множества точек, чтобы избежать таких примеров, как набор всех точек на евклидовой плоскости, который не имеет обычной линии.

Цветные точки

Вариант проблемы Сильвестра, поставленной в середине 1960-х гг. Рональд Грэм и популяризируется Дональд Дж. Ньюман, рассматривает конечные плоские наборы точек (не все в линии), которым заданы два цвета, и спрашивает, есть ли в каждом таком наборе прямая, проходящая через две или более точек одного цвета. На языке наборов и семейства наборов, эквивалентное утверждение состоит в том, что семейство коллинеарных подмножеств конечного множества точек (не все на одной строке) не может иметь Свойство B. Доказательство этого варианта было объявлено Теодор Моцкин но никогда не публиковался; первое опубликованное доказательство было сделано Чакериан (1970).^[19]

Неверные координаты

В Конфигурация Гессен, в котором линия, проходящая через каждую пару точек, содержит третью точку. Теорема Сильвестра – Галлаи показывает, что она не может быть реализована прямыми линиями на евклидовой плоскости, но имеет реализацию в комплексная проективная плоскость.

Так же, как Евклидова плоскость или проективная плоскость можно определить с помощью действительные числа для координат их точек (Декартовы координаты для евклидовой плоскости и однородные координаты для проективной плоскости) аналогичные абстрактные системы точек и линий могут быть определены с использованием других систем счисления в качестве координат. Теорема Сильвестра – Галлаи не верна для геометрий, определенных таким образом над конечные поля: для некоторых конечных геометрий, определенных таким образом, таких как Самолет Фано, множество всех точек геометрии не имеет обычных линий.^[7]

Теорема Сильвестра-Галла также не применяется напрямую к геометриям, в которых точки имеют координаты, которые являются парами сложные числа или кватернионы, но эти геометрии имеют более сложные аналоги теоремы. Например, в комплексная проективная плоскость существует конфигурация из девяти баллов, Конфигурация Гессе (точки перегиба кубической кривой), в которых каждая прямая необычна, что нарушает теорему Сильвестра – Галлаи. Такая конфигурация известна как Конфигурация Сильвестра-Галлая, и это не может быть реализовано точками и линиями евклидовой плоскости. Другой способ сформулировать теорему Сильвестра – Галлаи состоит в том, что всякий раз, когда точки конфигурации Сильвестра – Галла вкладываются в евклидово пространство с сохранением коллинеарности, все точки должны лежать на одной прямой, и пример конфигурации Гессе показывает, что это ложно для комплексная проективная плоскость. Однако, Келли (1986) доказал аналог теоремы Сильвестра – Галлаи для комплексных чисел: всякий раз, когда точки конфигурации Сильвестра – Галлаи вложены в комплексное проективное пространство, все точки должны лежать в двумерном подпространстве. Эквивалентно, набор точек в трехмерном сложном пространстве, чьи аффинная оболочка это все пространство должно иметь обычную линию, а на самом деле должно иметь линейное количество обычных линий.^[20] Так же, Лось, Преториус и Свейнпол (2006) показал, что всякий раз, когда конфигурация Сильвестра – Галла вкладывается в пространство, определенное над кватернионами, ее точки должны лежать в трехмерном подпространстве.

Матроиды

Каждый набор точек на евклидовой плоскости и соединяющие их прямые можно абстрагировать как элементы и плоскости ранга-3. ориентированный матроид. Точки и линии геометрии, определенные с использованием других систем счисления, чем действительные числа, также образуют матроиды, но не обязательно ориентированные матроиды. В этом контексте результат Келли и Мозер (1958) нижнюю границу числа обычных прямых можно обобщить на ориентированные матроиды: каждый ориентированный матроид ранга 3 с ${ displaystyle n}$ элементов имеет как минимум ${ displaystyle 3n / 7}$ двухточечные прямые или, что то же самое, каждый матроид ранга 3 с меньшим количеством двухточечных прямых должен быть неориентируемым.^[21] Матроид без двухточечных линий называется Сильвестр матроид. Соответственно, конфигурация Келли – Мозера с семью точками и только тремя обычными линиями образует одну из запрещенные несовершеннолетние за GF (4) -представимые матроиды.^[15]

Геометрия расстояния

Другое обобщение теоремы Сильвестра – Галлаи на произвольные метрические пространства было предположено Chvátal (2004) и доказано Чен (2006). В этом обобщении тройка точек в метрическом пространстве определяется как коллинеарная, когда неравенство треугольника для этих точек есть равенство, и линия определяется из любой пары точек путем многократного включения дополнительных точек, которые коллинеарны точкам, уже добавленным к линии, до тех пор, пока такие точки больше не будут добавлены. Обобщение Хватала и Чена утверждает, что каждое конечное метрическое пространство имеет прямую, содержащую либо все точки, либо ровно две точки.^[22]

Примечания

Рекомендации

внешняя ссылка

• Малькевич, Иосиф (2003), «Дискретная геометрическая жемчужина», Столбец характеристик AMS, Американское математическое общество, заархивировано из оригинал на 2006-10-10
• Вайсштейн, Эрик В., «Обычная линия», MathWorld
• Доказательство презентации к Теренс Тао на лекциях Minerva 2013