Balancing poset extensions View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1984-06

AUTHORS

Jeff Kahn, Michael Saks

ABSTRACT

We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log2e (X) comparisons whereC is approximately 2.17. More... »

PAGES

113-126

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf00565647

DOI

http://dx.doi.org/10.1007/bf00565647

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1019850122


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Rutgers University, 08903, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Massachusetts Institute of Technology, 02139, Cambridge, MA, USA", 
            "Rutgers University, 08903, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kahn", 
        "givenName": "Jeff", 
        "id": "sg:person.07651605463.67", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Rutgers University, 08903, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Rutgers University, 08903, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-642-47404-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035094391", 
          "https://doi.org/10.1007/978-3-642-47404-0"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1984-06", 
    "datePublishedReg": "1984-06-01", 
    "description": "We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log2e (X) comparisons whereC is approximately 2.17.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf00565647", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136683", 
        "issn": [
          "0167-8094", 
          "1572-9273"
        ], 
        "name": "Order", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "1"
      }
    ], 
    "keywords": [
      "partial information", 
      "linear extension", 
      "multiplicative constant", 
      "information theoretic", 
      "finite", 
      "extension", 
      "theoretic", 
      "whereC", 
      "whichX", 
      "ofX", 
      "andy", 
      "setP", 
      "set", 
      "constants", 
      "information", 
      "number", 
      "pairs", 
      "IFX", 
      "consequences", 
      "proportion"
    ], 
    "name": "Balancing poset extensions", 
    "pagination": "113-126", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019850122"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf00565647"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf00565647", 
      "https://app.dimensions.ai/details/publication/pub.1019850122"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-10-01T06:27", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/article/article_167.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf00565647"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/bf00565647'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/bf00565647'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf00565647'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf00565647'


 

This table displays all metadata directly associated to this object as RDF triples.

89 TRIPLES      21 PREDICATES      46 URIs      37 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf00565647 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N276e05865f8a4c90af2d14df01982e54
4 schema:citation sg:pub.10.1007/978-3-642-47404-0
5 schema:datePublished 1984-06
6 schema:datePublishedReg 1984-06-01
7 schema:description We show that any finite partially ordered setP (not a total order) contains a pair of elementsx andy such that the proportion of linear extensions ofP in whichx lies belowy is between 3/11 and 8/11. A consequence is that the information theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: ifX is a totally ordered set about which we are given some partial information, and ife(X) is the number of total orderings ofX compatible with this information, then it is possible to sortX using no more thanC log2e (X) comparisons whereC is approximately 2.17.
8 schema:genre article
9 schema:isAccessibleForFree false
10 schema:isPartOf N1ae5a2e3eda7418085abfe991572779c
11 N85d671080df74a3cbc666e91b6e0dc69
12 sg:journal.1136683
13 schema:keywords IFX
14 andy
15 consequences
16 constants
17 extension
18 finite
19 information
20 information theoretic
21 linear extension
22 multiplicative constant
23 number
24 ofX
25 pairs
26 partial information
27 proportion
28 set
29 setP
30 theoretic
31 whereC
32 whichX
33 schema:name Balancing poset extensions
34 schema:pagination 113-126
35 schema:productId N1ae43f83acd54e5eadf79ab5d58233f4
36 N66a7ea4dd6834e2080836d57be0da6cd
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019850122
38 https://doi.org/10.1007/bf00565647
39 schema:sdDatePublished 2022-10-01T06:27
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Na5875106b8be4ebeb705520baf2ecf92
42 schema:url https://doi.org/10.1007/bf00565647
43 sgo:license sg:explorer/license/
44 sgo:sdDataset articles
45 rdf:type schema:ScholarlyArticle
46 N1ae43f83acd54e5eadf79ab5d58233f4 schema:name doi
47 schema:value 10.1007/bf00565647
48 rdf:type schema:PropertyValue
49 N1ae5a2e3eda7418085abfe991572779c schema:volumeNumber 1
50 rdf:type schema:PublicationVolume
51 N276e05865f8a4c90af2d14df01982e54 rdf:first sg:person.07651605463.67
52 rdf:rest N6eaa7c88d1e740219cd84c65ea536d40
53 N66a7ea4dd6834e2080836d57be0da6cd schema:name dimensions_id
54 schema:value pub.1019850122
55 rdf:type schema:PropertyValue
56 N6eaa7c88d1e740219cd84c65ea536d40 rdf:first sg:person.011520224512.05
57 rdf:rest rdf:nil
58 N85d671080df74a3cbc666e91b6e0dc69 schema:issueNumber 2
59 rdf:type schema:PublicationIssue
60 Na5875106b8be4ebeb705520baf2ecf92 schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
63 schema:name Mathematical Sciences
64 rdf:type schema:DefinedTerm
65 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
66 schema:name Pure Mathematics
67 rdf:type schema:DefinedTerm
68 sg:journal.1136683 schema:issn 0167-8094
69 1572-9273
70 schema:name Order
71 schema:publisher Springer Nature
72 rdf:type schema:Periodical
73 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
74 schema:familyName Saks
75 schema:givenName Michael
76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
77 rdf:type schema:Person
78 sg:person.07651605463.67 schema:affiliation grid-institutes:grid.430387.b
79 schema:familyName Kahn
80 schema:givenName Jeff
81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07651605463.67
82 rdf:type schema:Person
83 sg:pub.10.1007/978-3-642-47404-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035094391
84 https://doi.org/10.1007/978-3-642-47404-0
85 rdf:type schema:CreativeWork
86 grid-institutes:grid.430387.b schema:alternateName Rutgers University, 08903, New Brunswick, NJ, USA
87 schema:name Massachusetts Institute of Technology, 02139, Cambridge, MA, USA
88 Rutgers University, 08903, New Brunswick, NJ, USA
89 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...