We define the occurrence graph of a pattern p in a permutation as the graph with the occurrences of p in the permutation 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 hereditary property of graphs gives rise to a permutation class.

Download the paper

• Bjarni's BSc thesis
  
• arXiv
  

Additional material

• Presentation at the biannual conference of the Icelandic Mathematics Society 2015
  
• Presentation at Permutation Patterns 2016