Málstofa í stærðfræði
Fyrirlesari: Duncan Alexander Adamson, Háskólinn í Reykjavík
Titill: Combinatorial Structures for Crystal Structure Prediction
Staðsetning: Tg-227 í Tæknigarði.
Tímasetning: Fimmtudaginn 17. mars 2022, kl. 10:30.
Ágrip:
Crystals are a fundamental form of matter defined by a periodic structure with a high level of symmetry. The relatively small period of crystals allows the global properties of the structure to be predicted from a relatively small amount of information. Despite the advantages crystals have over other forms of matter, the problem of predicting the structure of a crystal has remained a major open problem spanning materials science, chemistry, and computer science.
In this talk we present a set of multidimensional necklaces, a multidimensional generalisation of combinatorial necklaces, designed to capture the symmetry within the translational space that is inherent to crystal structures. Along with the motivation and definition, we see how that several classical problems for one dimensional necklaces can be generalised to the multidimensional setting, including the problems of:
* Counting (determining the number of necklaces of a given size over a given alphabet)
* Generating (outputting every necklace of a given size over a given alphabet under some order)
* Ranking (determining the number of necklaces of a given size over a given alphabet that are smaller than some input necklace)
* Unranking (output the necklace with a given rank within the set of necklaces of some given size over a given alphabet)
Further, we provide efficient algorithms for solving each of these problems.
Fyrirlesari: Giulio Cerbai, Raunvísindastofnun Háskóla Íslands
Titill: A combinatorial theory of transport of patterns
Staðsetning: Tg-227 í Tæknigarði
Tími: Fimmtudagur 24.febrúar kl. 10:30 / 3. mars kl. 10:30
Ágrip:
Combinatorics study enumerative, algebraic and geometric properties of families of discrete objects. Some of them can be equipped with a notion of pattern containment. The resulting posets have been extensively studied, but few results that link different structures are known. Our work aims to develop a unifying theory of transport of patterns capable of handling various families of objects. By revealing links between combinatorial structures and providing new enumerative results, this would improve our global understanding of pattern avoidance.
The first part of this seminar is devoted to a gentle introduction to combinatorics and, more specifically, permutation patterns. We provide the necessary background and define a hierarchy of endofunctions that embody the structures covered by our work. We then state the two fundamental aspects to transport of patterns: (i) defining suitable pattern-transporting maps between sets of endofunctions; (ii) understanding how such maps behave with respect to pattern containment. Finally we introduce the Burge transposition on biwords and show how this operation can be used to obtain a transport theorem for (modified) ascent sequences and Fishburn permutations.
In the second part of this seminar, we show numerous examples and applications of the proposed framework, as well as some related research directions. We also show how the Burge transpose can be used to provide a generalization of the Eulerian polynomial over Cayley permutations.
Málstofa í stærðfræði
Fyrirlesari: Thomas Selig, University of Strathclyde
Titill: EW-tableaux, permutations and recurrent configurations of the sandpile model on Ferrers graphs.
Staðsetning: VRII, V-147
Tími: Miðvikudagur 27. júní kl. 10:30
Ágrip:
The Abelian sandpile model (ASM) is a dynamic process on a graph. More specifically, it is a Markov chain on the set of configurations on that graph. Of particular interest are the recurrent configurations, i.e. those that appear infinitely often in the long-time running of the model. We study the ASM on Ferrers graphs, a class of bipartite graphs in one-to-one correspondence with Ferrers diagrams. We show that minimal recurrent configurations are in one-to-one correspondence with a set of certain 0/1 fillings of the Ferrers diagrams introduced by Ehrenborg and van Willigensburg. We refer to these fillings as EW-tableaux, and establish a bijection between the set of EW-tableaux of a given Ferrers diagram and a set of permutations whose descent bottoms are given by the shape of the Ferrers diagram. This induces a bijection between these permutations and minimal recurrent configurations of the ASM. We enrich this bijection to encode all recurrent configurations, via a decoration of the corresponding permutation. We also show that the set of recurrent configurations over all Ferrers graphs of a given size are in bijection with the set of alternating trees of that size.
Málstofa í stærðfræði
Fyrirlesari: Anders Claesson
Titill: Interval orders via combinatorial species and ballot matrices
Staðsetning: V-157, VRII.
Tími: Föstudagur 5. febrúar kl. 13:20.
Ágrip:
We give a brief introduction to (some aspects of) combinatorial species.
Using this framework we introduce ballot matrices and present a subset
of them that is in bijection with labeled interval orders. Such ballot
matrices decompose naturally into a pair of permutations with related
properties, which leads to a new formula for the number of labeled
interval orders.
This talk is based on joint work with Stuart Hannah.
Málstofa í stærðfræði
Fyrirlesarar: Bjarni Jens Kristinsson, Háskóla Íslands, og Henning Úlfarsson, Háskólanum í Reykjavík
Titill: Occurrence graphs of patterns in permutations
Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 4. júní, klukkan 15:00-16:00.
Ágrip:
This paper is based on a generalisation of the idea behind the proof of the Simultaneous Shading Lemma by Claesson et al. (2014). We define the occurrence graph \(G_p(\pi)\) of a pattern \(p\) in a permutation \(\pi\) as the graph with the occurrences of \(p\) in \(\pi\) as vertices and edges between the vertices if the occurrences differ by exactly one element. We study the general properties of the occurrence graphs and some interesting extreme cases. The main theorem in this paper is that every hereditary property of graphs produces a permutation class.
Málstofa í stærðfræði
Fyrirlesari: Henning Úlfarsson, Háskólinn í Reykjavík
Titill: Struct: An algorithm for guessing the structure and enumeration of permutation sets
Staðsetning: Naustið, Endurmenntun (hér)
Tími: Fimmtudagur 22. janúar, frá 15:00-16:00.
Höfundar:
Michael Albert, Anders Claesson, Bjarki Gudmundsson, Henning Ulfarsson
Ágrip:
Struct is an algorithm being developed by the authors to
guess the structure of a set of permutations. In some cases the structure
discovered is sufficient to infer the generating function of the set and
provides an enumeration of the permutations by length. A preliminary version of
the algorithm will be presented and applied to several sets of permutations.
This research is funded by the Icelandic Research Fund, Grant no.~141761-051
