A permutation group determined by an ordered set

Anders Claesson, Chris D. Godsil, David G. Wagner

Research output: Contribution to journalArticle

3 Citations (Scopus)

Abstract

Let P be a finite ordered set, and let J(P) be the distributive lattice of order ideals of P. The covering relations of J(P) are naturally associated with elements of P; in this way, each element of P defines an involution on the set J(P). Let Γ(P) be the permutation group generated by these involutions. We show that if P is connected then Γ(P) is either the alternating or the symmetric group. We also address the computational complexity of determining which case occurs.
LanguageEnglish
Pages273–279
Number of pages7
JournalDiscrete Mathematics
Volume269
Issue number1-3
Early online date21 May 2003
DOIs
Publication statusPublished - 28 Jul 2003

Fingerprint

Ordered Set
Permutation group
Involution
Computational complexity
Order Ideal
Distributive Lattice
Symmetric group
Finite Set
Computational Complexity
Covering

Keywords

  • ordered set
  • distributive lattice
  • permutation group

Cite this

Claesson, A., Godsil, C. D., & Wagner, D. G. (2003). A permutation group determined by an ordered set. Discrete Mathematics, 269(1-3), 273–279. https://doi.org/10.1016/S0012-365X(03)00094-3
Claesson, Anders ; Godsil, Chris D. ; Wagner, David G. / A permutation group determined by an ordered set. In: Discrete Mathematics. 2003 ; Vol. 269, No. 1-3. pp. 273–279.
@article{d6b611ca35664a63ae36396fefe47d08,
title = "A permutation group determined by an ordered set",
abstract = "Let P be a finite ordered set, and let J(P) be the distributive lattice of order ideals of P. The covering relations of J(P) are naturally associated with elements of P; in this way, each element of P defines an involution on the set J(P). Let Γ(P) be the permutation group generated by these involutions. We show that if P is connected then Γ(P) is either the alternating or the symmetric group. We also address the computational complexity of determining which case occurs.",
keywords = "ordered set, distributive lattice, permutation group",
author = "Anders Claesson and Godsil, {Chris D.} and Wagner, {David G.}",
year = "2003",
month = "7",
day = "28",
doi = "10.1016/S0012-365X(03)00094-3",
language = "English",
volume = "269",
pages = "273–279",
journal = "Discrete Mathematics",
issn = "0012-365X",
number = "1-3",

}

Claesson, A, Godsil, CD & Wagner, DG 2003, 'A permutation group determined by an ordered set' Discrete Mathematics, vol. 269, no. 1-3, pp. 273–279. https://doi.org/10.1016/S0012-365X(03)00094-3

A permutation group determined by an ordered set. / Claesson, Anders; Godsil, Chris D.; Wagner, David G.

In: Discrete Mathematics, Vol. 269, No. 1-3, 28.07.2003, p. 273–279.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A permutation group determined by an ordered set

AU - Claesson, Anders

AU - Godsil, Chris D.

AU - Wagner, David G.

PY - 2003/7/28

Y1 - 2003/7/28

N2 - Let P be a finite ordered set, and let J(P) be the distributive lattice of order ideals of P. The covering relations of J(P) are naturally associated with elements of P; in this way, each element of P defines an involution on the set J(P). Let Γ(P) be the permutation group generated by these involutions. We show that if P is connected then Γ(P) is either the alternating or the symmetric group. We also address the computational complexity of determining which case occurs.

AB - Let P be a finite ordered set, and let J(P) be the distributive lattice of order ideals of P. The covering relations of J(P) are naturally associated with elements of P; in this way, each element of P defines an involution on the set J(P). Let Γ(P) be the permutation group generated by these involutions. We show that if P is connected then Γ(P) is either the alternating or the symmetric group. We also address the computational complexity of determining which case occurs.

KW - ordered set

KW - distributive lattice

KW - permutation group

U2 - 10.1016/S0012-365X(03)00094-3

DO - 10.1016/S0012-365X(03)00094-3

M3 - Article

VL - 269

SP - 273

EP - 279

JO - Discrete Mathematics

T2 - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -