Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

descriptionPublicationkeyboard_double_arrow_right Article , Preprint 01 Jul 2020Embargo end date: 01 Jan 2019 Spain English Publisher:Elsevier BVJournal:Linear Algebra and its Applications, volume 597, pages 94-112 (issn: 0024-3795,

Copyright policy )Funded by:EC | CONNECT

Authors: Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel;

doi: 10.1016/j.laa.2020.03.015 , 10.48550/arxiv.1906.05851

arXiv: 1906.05851

handle: 2117/330465 , 10459.1/68317

Spectra and eigenspaces from regular partitions of Cayley (di)graphs of permutation groups

- Summary
- Subjects
- Related research
  (5)
- Metrics

Abstract

In this paper, we present a method to obtain regular (or equitable) partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups on $n$ letters. We prove that every partition of the number $n$ gives rise to a regular partition of the Cayley graph. By using representation theory, we also obtain the complete spectra and the eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide a method to find all the eigenvalues and eigenvectors of such (di)graphs, based on their irreducible representations. As examples, we apply this method to the pancake graphs $P(n)$ and to a recent known family of mixed graphs $Γ(d,n,r)$ (having edges with and without direction). As a byproduct, the existence of perfect codes in $P(n)$ allows us to give a lower bound for the multiplicity of its eigenvalue $-1$.

Country

Spain

Related Organizations

Universitat Polite`cnica de Catalunya
Spain
University of Lleida
Spain
Universitat Politècnica de Catalunya
Spain

Keywords

Eigenvalues, singular values, and eigenvectors, Regular partition, Directed graphs (digraphs), tournaments, :20 Group theory and generalizations::20C Representation theory of groups [Classificació AMS], Classificació AMS::05 Combinatorics::05C Graph theory, spectrum, :Matemàtiques i estadística::Àlgebra::Teoria de grups [Àrees temàtiques de la UPC], Classificació AMS::15 Linear and multilinear algebra; matrix theory, Graphs and linear algebra (matrices, eigenvalues, etc.), Classificació AMS::20 Group theory and generalizations::20C Representation theory of groups, regular partition, Grups, Teoria de, representation theory, Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra::Teoria de grups, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra::Àlgebra lineal i multilineal, symmetric group, lifted graph, Combinatorics (math.CO), 05C50, Symmetric group, Algebras, Linear, :Matemàtiques i estadística::Àlgebra::Àlgebra lineal i multilineal [Àrees temàtiques de la UPC], Lifted (di)graph, Algebras, Linear, Grafs, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), matrix theory, Spectrum, FOS: Mathematics, Mathematics - Combinatorics, lifted digraph, New mixed graph, Teoria de, Grafs, Teoria de, :15 Linear and multilinear algebra [Classificació AMS], Grups, Representation theory, Representations of finite symmetric groups, new mixed graph, Classificació AMS::15 Linear and multilinear algebra, Graph theory, Pancake graph, pancake graph, Group theory, Àlgebra lineal, :05 Combinatorics::05C Graph theory [Classificació AMS], :Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs [Àrees temàtiques de la UPC]

5 Research products, page 1 of 1

Identifying codes in line digraphs
2020IsAmongTopNSimilarDocuments
Spectra and eigenspaces of arbitrary lifts of graphs
2021IsAmongTopNSimilarDocuments
Bipartite biregular Moore graphs
2021IsAmongTopNSimilarDocuments
New results for the Mondrian art problem
2021IsAmongTopNSimilarDocuments
New cyclic Kautz digraphs with optimal diameter
2021IsAmongTopNSimilarDocuments

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	4
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average