A simple proof characterizing interval orders with interval lengths between 1 and k

Boyadzhiyska, Simona; Isaak, Garth; Trenk, Ann N.

doi:10.2140/involve.2018.11.893

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

A simple proof characterizing interval orders with interval lengths between 1 and $k$

Simona Boyadzhiyska, Garth Isaak and Ann N. Trenk

Vol. 11 (2018), No. 5, 893–900

DOI: 10.2140/involve.2018.11.893

Abstract

A poset $P = (X, ≺)$ has an interval representation if each $x \in X$ can be assigned a real interval $I_{x}$ so that $x ≺ y$ in $P$ if and only if $I_{x}$ lies completely to the left of $I_{y}$ . Such orders are called interval orders. Fishburn (1983, 1985) proved that for any positive integer $k$ , an interval order has a representation in which all interval lengths are between $1$ and $k$ if and only if the order does not contain $(k + 2) + 1$ as an induced poset. In this paper, we give a simple proof of this result using a digraph model.

Keywords

interval order, interval graph, semiorder

Mathematical Subject Classification 2010

Primary: 05C62, 06A99

Milestones

Received: 31 August 2017

Revised: 30 January 2018

Accepted: 5 February 2018

Published: 2 April 2018

Communicated by Glenn Hurlbert

Authors

Simona Boyadzhiyska
Berlin Mathematical School Freie Universität Berlin Berlin Germany

Garth Isaak
Department of Mathematics Lehigh University Bethlehem, PA United States

Ann N. Trenk
Department of Mathematics Wellesley College Wellesley, MA United States

Vol. 11, No. 5, 2018