## Group-theoretic generalisations of vertex and edge connectivities

HTML articles powered by AMS MathViewer

- by Yinan Li and Youming Qiao PDF
- Proc. Amer. Math. Soc.
**148**(2020), 4679-4693 Request permission

## Abstract:

Let $p$ be an odd prime. Let $P$ be a finite $p$-group of class $2$ and exponent $p$, whose commutator quotient $P/[P,P]$ is of order $p^n$. We define two parameters for $P$ related to central decompositions. The first parameter, $\kappa (P)$, is the smallest integer $s$ for the existence of a subgroup $S$ of $P$ satisfying (1) $S\cap [P,P]=[S,S]$, (2) $|S/[S,S]|=p^{n-s}$, and (3) $S$ is centrally decomposable. The second parameter, $\lambda (P)$, is the smallest integer $s$ for the existence of a central subgroup $N$ of order $p^s$, such that $P/N$ is centrally decomposable.

While defined in purely group-theoretic terms, these two parameters generalise, respectively, the vertex and edge connectivities of graphs: For a simple undirected graph $G$, through the classical procedures of Baer (Trans. Amer. Math. Soc., 1938), Tutte (J. Lond. Math. Soc., 1947) and Lovász (B. Braz. Math. Soc., 1989), there is a $p$-group $P_G$ of class $2$ and exponent $p$ that is naturally associated with $G$. Our main results show that the vertex connectivity $\kappa (G)$ equals $\kappa (P_G)$, and the edge connectivity $\lambda (G)$ equals $\lambda (P_G)$.

We also discuss the relation between $\kappa (P)$ and $\lambda (P)$ for a general $p$-group $P$ of class $2$ and exponent $p$, as well as the computational aspects of these parameters. In particular, our main results imply that the $p$-group central decomposition algorithm of Wilson (J. Algebra and J. of Group Theory, 2009) can be used to solve the graph connectivity problem.

## References

