BiSC

The BiSC algorithm for discovering patterns avoided by a permutation set.

Running the algorithm

The code depends on Sage, pattern-avoidance and permutation-sets. Furthermore, it is assumed that the three repositories (pattern-avoidance, permutation-sets and bisc) are in the same folder.

If you do not want to install Sage on your computer (or the three necessary repositories) you can run everything in SageMathCloud. After creating your account, create a new project. Click the New button and select >_Terminal. This will create a Command line terminal session. In this terminal session type

git pull https://github.com/ulfarsson/pattern-avoidance.git
git pull https://github.com/ulfarsson/permutation-sets.git
git pull https://github.com/ulfarsson/bisc.git

hitting Enter after each line. Now navigate into the bisc folder (cd bisc). You now have two options:

1. Type sage and hit Enter. You are now working with Sage in the terminal. Type %runfile helper_functions.sage to load all the neccessary files.
2. If you do not like working in a terminal you can instead click the New button and create a Sage Worksheet. In the first line type runfile('helper_functions.sage') to load all the neccessary files.

The rest of the tutorial works the same for option 1. and 2. above.

Creating a permutation set to investigate

The repository permutation-sets has many predefined examples you can use, located in the subfolder examples. If you want to investigate West-2-stack-sortable permutations you will find them in the file examples/examples_sorting.sage. They are example nr. 2. Let's load those permutations up lenght 7:

A, B = create_example('sorting', 2, 7)

This will store the West-2-stack-sortable permutations in the dictionary A, and their compliment in the dictionary B.

Mining for allowed patterns

We now run the mine algorithm on our set. If we want to look for patterns of length 5, using all of the permutations we created (up to length 7), we do:

ci, goodpatts = run_mine(A, 5, 7)

This will create an interval ci, to be used later, and collect the mesh patterns present in permutations in A in a dictionary goodpatts.

Generating forbidden patterns

We now run the forb algorithm to generate the forbidden patterns. To make it generate forbidden patterns up to length 5 we do:

SG = run_forb(ci, goodpatts, 5)

Looking at what we found

To get a short description of what was found run

show_me(SG, more=False)

To see the patterns themselves flip more to True.

Do the patterns suffice?

It is always a good idea to make sure that the patterns we found actually describe the set of permutations we are investigating. To do this we check whether there are permutations in the compliment that avoid the patterns we found. To see if this is the case, at least up to length 7 we do:

val, avoiding_perms = run_patterns_suffice(SG, 7, B)

The output is val, which is a Boolean variable telling us whether there are any avoiding permutations in B up to length 7, and avoiding_perms will store those permutations.

Can we get away with less?

If you are familiar with the West-2-stack-sortable permutations you might have been surprised to see that we found one mesh pattern of length 5 that is actually redundant. To see if a size 2 subset of the patterns we found is enough to describe the permutations we do:

bases, dict_numbs_to_patts = run_clean_up(SG, B, 6, 4, limit_monitors = 2)

Note that SG is the forbidden patterns found above, B is the complement of the permutations we are investigating. The 6 tells the function to only look at permutations in B up to length 6, while the 4 tells the function that it should only use patterns from SG up to length 4.

Finally, to look at a particular basis in bases, do:

show_me_basis(bases[0], dict_numbs_to_patts)

This will show you the two patterns of length 4 that describe the West-2-stack-sortable permutations.