И.Н. Белоусов, А.А. Махнев. Обратные задачи в теории дистанционно регулярных графов: двойственные 2-схемы ... С. 44-51

УДК 519.17

MSC: 05C25

DOI: 10.21538/0134-4889-2019-25-4-44-51

Полный текст статьи (Full text)

Пусть $\Gamma$ - дистанционно регулярный граф диаметра 3 с сильно регулярным графом $\Gamma_3$. Нахождение параметров графа $\Gamma_3$ по массиву пересечений графа $\Gamma$ является прямой задачей. Нахождение массива пересечений графа $\Gamma$ по параметрам графа $\Gamma_3$ является обратной задачей. Прямая и обратная задачи были решены А.А. Махневым и М.С. Нировой: если граф $\Gamma$ с массивом пересечений $\{k,b_1,b_2;1,c_2,c_3\}$ имеет собственное значение $\theta_2=-1$, то дополнительный граф к $\Gamma_3$ является псевдогеометрическим для $pG_{c_3}(k,b_1/c_2)$. Обратно, если $\Gamma_3$ является псевдогеометрическим графом для $pG_{\alpha}(k,t)$, то $\Gamma$ имеет массив пересечений $\{k,c_2t,k-\alpha+1;1,c_2,\alpha\}$, где $k-\alpha+1\le c_2t<k$, $1\le c_2\le \alpha$. Ранее изучались дистанционно регулярные графы $\Gamma$ диаметра 3, для которых граф $\Gamma_3$ ($\bar \Gamma_3$) является псевдогеометрическим графом для сети или обобщенного четырехугольника. В данной работе изучаются массивы пересечений дистанционно регулярных графов $\Gamma$ диаметра 3, для которых граф $\Gamma_3$ ($\bar \Gamma_3$) является псевдогеометрическим графом для двойственной 2-схемы $pG_{t+1}(l,t)$. Найдены новые серии допустимых массивов пересечений: $$\{m(m^2-1),m^2(m-1),m^2;1,1,(m^2-1)(m-1)\},  \{m(m+1),(m+2)(m-1),m+2;1,1,m^2-1\},$$ $$\{2m(m-1),(2m-1)(m-1),2m-1;1,1,2(m-1)^2\},$$ где $m\equiv\  \pm 1\ ({\rm mod}\ 3)$. Известные серии 2-схем Штейнера -это унитали, схемы, отвечающие проективным плоскостям четного порядка, содержащим гиперовал, схемы точек и прямых проективного пространства $PG(n,q)$ и схемы точек и прямых аффинного пространства $AG(n,q)$. Найдены допустимые массивы пересечений    дистанционно регулярных графов $\Gamma$ диаметра 3, для которых граф $\Gamma_3$ ($\bar \Gamma_3$) является псевдогеометрическим графом для одной из известных 2-схем Штейнера.

Ключевые слова: дистанционно регулярный граф, дуальная 2-схема

СПИСОК ЛИТЕРАТУРЫ

1.   Brouwer A.E., Cohen A.M., Neumaier A. Distance-regular graphs. Berlin; Heidelberg; N Y: Springer-Verlag, 1989. 495 p.

2.   Koolen J.H., Park J. Shilla distance-regular graphs // Europ. J. Comb. 2010. Vol. 31. P. 2064–2073.

3.   Jurisic A., Koolen J. Krein parameters and antipodal tight graphs with diameter 3 and 4 // Discrete Math. 2002. Vol. 244. P. 181–202. doi: 10.1016/S0012-365X(01)00082-6 

4.   Bang S., Koolen J. Distance-regular graphs of diameter 3 having eigenvakue -1 // Linear Algebra Appl. 2017. Vol. 531. P. 38–53. doi: 10.1016/j.laa.2017.05.038 

5.   Махнев А.А., Нирова М.С. Дистанционно регулярные графы Шилла с $b_2 = c_2$ // Мат. заметки. 2018. Т. 103, № 5. C. 730–744. doi: 10.4213/mzm11503 

6.   Barwick S., Ebert G. Unitals in projective planes. N Y etc.: Springer, 2008. 193 p. doi: 10.1007/978-0-387-76366-8 

