NDLI: A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2

Please wait, while we are loading the content...

A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2

Content Provider	Springer Nature Link
Author	Howard, David M. Keller, Mitchel T. Young, Stephen J.
Copyright Year	2007
Abstract	The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then \|h $_{ L }$(x)–h $_{ L }$(y)\|≤k, where h $_{ L }$(x) is the height of x in L. Tanenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem of characterizing the posets of linear discrepancy 2. We show that this problem is equivalent to finding the posets with linear discrepancy equal to 3 having the property that the deletion of any point results in a reduction in the linear discrepancy. Howard determined that there are infinitely many such posets of width 2. We complete the forbidden subposet characterization of posets with linear discrepancy equal to 2 by finding the minimal posets of width 3 with linear discrepancy equal to 3. We do so by showing that, with a small number of exceptions, they can all be derived from the list for width 2 by the removal of specific comparisons.
Ending Page	153
Page Count	15
Starting Page	139
File Format	PDF
ISSN	01678094
e-ISSN	15729273
Journal	Order
Issue Number	3
Volume Number	24
Language	English
Publisher	Springer Netherlands
Publisher Date	2007-09-22
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Geometry Combinatorics of partially ordered sets Convex and Discrete Geometry Poset Linear extension Theory of Computation Linear discrepancy
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

Linear Discrepancy of the Product of Two Chains

Linear Discrepancy and Weak Discrepancy of Partially Ordered Sets

Irreducible Width 2 Posets of Linear Discrepancy 3

Incidence Posets and Cover Graphs

Computing Orbits of the Automorphism Group of the Subsequence Poset B $_{ m,n }$

Homomorphism-Homogeneous Partially Ordered Sets

Decompositions of Partially Ordered Sets

Diamond-Free Subsets in the Linear Lattices

Dimension Preserving Contractions and a Finite List of 3-Irreducible Posets

A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2

Similar Documents

Linear Discrepancy of the Product of Two Chains

Linear Discrepancy and Weak Discrepancy of Partially Ordered Sets

Irreducible Width 2 Posets of Linear Discrepancy 3

Incidence Posets and Cover Graphs

Computing Orbits of the Automorphism Group of the Subsequence Poset B $_{ m,n }$

Homomorphism-Homogeneous Partially Ordered Sets

Decompositions of Partially Ordered Sets

Diamond-Free Subsets in the Linear Lattices

Dimension Preserving Contractions and a Finite List of 3-Irreducible Posets

A Characterization of Partially Ordered Sets with Linear Discrepancy Equal to 2