About: 1/3–2/3 conjecture     Goto   Sponge   NotDistinct   Permalink

An Entity of Type : yago:Speculation105891783, within Data Space : live.dbpedia.org associated with source document(s)
QRcode icon
http://live.dbpedia.org/describe/?url=http%3A%2F%2Fdbpedia.org%2Fresource%2F1%2F3%E2%80%932%2F3_conjecture

In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. Equivalently, in every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y.

AttributesValues
rdf:type
rdfs:label
  • 1/3–2/3 conjecture
rdfs:comment
  • In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. Equivalently, in every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y.
sameAs
foaf:depiction
  • External Image
foaf:isPrimaryTopicOf
thumbnail
dct:subject
Wikipage page ID
Wikipage revision ID
Link from a Wikipage to another Wikipage
Link from a Wikipage to an external page
dbp:wikiPageUsesTemplate
authorlink
  • Nati Linial
first
  • Nati
last
  • Linial
year
has abstract
  • In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible sorted orders by a factor of 2/3 or better. Equivalently, in every finite partially ordered set that is not totally ordered, there exists a pair of elements x and y with the property that at least 1/3 and at most 2/3 of the linear extensions of the partial order place x earlier than y.
prov:wasDerivedFrom
Wiki page out degree
page length (characters) of wiki page
gold:hypernym
is foaf:primaryTopic of
is Link from a Wikipage to another Wikipage of
is Wikipage redirect of
Faceted Search & Find service v1.17_git93 as of Oct 15 2021


Alternative Linked Data Documents: PivotViewer | ODE     Content Formats:   [cxml] [csv]     RDF   [text] [turtle] [ld+json] [rdf+json] [rdf+xml]     ODATA   [atom+xml] [odata+json]     Microdata   [microdata+json] [html]    About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data] Valid XHTML + RDFa
OpenLink Virtuoso version 08.03.3322 as of Apr 19 2022, on Linux (x86_64-generic-linux-glibc25), Single-Server Edition (378 GB total memory, 32 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2022 OpenLink Software