Fractional weak discrepancy and split semiorders

DOI10.1016/J.DAM.2010.04.014zbMATH Open1256.06002arXiv1501.06430OpenAlexW1994085942MaRDI QIDQ531608FDOQ531608

Authors: Alan Shuchat, Randy Shull, Ann Trenk 

Publication date: 19 April 2011

Published in: Discrete Applied Mathematics, Order (Search for Journal in Brave)

Abstract: A poset $P=(X,prec)$ is a unit OC interval order if there exists a representation that assigns an open or closed real interval $I(x)$ of unit length to each $xinP$ so that $xprecy$ in $P$ precisely when each point of $I(x)$ is less than each point in $I(y)$. In this paper we give a forbidden poset characterization of the class of unit OC interval orders and an efficient algorithm for recognizing the class. The algorithm takes a poset $P$ as input and either produces a representation or returns a forbidden poset induced in $P$.

Full work available at URL: https://arxiv.org/abs/1501.06430

Recommendations

• Fractional weak discrepancy and interval orders
• The fractional weak discrepancy of a partially ordered set
• Fractional weak discrepancy of posets and certain forbidden configurations
• On the fractional dimension of partially ordered sets
• The total weak discrepancy of a partially ordered set
• Linear discrepancy and weak discrepancy of partially ordered sets
• The fractional weak discrepancy of \((M, 2)\)-free posets
• The lower semicontinuity of the Frobenius splitting numbers
• scientific article; zbMATH DE number 1534280
• Fractional dimension of partial orders

zbMATH Keywords

posetsefficient algorithmssemiordersforbidden subposetsforcing cyclefractional weak discrepancymixed interval graphsproper interval orderssplit semiordersunit interval orders

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Software, source code, etc. for problems pertaining to ordered structures (06-04)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Intransitive indifference with unequal indifference intervals
• Foundational aspects of theories of measurement
• Title not available (Why is that?)
• Integral mixed unit interval graphs
• Unit interval graphs of open and closed intervals
• Generalizations of semiorders: A review note
• A short proof that `proper = unit'
• Split semiorders
• Linear discrepancy and weak discrepancy of partially ordered sets
• Fractional weak discrepancy and interval orders
• On \(k\)-weak orders: Recognition and a tolerance result
• The fractional weak discrepancy of a partially ordered set
• Range of the fractional weak discrepancy function
• Fractional weak discrepancy of posets and certain forbidden configurations
• On the Weakness of an Ordered Set
• Unit mixed interval graphs

Cited In (1)

• Dimension of restricted classes of interval orders

This page was built for publication: Fractional weak discrepancy and split semiorders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q531608)