Occurrence graphs of patterns in permutations

Abstract

We define the \emph{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 then study properties of these graphs. The main theorem in this paper is that every \emph{hereditary property} of graphs gives rise to a \emph{permutation class}.

19 pages, 15 figures

References in corpus (2)

• Coincidence among families of mesh patterns
• Algorithms for discovering and proving theorems about permutation patterns