Большие пути в дистанционных графах в векторных пространствах над конечным полем

Аннотация

В статье изучается следующая задача. Пусть $E \subset \mathbb{F}_{q}^{d}$ является подмножеством $d-$ мерного векторного пространства над конечным полем из $q$ элементов.
Мы определяем так называемый дистанционный граф на множестве $E$ c единичным расстоянием между вершинами. Расстояние между вершинами $x,y$ определяется так $\|x\! -\! y \|\!=\!(x_{1}-y_{1})^{2}+\ldots +(x_{d}-y_{d})^{2}$.
Вершины дистанционного графа это элементы множества $E$ и пара вершин $x,y \in E$ соединены ребром если расстояние между ними равно единице.
В настоящей работе изучаются длинные пути в этом графе.
А именно, получена нижняя оценка на длину самого большого непересекающегося пути в нем.
При определенных условиях в работе доказано, что длина такого пути состоит из большинства вершин из множества $E$. Это дополняет результат из работы А. Иосевича и соавторов.
При доказательстве мы используем некоторые комбинаторные идеи и результаты, полученные А. Иосевичем и М. Рудневым а также совместный результат М. Беннета, Дж. Чапмана, Д. Коверта, Д. Харта, А. Иосевича и Дж. Пакианатана. Основная идея построения большого пути в таком графе заключается в следующем. Мы строим много путей меньшей длины стандартными методами. Далее, основываясь на совместном результате М.Руднева и А. Иосевича о распределении расстояний между элементами множества $E$, мы заключаем, что существуют пара вершин у двух различных путей с расстоянием единица. Тем самым есть возможность соединить какие-то два уже построенных пути за их вершины и получить путь большей длины. Эта процедура повторяется итеративно до тех пор, пока не построится путь заданной нами длины. Отметим, что данный метод и основной результат остается верен и для так определенных дистанционных графов с любым ненулевым расстоянием.