7.   Assmus E.F., Key J.D. Jr. Designs and their codes. Chap. 8: Steiner systems. Cambridge: Cambridge Univ. Press, 1994. P. 295–316. doi: 10.1017/CBO9781316529836.009 

8.   Махнев A.A., Белоусов И.Н., Падучих Д.В. Конечные геометрии и их автоморфизмы. Новосибирск: Изд-во СО РАН, 2016. 188 c.

9.   Bruck R.H., Ryser H.J. The nonexistence of certain finite projective planes // Canadian J. Math. 1949. Vol. 1. P. 88–93. doi: 10.4153/cjm-1949-009-2 

Поступила 1.08.2019

После доработки 8.11.2019

Принята к публикации 25.11.2019

Белоусов Иван Николаевич
канд. физ.-мат. наук
зав. отделом, старший науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: i_belousov@mail.ru

Махнев Александр Алексеевич
д-р физ.-мат. наук, чл.-корр. РАН
главный науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: makhnev@imm.uran.ru

Ссылка на статью: И.Н. Белоусов, А.А. Махнев. Обратные задачи в теории дистанционно регулярных графов:  двойственные 2-схемы // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 4. С. 44-51.

English

I.N. Belousov, A.A. Makhnev. Inverse problems in the theory of distance-regular graphs: Dual 2-designs

Let $\Gamma$ be a distance-regular graph of diameter 3 with a strongly regular graph $\Gamma_3$. Finding the parameters of $\Gamma_3$ from the intersection array of $\Gamma$ is a direct problem, and finding the intersection array of $\Gamma$ from the parameters of $\Gamma_3$ is its inverse. The direct and inverse problems were solved by A.A. Makhnev and M.S. Nirova: if a graph $\Gamma$ with intersection array $\{k,b_1,b_2;1,c_2,c_3\}$ has eigenvalue $\theta_2=-1$, then the graph complementary to $\Gamma_3$ is pseudo-geometric for $pG_{c_3}(k,b_1/c_2)$. Conversely, if $\Gamma_3$ is a pseudo-geometric graph for $pG_{\alpha}(k,t)$, then $\Gamma$ has intersection array $\{k,c_2t,k-\alpha+1;1,c_2,\alpha\}$, where $k-\alpha+1\le c_2t<k$ and $1\le c_2\le \alpha.$ Distance-regular graphs $\Gamma$ of diameter 3 for which the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudo\-geometric for a net or a generalized quadrangle were studied earlier. In this paper we study intersection arrays of distance-regular graphs $\Gamma$ of diameter 3 for which the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudo-geometric for a dual 2-design $pG_{t+1}(l,t)$. New infinite families of feasible intersection arrays are found: $$\{m(m^2-1),m^2(m-1),m^2;1,1,(m^2-1)(m-1)\} , \{m(m+1),(m+2)(m-1),m+2;1,1,m^2-1\},$$ and $$\{2m(m-1),(2m-1)(m-1),2m-1;1,1,2(m-1)^2\},$$ where $m\equiv\pm 1$ (mod 3). The known families of Steiner 2-designs are unitals, designs corresponding to odd-order projective planes containing a hyperoval, designs of points and lines of projective spaces $PG(n,q)$, and designs of points and lines of affine spaces $AG(n,q)$. We find feasible intersection arrays of a distance-regular graph $\Gamma$ of diameter 3 for which the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudo-geometric for one of the known Steiner 2-designs.

Keywords: distance-regular graph, dual 2-design

Received August 1, 2019

Revised November 8, 2019

Accepted November 25, 2019

Ivan Nikolaevich Belousov, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia,; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: i_belousov@mail.ru

Aleksandr Alekseevich Makhnev, Dr. Phys.-Math. Sci., RAS Corresponding Member, Prof., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620083 Russia, e-mail: makhnev@imm.uran.ru

Cite this article as: I.N.Belousov, A.A.Makhnev. Inverse problems in the theory of distance-regular graphs: Dual 2-designs, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 4, pp. 44–51.