Проблема с посадкой сада

В дискретной геометрии исходная задача о посадке фруктовых садов (или задача о посадке деревьев ) требует максимального количества трехточечных линий , достижимого за счет конфигурации определенного количества точек на плоскости . Также проводятся исследования того, сколько $из k$ может быть линий -точек. Халлард Т. Крофт и Пол Эрдеш доказали $t_{k}>{\frac {cn^{2}}{k^{3}}},$ где $n$ — количество точек, а $t k$ — количество $линий с k$ -точками. ^[1] Их конструкция содержит несколько $m$ -точечных прямых, где $m > k$ . Можно также задать вопрос, если это запрещено.

Целочисленная последовательность

Определите ⁠ $t_{3}^{\text{orchard}}(n)$ ⁠ — максимальное количество трехточечных линий, достижимое при конфигурации из $n$ точек. Для произвольного количества $n$ точек ⁠ $t_{3}^{\text{orchard}}(n)$ ⁠ было показано, что ${\tfrac {1}{6}}n^{2}-O(n)$ в 1974 году.

Первые несколько значений ⁠ $t_{3}^{\text{orchard}}(n)$ ⁠ приведены в следующей таблице (последовательность A003035 в OEIS ).

$н$	4	5	6	7	8	9	10	11	12	13	14
⁠ $t_{3}^{\text{orchard}}(n)$ ⁠	1	2	4	6	7	10	12	16	19	22	26

Верхняя и нижняя границы

Поскольку никакие две прямые не могут иметь общие две различные точки, тривиальная верхняя граница количества трехточечных линий, определяемых $n$ точками, равна $\left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .$ Используя тот факт, что количество двухточечных линий не менее ⁠ ${\tfrac {6n}{13}}$ ⁠ ( Csima & Sawyer 1993 ), эту верхнюю границу можно снизить до $\left\lfloor {\frac {{\binom {n}{2}}-{\frac {6n}{13}}}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .$

Нижние оценки для ⁠ $t_{3}^{\text{orchard}}(n)$ ⁠ задаются конструкциями для множеств точек со многими трехточечными линиями. Самая ранняя квадратичная нижняя граница $\approx {\tfrac {1}{8}}n^{2}$ был дан Сильвестром , который поместил $n$ точек на кубическую кривую $y = x 3$ . Это было улучшено до ${\tfrac {1}{6}}n^{2}-{\tfrac {1}{2}}n+1$ в 1974 году Берром , Грюнбаумом и Слоаном ( 1974 ), используя конструкцию, основанную на эллиптических функциях Вейерштрасса . Элементарная конструкция с использованием гипоциклоидов была найдена Фюреди и Паласти (1984), достигнув той же нижней границы.

В сентябре 2013 года Бен Грин и Теренс Тао опубликовали статью, в которой доказывают, что для всех наборов точек достаточного размера $n > n 0$ существует не более ${\frac {n(n-3)}{6}}+1={\frac {1}{6}}n^{2}-{\frac {1}{2}}n+1$ Трехочковые линии, соответствующие нижней границе, установленной Берром, Грюнбаумом и Слоаном. ^[2] Таким образом, при достаточно большом $n$ точное значение ⁠ $t_{3}^{\text{orchard}}(n)$ ⁠ известно.

Это немного лучше, чем граница, которая напрямую следует из их жесткой нижней границы ⁠. ${\tfrac {n}{2}}$ ⁠ для количества двухточечных линий : ${\tfrac {n(n-2)}{6}},$ доказал в той же статье и решил проблему 1951 года, независимо поставленную Габриэлем Эндрю Дираком и Теодором Моцкиным .

Задача о посадке фруктовых садов также рассматривалась на конечных полях. В этой версии задачи $n$ точек лежат в проективной плоскости, определенной над конечным полем ( Падманабхан и Шукла, 2020 ).

Примечания

^ Справочник по комбинаторике под редакцией Ласло Ловаша , Рона Грэма и др., в главе « Экстремальные задачи комбинаторной геометрии» Пола Эрдеша и Джорджа Б. Перди .
^ Грин и Тао (2013)

Ссылки

Брасс, П.; Мозер, WOJ; Пах, Дж. (2005), Проблемы исследования дискретной геометрии , Springer-Verlag, ISBN 0-387-23815-8 .
Берр, Южная Каролина ; Грюнбаум, Б .; Слоан, Нью-Джерси (1974), «Проблема сада», Geometriae Dedicata , 2 (4): 397–424, doi : 10.1007/BF00147569 , S2CID 120906839 .
Чима, Дж.; Сойер, Э. (1993), «Существует 6 n /13 обычных точек», Дискретная и вычислительная геометрия , 9 (2): 187–202, doi : 10.1007/BF02189318 .
Фюреди, З. ; Паласти, И. (1984), «Расположение линий с большим количеством треугольников», Proceedings of the American Mathematical Society , 92 (4): 561–566, doi : 10.2307/2045427 , JSTOR 2045427 .
Грин, Бен ; Тао, Теренс (2013), «О множествах, определяющих несколько обычных линий», Дискретная и вычислительная геометрия , 50 (2): 409–468, arXiv : 1208.4714 , doi : 10.1007/s00454-013-9518-9 , S2CID 15813230
Падманабхан, Р.; Шукла, Алок (2020), «Сады в эллиптических кривых над конечными полями», Конечные поля и их приложения , 68 (2): 101756, arXiv : 2003.07172 , doi : 10.1016/j.ffa.2020.101756 , S2CID 212725631

Внешние ссылки

Вайсштейн, Эрик В. , «Проблема посадки фруктовых садов» , MathWorld

[1] Справочник по комбинаторике под редакцией Ласло Ловаша , Рона Грэма и др., в главе « Экстремальные задачи комбинаторной геометрии» Пола Эрдеша и Джорджа Б. Перди .

[2] Грин и Тао (2013)

[1]

[2]