×

Using a Grassmann graph to recover the underlying projective geometry. (English) Zbl 07906414

Summary: Let \(n\), \(k\) denote integers with \(n>2k\geq 6\). Let \(\mathbb{F}_q\) denote a finite field with \(q\) elements, and let \(V\) denote a vector space over \(\mathbb{F}_q\) that has dimension \(n\). The projective geometry \(P_q(n)\) is the partially ordered set consisting of the subspaces of \(V\); the partial order is given by inclusion. For the Grassmann graph \(J_q(n,k)\) the vertex set consists of the \(k\)-dimensional subspaces of \(V\). Two vertices of \(J_q(n,k)\) are adjacent whenever their intersection has dimension \(k-1\). The graph \(J_q(n,k)\) is known to be distance-regular. Let \(\partial\) denote the path-length distance function of \(J_q(n,k)\). Pick two vertices \(x, y\) in \(J_q(n,k)\) such that \(1<\partial (x,y)<k\). The set \(P_q(n)\) contains the elements \(x,y,x\cap y,x+y\). In our main result, we describe \(x\cap y\) and \(x+y\) using only the graph structure of \(J_q(n,k)\). To achieve this result, we make heavy use of the Euclidean representation of \(J_q(n,k)\) that corresponds to the second largest eigenvalue of the adjacency matrix.

MSC:

05E30 Association schemes, strongly regular graphs
05C12 Distance in graphs
51E20 Combinatorial structures in finite projective spaces

References:

[1] Brouwer, AE; Cohen, AM; Neumaier, A., Distance-Regular Graphs, 1989, Berlin: Springer, Berlin · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2
[2] Egawa, Y., Characterization of \(H(n, q)\) by the parameters, J. Combin. Theory Ser. A, 31, 108-125, 1981 · Zbl 0472.05056 · doi:10.1016/0097-3165(81)90007-8
[3] Terwilliger, P., Kite-free distance-regular graphs, Eur. J. Combin., 16, 405-414, 1995 · Zbl 0829.05059 · doi:10.1016/0195-6698(95)90020-9
[4] Ivanov, AA; Shpectorov, SV, A characterization of the association schemes of Hermitian forms, J. Math. Soc. Jpn., 43, 25-48, 1991 · Zbl 0755.05099 · doi:10.2969/jmsj/04310025
[5] Moon, A., Characterization of the odd graphs \(O_k\) by parameters, Discret. Math., 42, 91-97, 1982 · Zbl 0494.05035 · doi:10.1016/0012-365X(82)90057-7
[6] Chang, LC, The uniqueness and non-uniqueness of the triangular association schemes, Sci. Record. Math. New Ser., 3, 604-613, 1959 · Zbl 0089.15102
[7] Terwilliger, P., The Johnson graph \(J(d, r)\) is unique if \((d, r) \ne (2, 8)\), Discret. Math., 58, 175-189, 1986 · Zbl 0587.05038 · doi:10.1016/0012-365X(86)90160-3
[8] Huang, T., A characterization of the association schemes of bilinear forms, Eur. J. Combin., 8, 159-173, 1987 · Zbl 0675.05064 · doi:10.1016/S0195-6698(87)80007-0
[9] Cuypers, H., Two remarks on Huang’s characterization of the bilinear forms graphs, Eur. J. Combin., 13, 33-37, 1992 · Zbl 0773.05077 · doi:10.1016/0195-6698(92)90065-8
[10] Metsch, K., On a characterization of bilinear forms graphs, Eur. J. Combin., 20, 293-306, 1999 · Zbl 0923.05050 · doi:10.1006/eujc.1998.0280
[11] Gavrilyuk, AL; Koolen, JH, A characterization of the graphs of \((d\times d)\)-bilinear forms over \({\mathbb{F} }_2\), Combinatorica, 39, 289-321, 2019 · Zbl 1438.05241 · doi:10.1007/s00493-017-3573-4
[12] Metsch, K., A characterization of Grassmann graphs, Eur. J. Combin., 16, 639-644, 1995 · Zbl 0836.05066 · doi:10.1016/0195-6698(95)90045-4
[13] van Dam, ER; Koolen, JH, A new family of distance-regular graphs with unbounded diameter, Invent. Math., 162, 189-193, 2005 · Zbl 1074.05092 · doi:10.1007/s00222-005-0442-3
[14] Gavrilyuk, A.L., Koolen, J.H.: On a characterization of the Grassmann graphs. arXiv:1806.02652v1 (2018)
[15] Axler, S., Linear Algebra Done Right, 1997, New York: Springer, New York · Zbl 0886.15001 · doi:10.1007/b97662
[16] Terwilliger, P.: Online course notes for algebraic graph theory. Spring. https://people.math.wisc.edu/ pmterwil (2022)
[17] Nomura, K.; Terwilliger, P., Krawtchouk polynomials, the Lie algebra \(\mathfrak{sl}_2\), and Leonard pairs, Linear Algebra Appl., 437, 345-375, 2012 · Zbl 1261.33001 · doi:10.1016/j.laa.2012.02.006
[18] Terwilliger, P., A new inequality for distance-regular graphs, Discret. Math., 137, 319-332, 1995 · Zbl 0814.05074 · doi:10.1016/0012-365X(93)E0170-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.