- J. L. Alperin,
*Large Abelian subgroups of $p$-groups*, Trans. Amer. Math. Soc.**117**(1965), 10–20. MR**170946**, DOI 10.1090/S0002-9947-1965-0170946-4 - László Babai, Paul Erdős, and Stanley M. Selkow,
*Random graph isomorphism*, SIAM J. Comput.**9**(1980), no. 3, 628–635. MR**584517**, DOI 10.1137/0209047 - Reinhold Baer,
*Groups with abelian central quotient group*, Trans. Amer. Math. Soc.**44**(1938), no. 3, 357–386. MR**1501972**, DOI 10.1090/S0002-9947-1938-1501972-1 - Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun,
*From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: Another bridge between graphs and alternating matrix spaces*, 11th Innovations in Theoretical Computer Science Conference, ITCS, 2020, pp. 8:1–8:48. - Joe Buhler, Ranee Gupta, and Joe Harris,
*Isotropic subspaces for skewforms and maximal abelian subgroups of $p$-groups*, J. Algebra**108**(1987), no. 1, 269–279. MR**887208**, DOI 10.1016/0021-8693(87)90138-4 - W. Burnside,
*On Some Properties of Groups Whose Orders are Powers of Primes*, Proc. London Math. Soc. (2)**11**(1913), 225–245. MR**1577221**, DOI 10.1112/plms/s2-11.1.225 - Reinhard Diestel,
*Graph theory*, 5th ed., Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017. MR**3644391**, DOI 10.1007/978-3-662-53622-3 - Xiaoyu He and Youming Qiao,
*On the Baer-Lovász-Tutte construction of groups from graphs: isomorphism types and homomorphism notions*, arXiv:2003.07200 (2020). - Hermann Heineken and Hans Liebeck,
*The occurrence of finite groups in the automorphism group of nilpotent groups of class $2$*, Arch. Math. (Basel)**25**(1974), 8–16. MR**349844**, DOI 10.1007/BF01238631 - Graham Higman,
*Enumerating $p$-groups. I. Inequalities*, Proc. London Math. Soc. (3)**10**(1960), 24–30. MR**113948**, DOI 10.1112/plms/s3-10.1.24 - Wilfrid Hodges,
*Model theory*, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR**1221741**, DOI 10.1017/CBO9780511551574 - Gábor Ivanyos and Youming Qiao,
*Algorithms based on $*$-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing*, SIAM J. Comput.**48**(2019), no. 3, 926–963. MR**3945816**, DOI 10.1137/18M1165682 - Serge Lang,
*Algebra*, 3rd ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002. MR**1878556**, DOI 10.1007/978-1-4613-0041-0 - Yinan Li and Youming Qiao,
*Linear algebraic analogues of the graph isomorphism problem and the Erdős-Rényi model (extended abstract)*, 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017, IEEE Computer Soc., Los Alamitos, CA, 2017, pp. 463–474. MR**3734252** - László Lovász,
*On determinants, matchings and random algorithms*, Fundamentals of Computation Theory, 1979, pp. 565–574. - László Lovász,
*Singular spaces of matrices and their application in combinatorics*, Bol. Soc. Brasil. Mat. (N.S.)**20**(1989), no. 1, 87–99. MR**1129080**, DOI 10.1007/BF02585470 - Avinoam Mann,
*Elements of minimal breadth in finite $p$-groups and Lie algebras*, J. Aust. Math. Soc.**81**(2006), no. 2, 209–214. MR**2267792**, DOI 10.1017/S1446788700015834 - Alan H. Mekler,
*Stability of nilpotent groups of class $2$ and prime exponent*, J. Symbolic Logic**46**(1981), no. 4, 781–788. MR**641491**, DOI 10.2307/2273227 - A. Yu. Ol’shanskii,
*The number of generators and orders of abelian subgroups of finite $p$-groups*, Mathematical notes of the Academy of Sciences of the USSR**23**(1978), no. 3, 183–185. - Tobias Rossmann and Christopher Voll,
*Groups, graphs, and hypergraphs: Average sizes of kernels of generic matrices with support constraints*, arXiv:1908.09589 (2019). - Michio Suzuki,
*Group theory. I*, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 247, Springer-Verlag, Berlin-New York, 1982. Translated from the Japanese by the author. MR**648772** - W. T. Tutte,
*The factorization of linear graphs*, J. London Math. Soc.**22**(1947), 107–111. MR**23048**, DOI 10.1112/jlms/s1-22.2.107 - W. T. Tutte,
*Connectivity in graphs*, Mathematical Expositions, No. 15, University of Toronto Press, Toronto, Ont.; Oxford University Press, London, 1966. MR**0210617** - Michael Vaughan-Lee,
*Groups of order $p^8$ and exponent $p$*, Int. J. Group Theory**4**(2015), no. 4, 25–42. MR**3416635** - James B. Wilson,
*Decomposing $p$-groups via Jordan algebras*, J. Algebra**322**(2009), no. 8, 2642–2679. MR**2559855**, DOI 10.1016/j.jalgebra.2009.07.029 - James B. Wilson,
*Finding central decompositions of $p$-groups*, J. Group Theory**12**(2009), no. 6, 813–830. MR**2582050**, DOI 10.1515/JGT.2009.015

## Additional Information

**Yinan Li**- Affiliation: Centrum Wiskunde and Informatica and QuSoft, Science Park 123, 1098XG Amsterdam, Netherlands
- MR Author ID: 1240769
- ORCID: 0000-0002-5456-1319
- Email: Yinan.Li@cwi.nl
**Youming Qiao**- Affiliation: Center for Quantum Software and Information, University of Technology, Sydney, Ultimo NSW 2007, Australia
- MR Author ID: 938330
- ORCID: 0000-0003-4334-1449
- Email: Youming.Qiao@uts.edu.au
- Received by editor(s): October 30, 2019
- Received by editor(s) in revised form: March 24, 2020
- Published electronically: August 14, 2020
- Additional Notes: The first author was partially supported by ERC Consolidator Grant 615307-QPROGRESS.

The second author was partially supported by the Australian Research Council DP200100950. - Communicated by: Martin Liebeck
- © Copyright 2020 American Mathematical Society
- Journal: Proc. Amer. Math. Soc.
**148**(2020), 4679-4693 - MSC (2010): Primary 20D15, 05C40, 15A69
- DOI: https://doi.org/10.1090/proc/15184
- MathSciNet review: 4143386