Michal Opler

activity

20152021

most citedMajor index distribution over permutation classes

1 citations · 2 across the 3 of their papers we have counts for

collaborators

6 papers

cs.CC2021

Long paths make pattern-counting hard, and deep trees make it harder

Vít Jelínek, Michal Opler, Jakub Pekárek

We study the counting problem known as #PPM, whose input is a pair of permutations $π$ and $τ$ (called pattern and text, respectively), and the task is to find the number of subseq…

cs.CG2021

Non-homotopic Loops with a Bounded Number of Pairwise Intersections

Václav Blažej, Michal Opler, Matas Šileikis +1

Let $V_{n}$ be a set of $n$ points in the plane and let $x \in / V_{n}$ . An $x$ -loop is a continuous closed curve not containing any point of $V_{n}$ . We say that two $x$ -loops are non-…

math.CO2021

Griddings of permutations and hardness of pattern matching

Vít Jelínek, Michal Opler, Jakub Pekárek

We study the complexity of the decision problem known as Permutation Pattern Matching, or PPM. The input of PPM consists of a pair of permutations $τ$ (the `text') and $π$ (the `pa…

math.CO2020

A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes

Vít Jelínek, Michal Opler, Jakub Pekárek

Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations P and T whether the pattern P is contained in the text T. Bose, Buss and Lubiw showed…

math.CO2019★ 1 cited

Wilf collapse in permutation classes

Michael Albert, Vít Jelínek, Michal Opler

For a hereditary permutation class $C$ , we say that two permutations $π$ and $σ$ of $C$ are Wilf-equivalent in $C$ , if $C$ has the same numb…

math.CO2015★ 1 cited

Major index distribution over permutation classes

Michal Opler

For a permutation $π$ the major index of $π$ is the sum of all indices $i$ such that $π_{i} > π_{i + 1}$ . It is well known that the major index is equidistributed with the number of in…