liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
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
Generalised Ramsey numbers and Bruhat order on involutions
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
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.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2015. , 14 p.
Series
Linköping Studies in Science and Technology. Thesis, ISSN 0280-7971 ; 1734
National Category
Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-123044DOI: 10.3384/lic.diva-123044ISBN: 978-91-7685-892-9 (print)OAI: oai:DiVA.org:liu-123044DiVA: diva2:876270
Presentation
2015-12-17, Nobel (BL32), ingång 23, B-huset, Campus Valla, Linköpings universitet, Linköping, 10:15 (Swedish)
Opponent
Supervisors
Available from: 2015-12-03 Created: 2015-12-03 Last updated: 2015-12-03Bibliographically approved
List of papers
1. Generalised Ramsey numbers for two sets of cycles
Open this publication in new window or tab >>Generalised Ramsey numbers for two sets of cycles
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We determine several generalised Ramsey numbers for two sets Γ1 and Γ2 of cycles, 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 from the 1970s. Notably, including both C3 and C4 in one of the sets, makes very little difference from including only C4. Furthermore, we give a conjecture for the general case. We also describe many (Γ1, Γ2)-avoiding graphs, including a complete characterisation of most (Γ1, Γ2)-critical graphs, i.e., (Γ1, Γ2)-avoiding graphs on R(Γ1, Γ2) − 1 vertices, such that Γ1 or Γ2 contains a cycle of length at most 5. For length 4, this is an easy extension of a recent result of Wu, Sun, and Radziszowski, in which |Γ1| = |Γ2| = 1. For lengths 3 and 5, our results are new even in this special case.

Keyword
Generalised Ramsey number, critical graph, cycle, set of cycles
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-123042 (URN)
Available from: 2015-12-03 Created: 2015-12-03 Last updated: 2015-12-03Bibliographically approved
2. The Bruhat order on conjugation-invariant sets of involutions in the symmetric group
Open this publication in new window or tab >>The Bruhat order on conjugation-invariant sets of involutions in the symmetric group
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 {0, 1, . . . , n}, let

= { In has α fixed points for some α   A}.

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

Place, publisher, year, edition, pages
Springer, 2016
Keyword
Bruhat order, symmetric group, involution, conjugacy class, graded poset, EL-shellability
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-123043 (URN)10.1007/s10801-016-0691-9 (DOI)000387223300002 ()
Note

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

Available from: 2015-12-03 Created: 2015-12-03 Last updated: 2017-12-01Bibliographically approved

Open Access in DiVA

fulltext(326 kB)102 downloads
File information
File name FULLTEXT02.pdfFile size 326 kBChecksum SHA-512
9d64b82d8e018fd0a5467c92503dd842139a102dfcceec874f2655e4d5a1491d15b627f4ae0305ad6764a791f7fc1fa182f77e258627929d43056538adbb4ce2
Type fulltextMimetype application/pdf
omslag(19 kB)9 downloads
File information
File name COVER01.pdfFile size 19 kBChecksum SHA-512
95cf9b7c671fb33fdb30471bae147b08ceada68c15706d9a996c6ca2650a6a7602115383b09b89e34b0a2c4ea59d4f2e337647f2b1b8db2edf09e137b5bb8c6f
Type coverMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Hansson, Mikael

Search in DiVA

By author/editor
Hansson, Mikael
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 102 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 665 hits
CiteExportLink to record
Permanent link

Direct link
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