On the nullspace of arc-transitive graphs over finite fields
Primož Potočnik
, Pablo Spiga
and Gabriel Verret
Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, Slovenia
DOI: 10.1007/s10801-011-0340-2
Abstract
Let A be the adjacency matrix of a graph Γ. The nullity of A (that is, the dimension of the nullspace of A), when viewed as a matrix over a field of prime characteristic p, is called the p-nullity of Γ. We present several families of arc-transitive graphs with arbitrarily large p-nullity. We also show that the p-nullity of a vertex-transitive graph of order a power of p is zero, provided that the valency of the graph is coprime to p.
Pages: 389–401
Keywords: arc-transitive graphs; graph-restrictive groups; spectral graph theory; finite fields
Full Text: PDF
References
Alperin, J.L.: Local Representation Theory. Cambridge Studies in Advanced Mathematics, vol.
11. Cambridge University Press, Cambridge (1986) CrossRef Brouwer, A.E., van Eijl, C.A.: On the p-rank of the adjacency matrices of strongly regular graphs. J. Algebr. Comb. 1, 329-346 (1992) CrossRef Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol.
207. Springer, New York (2001) CrossRef Godsil, C., Royle, G.: Chromatic number and the 2-rank of a graph. J. Comb. Theory, Ser. B 81, 142-149 (2001) CrossRef Haemers, W.H.: Matrices for graphs, designs and codes. In: Crnković, D., Tonchev, V. (eds.) Information Security, Coding Theory and Related Combinatorics, pp. 253-277. IOS Press, Amsterdam (2011) Haemers, W.H., Peeters, R., van Rijckevorsel, J.M.: Binary codes of strongly regular graphs. Des. Codes Cryptogr. 17, 187-209 (1999) CrossRef Kovács, I., Malnič, A., Marusič, D., Miklavič, S., Transitive group actions: (im)primitivity and semiregular subgroups. arXiv:math/0701686v1 [math.GR] Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1984) Moisio, M.M.: Kloosterman sums, elliptic curves, and irreducible polynomials with prescribed trace and norm. Acta Arith. 134, 329-349 (2008) CrossRef Potočnik, P., Spiga, P., Verret, G.: An explicit method for constructing arc-transitive graphs with unbounded vertex stabilisers (in preparation) Potočnik, P., Spiga, P., Verret, G.: On graph-restrictive permutation groups. arXiv:1101.5186v2 [math.CO] Rotman, J.J.: Projective planes, graphs, and simple algebras. J. Algebra 155, 267-289 (1993) CrossRef Smith, K.J.C.: On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry. J. Comb. Theory 7, 122-129 (1969) CrossRef Suzuki, M.: Group Theory I. Springer, New York (1982) Tutte, W.T.: A family of cubical graphs. Proc. Camb. Philos. Soc. 43, 459-474 (1947) CrossRef Weiss, R.: Presentation for (G,s)-transitive graphs of small valency. Math. Proc. Philos. Soc. 101, 7-20 (1987) CrossRef
11. Cambridge University Press, Cambridge (1986) CrossRef Brouwer, A.E., van Eijl, C.A.: On the p-rank of the adjacency matrices of strongly regular graphs. J. Algebr. Comb. 1, 329-346 (1992) CrossRef Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol.
207. Springer, New York (2001) CrossRef Godsil, C., Royle, G.: Chromatic number and the 2-rank of a graph. J. Comb. Theory, Ser. B 81, 142-149 (2001) CrossRef Haemers, W.H.: Matrices for graphs, designs and codes. In: Crnković, D., Tonchev, V. (eds.) Information Security, Coding Theory and Related Combinatorics, pp. 253-277. IOS Press, Amsterdam (2011) Haemers, W.H., Peeters, R., van Rijckevorsel, J.M.: Binary codes of strongly regular graphs. Des. Codes Cryptogr. 17, 187-209 (1999) CrossRef Kovács, I., Malnič, A., Marusič, D., Miklavič, S., Transitive group actions: (im)primitivity and semiregular subgroups. arXiv:math/0701686v1 [math.GR] Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1984) Moisio, M.M.: Kloosterman sums, elliptic curves, and irreducible polynomials with prescribed trace and norm. Acta Arith. 134, 329-349 (2008) CrossRef Potočnik, P., Spiga, P., Verret, G.: An explicit method for constructing arc-transitive graphs with unbounded vertex stabilisers (in preparation) Potočnik, P., Spiga, P., Verret, G.: On graph-restrictive permutation groups. arXiv:1101.5186v2 [math.CO] Rotman, J.J.: Projective planes, graphs, and simple algebras. J. Algebra 155, 267-289 (1993) CrossRef Smith, K.J.C.: On the p-rank of the incidence matrix of points and hyperplanes in a finite projective geometry. J. Comb. Theory 7, 122-129 (1969) CrossRef Suzuki, M.: Group Theory I. Springer, New York (1982) Tutte, W.T.: A family of cubical graphs. Proc. Camb. Philos. Soc. 43, 459-474 (1947) CrossRef Weiss, R.: Presentation for (G,s)-transitive graphs of small valency. Math. Proc. Philos. Soc. 101, 7-20 (1987) CrossRef