Occurrence graphs of patterns in permutations

Kristinsson, Bjarni Jens; Ulfarsson, Henning

doi:10.2140/involve.2019.12.901

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

Occurrence graphs of patterns in permutations

Bjarni Jens Kristinsson and Henning Ulfarsson

Vol. 12 (2019), No. 6, 901–918

DOI: 10.2140/involve.2019.12.901

Abstract

We define the occurrence graph $G_{p} (π)$ of a pattern $p$ in a permutation $π$ as the graph whose vertices are the occurrences of $p$ in $π$ , with 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.

Keywords

graph, permutation, subgraph, pattern

Mathematical Subject Classification 2010

Primary: 05A05, 05A15, 05C30

Milestones

Received: 11 July 2016

Revised: 15 February 2019

Accepted: 18 February 2019

Published: 3 August 2019

Communicated by Anant Godbole

Authors

Bjarni Jens Kristinsson
Department of Mathematics University of Iceland Reykjavik Iceland

Henning Ulfarsson
School of Computer Science Reykjavik University Reykjavik Iceland

Vol. 12, No. 6, 2019