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

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-4184 (e-only)

ISSN: 1944-4176 (print)

Author Index

Coming Soon

Other MSP Journals

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

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.

PDF Access Denied

We have not been able to recognize your IP address 44.192.115.114 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

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