The distinguishing number of the direct product and wreath product action

被引:23
作者
Chan, Melody [1 ]
机构
[1] Univ Cambridge, Cambridge, England
[2] Univ Minnesota Duluth Res Experience Undergrad, Duluth, MN USA
[3] Yale Univ, New Haven, CT 06520 USA
基金
美国国家科学基金会;
关键词
symmetry group; symmetry breaking; distinguishing number; wreath product; direct product;
D O I
10.1007/s10801-006-0006-7
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a group acting faithfully on a set X. The distinguishing number of the action of G on X, denoted D-G(X), is the smallest number of colors such that there exists a coloring of X where no nontrivial group element induces a color-preserving permutation of X. In this paper, we consider the distinguishing number of two important product actions, the wreath product and the direct product. Given groups G and H acting on sets X and Y respectively, we characterize the distinguishing number of the wreath product G (Y) H in terms of the number of distinguishing colorings of X with respect to G and the distinguishing number of the action of H on Y. We also prove a recursive formula for the distinguishing number of the action of the Cartesian product of two symmetric groups S-m x S-n on [m] x [n].
引用
收藏
页码:331 / 345
页数:15
相关论文
共 13 条
[1]  
Albertson M.O., 1996, ELECT J COMBIN, V3
[2]  
ALBERTYN C, 1996, AGENDA, V30, P6
[3]   The distinguishing number of the hypercube [J].
Bogstad, B ;
Cowen, LJ .
DISCRETE MATHEMATICS, 2004, 283 (1-3) :29-35
[4]  
Cameron P. J., 1995, HDB COMBINATORICS, V1, P611
[5]  
CHAN M, IN PRESS ELECT J COM
[6]  
CHAN M, DISTINGUISHING NUMBE
[7]  
CHENG CT, 1999, THESIS J HOPKINS U
[8]  
DOBSON E, UNPUB AUTOMORPHISM G
[9]  
HALL M, 1959, THEORY GROUPS
[10]   LEXICOGRAPHIC PRODUCT OF GRAPHS [J].
HEMMINGER, RL .
DUKE MATHEMATICAL JOURNAL, 1966, 33 (03) :499-+