NDLI: The Representation Polyhedron of a Semiorder

Content Provider	Springer Nature Link
Author	Balof, Barry Fiorini, Samuel Doign, Jean Paul
Copyright Year	2011
Abstract	Let a finite semiorder, or unit interval order, be given. When suitably defined, its numerical representations are the solutions of a system of linear inequalities. They thus form a convex polyhedron. We show that the facets of the representation polyhedron correspond to the noses and hollows of the semiorder. Our main result is to prove that the system defining the polyhedron is totally dual integral. As a consequence, the coordinates of the vertices and the components of the extreme rays of the polyhedron are all integral multiples of a common value. Total dual integrality is in turn derived from a particular property of the oriented cycles in the directed graph of noses and hollows of a strictly upper diagonal step tableau. Our approach delivers also a new proof for the existence of the minimal representation of a semiorder, a concept originally discovered by Pirlot (Theory Decis 28:109–141, 1990). Finding combinatorial interpretations of the vertices and extreme rays of the representation polyhedron is left for future work.
Ending Page	135
Page Count	33
Starting Page	103
File Format	PDF
ISSN	01678094
e-ISSN	15729273
Journal	Order
Issue Number	1
Volume Number	30
Language	English
Publisher	Springer Netherlands
Publisher Date	2011-09-07
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Integer programming Geometry Representation polyhedron Combinatorics of partially ordered sets Total dual integrality Convex and Discrete Geometry Special polytopes (linear programming, centrally symmetric, etc.) Theory of Computation Semiorder
Content Type	Text
Resource Type	Article
Subject	Algebra and Number Theory Computational Theory and Mathematics Geometry and Topology

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Two enriched poset polytopes

Linear recursions for integer point transforms

Incompatible double posets and double order polytopes

Two double poset polytopes

Equivalence Between Four Models of Associahedra

Degrees of stretched Kostka coefficients

The Face Structure and Geometry of Marked Order Polyhedra

The two higher Stasheff-Tamari orders are equal

Numerical Representation of Semiorders

The Representation Polyhedron of a Semiorder

Similar Documents

Two enriched poset polytopes

Linear recursions for integer point transforms

Incompatible double posets and double order polytopes

Two double poset polytopes

Equivalence Between Four Models of Associahedra

Degrees of stretched Kostka coefficients

The Face Structure and Geometry of Marked Order Polyhedra

The two higher Stasheff-Tamari orders are equal

Numerical Representation of Semiorders

The Representation Polyhedron of a Semiorder