RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Математического института имени В. А. Стеклова // Архив

Труды МИАН, 2021, том 314, страницы 31–48 (Mi tm4189)

Эта публикация цитируется в 6 статьях

Циклы произвольной длины в графах расстояний над $\mathbb F_q^d$

А. Иосевич, Г. Джардин, Б. Макдональд

Department of Mathematics, University of Rochester, Rochester, NY, USA

Аннотация: Пусть $E \subset \mathbb F_q^d$ — подмножество линейного пространства размерности $d \ge 2$ над конечным полем $\mathbb F_q$ порядка $q$. В работе рассматривается так называемый граф расстояний $\mathcal G^{\text {dist}}_t(E)$, $t\neq 0$, в котором множеством вершин является $E$ и при этом две вершины $x$$y$ соединены ребром, если $\|x-y\| \equiv (x_1-y_1)^2+\dots +(x_d-y_d)^2=t$. Доказано, что при условии $|E| \ge C_k q^{\frac {d+2}{2}}$ граф $\mathcal G^{\text {dist}}_t(E)$ содержит правильное по порядку роста число циклов длины $k$. Также рассматривается граф скалярных произведений $\mathcal G^{\text {prod}}_t(E)$, $t\neq 0$, где в качестве множества вершин снова выступает $E$, а вершины $x$$y$ соединены ребром, если $x\cdot y \equiv x_1y_1+\dots +x_dy_d=t$. Аналогичные результаты получены и в этом случае, но методы доказательства несколько сложнее, поскольку функция $x\cdot y$ не инвариантна относительно сдвигов. При этом для достаточно длинных циклов показатель $\frac {d+2}{2}$ может быть уменьшен.

УДК: 512.624+519.1321

Поступило в редакцию: 21 сентября 2020 г.
После доработки: 24 февраля 2021 г.
Принята к печати: 30 июня 2021 г.

DOI: 10.4213/tm4189


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics, 2021, 314, 27–43

Реферативные базы данных:


© МИАН, 2024