Rankings of Multisets and Discrete Cones

Marston Conder, Simon Marshall, Arkadii Slinko


We study additive representability of orders on multisets (of size $k$ drawn from a
set of size $n$) which satisfy the condition of
Independence of Equal Submultisets (IES) introduced by Sertel and Slinko (2002). Here we
take a geometric view of those orders, and relate them to certain combinatorial
objects which we call discrete cones. Following Fishburn (1996) and Conder and
Slinko (2003), we define functions $f(n,k)$ and $g(n,k)$ which
measure the maximal possible deviation of an arbitrary
order satisfying the IES and an arbitrary almost representable order satisfying the
IES, respectively, from a representable order. We prove that
$g(n,k)=n-1$ whenever $nge 3$ and $(n,k)ne (5,2)$.
In the exceptional case, $g(5,2)=3$. We also prove that $g(n,k)le f(n,k)le n$ and
establish that for small $n$ and $k$ the functions $g(n,k)$ and $f(n,k)$ coincide.

multiset, linear orders, Independence of Equal Submultisets, additive representability

Math Review Classification
Primary 91B16

Last Updated
30 April 2004

24 pp

This article is available in: