Browse issues
no. 4
Binomial Cayley graphs and applications to dynamics on finite spaces
Bassols Cornudella, Bernat1; Viganò, Francesco1
1 Department of Mathematics Imperial College London SW7 2AZ London UK
Algebraic Combinatorics, Volume 7 (2024) no. 4, pp. 1197-1223.

Binomial Cayley graphs are obtained by considering the binomial coefficient of the weight function of a given Cayley graph and a natural number. We introduce these objects and study two families: one associated with symmetric groups and the other with powers of cyclic groups. We determine various combinatorial properties of these graphs through the spectral analysis of their adjacency matrices. In the case of symmetric groups, we establish a relation between the multiplicity of the null eigenvalue and longest increasing sub-sequences of permutations by means of the RSK correspondence. Finally, we consider dynamical arrangements of finitely many elements in finite spaces, which we refer to as particle-box systems. We apply the results obtained on binomial Cayley graphs in order to describe their degeneracy.

Received:
Revised:
Accepted:
Published online:
DOI: 10.5802/alco.361
Classification: 05C25, 05E15
Keywords: Cayley graphs, spectral graph theory, representation theory, symmetric group, cyclic group, dynamics on finite spaces

Bassols Cornudella, Bernat 1; Viganò, Francesco 1

1 Department of Mathematics Imperial College London SW7 2AZ London UK
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2024__7_4_1197_0,
     author = {Bassols Cornudella, Bernat and Vigan\`o, Francesco},
     title = {Binomial {Cayley} graphs and applications to dynamics on finite spaces},
     journal = {Algebraic Combinatorics},
     pages = {1197--1223},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {4},
     year = {2024},
     doi = {10.5802/alco.361},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.361/}
}
TY  - JOUR
AU  - Bassols Cornudella, Bernat
AU  - Viganò, Francesco
TI  - Binomial Cayley graphs and applications to dynamics on finite spaces
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 1197
EP  - 1223
VL  - 7
IS  - 4
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.361/
DO  - 10.5802/alco.361
LA  - en
ID  - ALCO_2024__7_4_1197_0
ER  - 
%0 Journal Article
%A Bassols Cornudella, Bernat
%A Viganò, Francesco
%T Binomial Cayley graphs and applications to dynamics on finite spaces
%J Algebraic Combinatorics
%D 2024
%P 1197-1223
%V 7
%N 4
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.361/
%R 10.5802/alco.361
%G en
%F ALCO_2024__7_4_1197_0
Bassols Cornudella, Bernat; Viganò, Francesco. Binomial Cayley graphs and applications to dynamics on finite spaces. Algebraic Combinatorics, Volume 7 (2024) no. 4, pp. 1197-1223. doi : 10.5802/alco.361. https://alco.centre-mersenne.org/articles/10.5802/alco.361/

[1] Babai, László Spectra of Cayley graphs, J. Combin. Theory Ser. B, Volume 27 (1979) no. 2, pp. 180-189 | DOI | MR | Zbl

[2] Baxendale, Peter Brownian motions in the diffeomorphism group. I, Compositio Math., Volume 53 (1984) no. 1, pp. 19-50 | Numdam | MR | Zbl

[3] da Costa, Paulo Henrique; Högele, Michael A.; Ruffino, Paulo R. Stochastic n-point D-bifurcations of stochastic Lévy flows and their complexity on finite spaces, Stoch. Dyn., Volume 22 (2022) no. 7, Paper no. 2240021, 39 pages | DOI | MR | Zbl

[4] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, Volume 57 (1981) no. 2, pp. 159-179 | DOI | MR | Zbl

[5] Godsil, Chris; Royle, Gordon Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001, xx+439 pages | DOI | MR

[6] Knuth, Donald E. Permutations, matrices, and generalized Young tableaux, Pacific J. Math., Volume 34 (1970), pp. 709-727 http://projecteuclid.org/euclid.pjm/1102971948 | DOI | MR | Zbl

[7] Kunita, Hiroshi Stochastic flows and stochastic differential equations, Cambridge Studies in Advanced Mathematics, 24, Cambridge University Press, Cambridge, 1990, xiv+346 pages | MR

[8] Macdonald, Ian G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1995, x+475 pages | DOI | MR

[9] Qian, Chengyang; Wu, Yaokun; Xiong, Yanzhen Inclusion Matrices for Rainbow Subsets, Bull. Iran. Math. Soc., Volume 50 (2023), Paper no. 2, 65 pages | DOI | Zbl

[10] Robinson, G. de B. On the Representations of the Symmetric Group, Amer. J. Math., Volume 60 (1938) no. 3, pp. 745-760 | DOI | MR | Zbl

[11] Rockmore, Dan; Kostelec, Peter; Hordijk, Wim; Stadler, Peter F. Fast Fourier transform for fitness landscapes, Appl. Comput. Harmon. Anal., Volume 12 (2002) no. 1, pp. 57-76 | DOI | MR | Zbl

[12] Roichman, Yuval Characters of the symmetric groups: formulas, estimates and applications, Emerging applications of number theory (Minneapolis, MN, 1996) (IMA Vol. Math. Appl.), Volume 109, Springer, New York, 1999, pp. 525-545 | DOI | MR | Zbl

[13] Sagan, Bruce E.; Stanley, Richard P. Robinson-Schensted algorithms for skew tableaux, J. Combin. Theory Ser. A, Volume 55 (1990) no. 2, pp. 161-193 | DOI | MR | Zbl

[14] Schensted, C. Longest increasing and decreasing subsequences, Canadian J. Math., Volume 13 (1961), pp. 179-191 | DOI | MR | Zbl

[15] Stanley, Richard P. Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, Cambridge, 1999, xii+581 pages | DOI | MR

Cited by Sources: