×

Combinatorics related to Higman’s conjecture. I: Parallelogramic digraphs and dispositions. (English) Zbl 1367.05210

Summary: In this paper we introduce a kind of directed graphs (digraphs) arranged in shifted rows of different lengths, which arise in a natural way related to problems of finding the number of certain families of canonical primitive connected cellular matrices of the \(p\)-Sylow \(\mathfrak{G}_n\) of \(\mathrm{GL}_n(q)\) formed by the upper unitriangular matrices over the finite field with \(q\) elements. Higman’s conjecture states that the number of conjugacy classes of \(\mathfrak{G}_n\) is a polynomial in \(q\). We associate a number, which we call the counter, to each directed graph, which gives additional information about the polynomial structure of the number of conjugacy classes. We focus on a family of digraphs, which we call parallelogramic digraphs, in which we have \(n\) rows of length \(k\) each one shifted one place to the right with respect to the previous one. We give explicit formulas for their counters for \(n\) up to 5. We prove also that the counters satisfy recurrence equations for fixed \(k\) when we vary \(n\), proving thus a fact that was empirically observed by R. H. Harding and A. P. Heinz and proved by P. Sun [Electron. J. Comb. 24, No. 2, Research Paper P2.41, 11 p. (2017; Zbl 1366.05122)] for \(k\) up to 5. When \(n > 1\), this number multiplied by \((q - 1)^{n k - 1}\) corresponds to the cardinality of the family of canonical cellular \(n k \times n k\) matrices over the field \(\mathbb{F}_q\) with \(n\) pivot lines of length \(k\) and exactly \(k - 1\) links connecting the pilots of the lines. We indicate other kinds of digraphs related to Higman’s conjecture that establish lines of future research on this topic.

MSC:

05E15 Combinatorial aspects of groups and algebras (MSC2010)
05C20 Directed graphs (digraphs), tournaments
05E10 Combinatorial aspects of representation theory
05A15 Exact enumeration problems, generating functions

Citations:

Zbl 1366.05122

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] David, H. T., A three-sample Kolmogorov-Smirnov test, Ann. Math. Stat., 29, 842-851 (1958) · Zbl 0089.14901
[2] Dubovichenko, S.; Dzhazairov-Kakhramanov, A. V., Study of the neutron and proton capture reactions \(^{10,11}B\)(n, \(γ),^{11}B\)(p, \(γ),^{14}C\)(p, \(γ)\), and \(^{15}N\)(p, \(γ)\) at thermal and astrophysical energies, Internat. J. Modern Phys. E, 23 (2014)
[3] Frobenius, G., Über die Charaktere der symmetrischen Gruppe, Sitz. König. Preuss. Akad. Wissen., 516-534 (1900) · JFM 31.0129.02
[4] Fujita, S., Stereochemistry and stereoisomerism characterized by the sphericity concept, Chem. Soc. Japan, 74, 1585-1603 (2001)
[5] Harmse, J. A., Pattern matching in column-strict fillings of rectangular arrays (2011), PhD Thesis · Zbl 1265.05038
[6] Haynes, G. C.; Cohen, F. R.; Koditschek, D. E., Gait transitions for quasi-static hexapedal locomotion on level ground, (Springer Tracts in Advanced Robotics, vol. 70 (2011)), 105-121 · Zbl 1250.93086
[7] Higman, G., Enumerating \(p\)-groups. I. Inequalities, Proc. Lond. Math. Soc., 3, 24-30 (1960) · Zbl 0093.02603
[8] King, R. C.; El-Sharkaway, N. G.I., Standard Young tableaux and weight multiplicities of the classical Lie groups, J. Phys. A: Math. Gen., 16, 3153-3177 (1983) · Zbl 0522.22015
[9] Lewis, J. B., Pattern avoidance for alternating permutations and reading words of tableaux (2012), PhD Thesis
[10] Luzanov, A. V., Spin-free quantum chemistry: what one can gain from Fock’s cyclic symmetry, Int. J. Quantum Chem., 111, 4042-4066 (2011)
[11] Neudatchin, V. G.; Struzhko, B. G.; Lebedev, V. M., Supermultiplet potential model of interaction between the lightest clusters and a unified description of various nuclear reactions, Phys. Part. Nucl., 36, 468-497 (2005)
[12] Proctor, R. A., Young tableaux, Gelfand patterns, and branching rules for classical groups, J. Algebra, 164, 299-360 (1994) · Zbl 0809.20030
[13] Schur, I., Über eine Klasse von Matrizen die sich einer gegeben Matrix zuordnen lassen (1901), Inaugural Diss. Berlin · JFM 32.0165.04
[14] Sloane, N. J.A., On-Line Encyclopedia of Integer Sequences · Zbl 1274.11001
[15] Stanley, R. P., Enumerative Combinatorics, vol. 1 (2012), Cambridge University Press · Zbl 1247.05003
[16] Sun, P., Enumeration of standard Young tableaux of shifted strips with constant width (2015)
[17] Vera-López, A.; Arregi, J. M., Classes de conjugaison dans les \(p\)-sous-groupes de Sylow de \(G L(n, q)\), C. R. Acad. Sci. Paris Ser. I, 310, 81-84 (1990) · Zbl 0697.20036
[18] Vera-López, A.; Arregi, J. M., Conjugacy classes in Sylow \(p\)-subgroups of \(G L(n, q)\), II, Proc. Roy. Soc. Edinburgh A, 119, 343-346 (1991) · Zbl 0777.20016
[19] Vera-López, A.; Arregi, J. M., Conjugacy classes in Sylow \(p\)-subgroups of \(G L(n, q)\), J. Algebra, 152, 1-19 (1992) · Zbl 0777.20015
[20] Vera-López, A.; Arregi, J. M., Conjugacy classes in Sylow \(p\)-subgroups of \(G L(n, q)\), IV, Glasg. Math. J., 36, 91-96 (1994) · Zbl 0810.20039
[21] Vera-López, A.; Arregi, J. M., Some algorithms for the calculation of conjugacy classes in the Sylow \(p\)-subgroups of \(G L(n, q)\), J. Algebra, 177, 899-925 (1995) · Zbl 0839.20061
[22] Vera-López, A.; Arregi, J. M.; Vera-López, F. J., On the number of conjugacy classes of the Sylow \(p\)-subgroups of \(G L(n, q)\), Bull. Aust. Math. Soc., 53, 431-439 (1996) · Zbl 0842.20021
[23] Vera-López, A.; Arregi, J. M., Conjugacy classes in unitriangular matrices, Linear Algebra Appl., 370, 85-124 (2003) · Zbl 1045.20045
[24] Vera-López, A.; Arregi, J. M., Computing in unitriangular matrices over finite fields, Linear Algebra Appl., 387, 193-219 (2004) · Zbl 1051.65048
[25] Vera-López, A.; Arregi, J. M.; Ormaetxea, L.; Vera-López, F. J., The exact number of conjugacy classes of the Sylow \(p\)-subgroups of \(GL(n, q)\) modulo \((q - 1)^{13}\), Linear Algebra Appl., 429, 617-624 (2008) · Zbl 1141.20008
[26] Vera-López, A.; García-Sánchez, M. A.; Basova, O.; Vera-López, F. J., A generalization of Catalan numbers, Discrete Math., 332, 23-39 (2014) · Zbl 1298.05028
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.