Skip to content

Research

During my ongoing studies I’ve done some research on various topics. Below are papers that I’ve coauthored.

2017

Enumerating permutations sortable by k passes through a pop-stack
arXiv: 1710.04978
Authors: Anders Claesson, Bjarki Ágúst Guðmundsson

In an exercise in the first volume of his famous series of books, Knuth considered sorting permutations by passing them through a stack. He noted that, out of the n! permutations on n elements, C_n of them can be sorted by a single pass through a stack, where C_n is the n-th Catalan number. Many variations of this exercise have since been considered, including allowing multiple passes through the stack and using different data structures. West classified the permutations that are sortable by 2 passes through a stack, and a formula for the enumeration was later proved by Zeilberger. The permutations sortable by 3 passes through a stack, however, have yet to be enumerated. We consider a variation of this exercise using pop-stacks. For any fixed k, we give an algorithm to derive a generating function for the permutations sortable by k passes through a pop-stack. Recently the generating function for k=2 was given by Pudwell and Smith (the case k=1 being trivial). Running our algorithm on a computer cluster we derive the generating functions for k at most 6. We also show that, for any k, the generating function is rational.

See source code at GitHub.

Presented at Math Colloquium, University of Iceland, Iceland, September 2017 by Bjarki Ágúst Guðmundsson (PDF, Announcement)
Presented at Stærðfræði á Íslandi, Iceland, October 2017 by Bjarki Ágúst Guðmundsson (PDF)
Referenced on OEIS

Formalizing the translation method in Agda
hdl: 1946/28736
Authors: Bjarki Ágúst Guðmundsson (MSc thesis)

If P and Q are sets of combinatorial objects, the translation method, introduced by Wood and Zeilberger (2009), allows one to turn an algebraic proof of the identity |P| = |Q| into a bijection between P and Q. We give a formalized implementation of the translation method in the programming language Agda. In contrast to the implementation previously given by Wood and Zeilberger, the bijections produced by our implementation are formally verified, making our implementation more robust. We also take advantage of the fact that Agda is a proof assistant, allowing users of our implementation to use the existing facilities provided by Agda for developing proofs. In particular, converting an existing algebraic proof for use in our implementation is often straightforward.

We prove that the expressions used in our implementation form a commutative semiring. Based on this we implement a semiring solver, allowing one to apply the translation method automatically to certain identities. We also show how cancellation procedures, introduced by Feldman and Propp (1995), can be used to give meaning to subtraction, division and k-th roots in the translation method, and we implement the cancellation procedure that represents subtraction. Finally we give a philosophical discussion about the inner workings of the translation method, and use that to count the number of “natural” bijections for an identity considered by Wood and Zeilberger.

See source code at GitHub.

Defended at Reykjavík University, Iceland, June 2017 by Bjarki Ágúst Guðmundsson (PDF)

Automatic discovery of structural rules of permutation classes
arXiv: 1705.04109
Authors: M. Albert, C. Bean, A. Claesson, B. Gudmundsson, and H. Ulfarsson

We introduce an algorithm that conjectures the structure of a permutation class in the form of a disjoint cover of “rules”; similar to generalized grid classes. The cover is usually easily verified by a human and translated into an enumeration. The algorithm is successful on different inputs than other algorithms and can succeed with any polynomial permutation class. We apply it to every non-polynomial permutation class avoiding a set of length four patterns. The structures found by the algorithm can sometimes allow an enumeration of the permutation class with respect to permutation statistics, as well as choosing a permutation uniformly at random from the permutation class. We sketch a new algorithm formalizing the human verification of the conjectured covers.

See source code at GitHub.

Presented at ICE-TCS Seminar, Reykjavik University, Iceland, November 2014 by Christian Bean
Presented at Experimental Mathematics Seminar, Rutgers University, USA, March 2015 by Henning Ulfarsson (Video: Part 1, Part 2)
Presented at Scottish Combinatorics Meeting, University of Glasgow, Scotland, April 2016 by Christian Bean (PDF)
Presented at Permutation Patterns, Howard University, USA, June 2016 by Christian Bean (Abstract, pg. 10)
Referenced on OEIS

2016

Algorithmic coincidence classification of mesh patterns
Authors: Bjarki Ágúst Guðmundsson, Tómas Ken Magnússon, Henning Ulfarsson

See source code at GitHub. Will be Tómas’ MSc thesis subject.

Presented at Permutation Patterns, Howard University, USA, June 2016 by Bjarki Ágúst Guðmundsson (Abstract, pg. 33)
Poster at Permutation Patterns, Reykjavík University, Iceland, June 2017 by Tómas Ken Magnússon (PDF)

2015

Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring
arXiv: 1509.00099
doi: doi:10.1016/j.entcs.2016.03.013
Authors: Bjarki Ágúst Guðmundsson, Tómas Ken Magnússon, Björn Orri Sæmundsson

We study the weighted improper coloring problem, a generalization of defective coloring. We present some hardness results and in particular we show that weighted improper coloring is not fixed-parameter tractable when parameterized by pathwidth. We generalize bounds for defective coloring to weighted improper coloring and give a bound for weighted improper coloring in terms of the sum of edge weights. Finally we give fixed-parameter algorithms for weighted improper coloring both when parameterized by treewidth and maximum degree and when parameterized by treewidth and precision of edge weights. In particular, we obtain a linear-time algorithm for weighted improper coloring of interval graphs of bounded degree.

Published in Electronic Notes in Theoretical Computer Science, Volume 322, 18 April 2016, Pages 181-195
Presented at ICTCS 2015, the 16th Italian Conference on Theoretical Computer Science by Tómas Ken Magnússon
Presented at ICE-TCS Seminar, Reykjavik University, Iceland, 2015 by Tómas Ken Magnússon

2014

Collatz meets Fibonacci
arXiv: 1404.3054
Authors: Michael Albert, Bjarki Gudmundsson, Henning Ulfarsson

The Collatz map is defined for a positive even integer as half that integer, and for a positive odd integer as that integer threefold, plus one. The Collatz conjecture states that when the map is iterated the number one is eventually reached. We study permutations that arise as sequences from this iteration. We show that permutations of this type of length up to 14 are enumerated by the Fibonacci numbers. Beyond that excess permutations appear. We will explain the appearance of these excess permutations and give an upper bound on the exact enumeration.

Presented at Stærðfræði á Íslandi, Iceland, 2013 by Bjarki Ágúst Guðmundsson
Presented at MIT Combinatorics Seminar, Boston, MA, October 2013 by Henning Ulfarsson
Poster at Permutation Patterns, East Tennessee State University, USA, July 2014 by Michael Albert (PDF)
Presented at the 2015 Joint Mathematics Meetings, San Antonio, TX by Michael Albert
Referenced on OEIS