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

This article is available for purchase or by subscription. See below.

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.

PDF Access Denied

We have not been able to recognize your IP address 18.97.9.174 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

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