liu.seSearch for publications in DiVA
Change search

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf
The Bruhat order on conjugation-invariant sets of involutions in the symmetric group
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
2016 (English)In: Journal of Algebraic Combinatorics, ISSN 0925-9899, E-ISSN 1572-9192, Vol. 44, no 4, 849-862 p.Article in journal (Refereed) Published
##### Abstract [en]

Let In be the set of involutions in the symmetric group Sn, and for A $\small\subseteq$ {0, 1, . . . , n}, let

$\small F _{n}^A$ = {$\sigma$$\in$ In$\sigma$ has α fixed points for some α $\in$  A}.

We give a complete characterisation of the sets A for which $\small F _{n}^A$, with the order induced by the Bruhat order on Sn, is a graded poset. In particular, we prove that $\small F _{n}^\lbrace^1^\rbrace$ (i.e., the set of involutions with exactly one fixed point) is graded, which settles a conjecture of Hultman in the affirmative. When $\small F _{n}^A$ is graded, we give its rank function. We also give a short, new proof of the EL-shellability of $\small F _{n}^\lbrace^0^\rbrace$ (i.e., the set of fixed-point-free involutions), recently proved by Can, Cherniavsky, and Twelbeck.

##### Place, publisher, year, edition, pages
Springer, 2016. Vol. 44, no 4, 849-862 p.
##### Keyword [en]
Bruhat order, symmetric group, involution, conjugacy class, graded poset, EL-shellability
Mathematics
##### Identifiers
ISI: 000387223300002OAI: oai:DiVA.org:liu-123043DiVA: diva2:876258
##### Note

At the time for thesis presentation publication was in status: Manuscript

Available from: 2015-12-03 Created: 2015-12-03 Last updated: 2016-12-09Bibliographically approved
##### In thesis
1. Generalised Ramsey numbers and Bruhat order on involutions
Open this publication in new window or tab >>Generalised Ramsey numbers and Bruhat order on involutions
2015 (English)Licentiate thesis, comprehensive summary (Other academic)
##### Abstract [en]

This thesis consists of two papers within two different areas of  combinatorics.

Ramsey theory is a classic topic in graph theory, and Paper A deals with two of its most fundamental problems: to compute Ramsey numbers and to characterise critical graphs. More precisely, we study generalised Ramsey numbers for two sets Γ1 and Γ2 of cycles. We determine, in particular, all generalised Ramsey numbers R(Γ1, Γ2) such that Γ1 or Γ2 contains a cycle of length at most 6, or the shortest cycle in each set is even. This generalises previous results of Erdös, Faudree, Rosta, Rousseau, and Schelp. Furthermore, we give a conjecture for the general case. We also characterise many (Γ1, Γ2)-critical graphs. As special cases, we obtain complete characterisations of all (Cn,C3)-critical graphs for n ≥ 5, and all (Cn,C5)-critical graphs for n ≥ 6.

In Paper B, we study the combinatorics of certain partially ordered sets. These posets are unions of conjugacy classes of involutions in the symmetric group Sn, with the order induced by the Bruhat order on Sn. We obtain a complete characterisation of the posets that are graded. In particular, we prove that the set of involutions with exactly one fixed point is graded, which settles a conjecture of Hultman in the affirmative. When the posets are graded, we give their rank functions. We also give a short, new proof of the EL-shellability of the set of fixed-point-free involutions, recently proved by Can, Cherniavsky, and Twelbeck.

##### Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1734
Mathematics
##### Identifiers
urn:nbn:se:liu:diva-123044 (URN)10.3384/lic.diva-123044 (DOI)978-91-7685-892-9 (ISBN)
##### Presentation
2015-12-17, Nobel (BL32), ingång 23, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (Swedish)
##### Supervisors
Available from: 2015-12-03 Created: 2015-12-03 Last updated: 2015-12-03Bibliographically approved

#### Open Access in DiVA

No full text

Publisher's full text

#### Search in DiVA

Hansson, Mikael
##### By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
##### In the same journal
Journal of Algebraic Combinatorics
Mathematics

#### Altmetric score

Total: 90 hits

Cite
Citation style
• apa
• harvard1
• ieee
• modern-language-association-8th-edition
• vancouver
• oxford
• Other style
More styles
Language
• de-DE
• en-GB
• en-US
• fi-FI
• nn-NO
• nn-NB
• sv-SE
• Other locale
More languages
Output format
• html
• text
• asciidoc
• rtf