Inverse Problems in the Theory of Distance-Regular Graphs: Dual 2-Designs

I. N. Belousov ; A. A. Makhnev

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 4, pp. 44-51

Résumé

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$ and $1\le c_2\le \alpha$. Distance-regular graphs $\Gamma$ of diameter 3 such that the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudogeometric 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 such that the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudogeometric 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 projective planes of even order 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 such that the graph $\Gamma_3$ ($\bar \Gamma_3$) is pseudogeometric for one of the known Steiner 2-designs.

Détail

Keywords: distance-regular graph, dual 2-design.

Bibliographie

[1] Brouwer A.E., Cohen A.M., Neumaier A., Distance-regular graphs, Springer-Verlag, Berlin; Heidelberg; N Y, 1989, 495 pp. | MR | Zbl

[2] Koolen J.H., Park J., “Shilla distance-regular graphs”, Europ. J. Comb., 31 (2010), 2064–2073 | DOI | MR | Zbl

[3] Jurisic A., Koolen J., “Krein parameters and antipodal tight graphs with diameter 3 and 4”, Discrete Math., 244 (2002), 181–202 | DOI | MR | Zbl

[4] Bang S., Koolen J., “Distance-regular graphs of diameter 3 having eigenvakue -1”, Linear Algebra Appl., 531 (2017), 38–53 | DOI | MR | Zbl

[5] Makhnev A.A., Nirova M.S., “Distance-regular Shilla graphs with $b2 = c2$”, Math. Notes, 103:5 (2018), 780–792 | DOI | MR | Zbl

[6] Barwick S., Ebert G., Unitals in projective planes, Springer, N Y etc., 2008, 193 pp. | DOI | MR | Zbl

[7] Assmus E.F., Key J.D. Jr., “Chap. 8: Steiner systems”, Designs and their codes, Cambridge Univ. Press, Cambridge, 1994, 295–316 | MR

[8] Makhnev A.A., Belousov I.N., Paduchikh D.V., Konechnye geometrii i ikh avtomorfizmy, Izd-vo SO RAN, Novosibirsk, 2016, 188 pp.

[9] Bruck R.H., Ryser H.J., “The nonexistence of certain finite projective planes”, Canadian J. Math., 1 (1949), 88–93 | DOI | MR | Zbl