{"entities":{"Q1209661":{"pageid":1220410,"ns":120,"title":"Item:Q1209661","lastrevid":66308073,"modified":"2026-04-12T09:05:56Z","type":"item","id":"Q1209661","labels":{"en":{"language":"en","value":"On estimating the number of order ideals in partial orders, with some applications"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 168246"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$CF80A32E-995B-4545-9FD6-015942673ADC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7e7747d0d91482a49ca81c3ec4b5b7f2c5a2033d","datavalue":{"value":{"text":"On estimating the number of order ideals in partial orders, with some applications","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209661$272C031C-AC9C-46F5-A9E3-0CDB15B079A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0614f415de9f7386cb72a238aebd24191d136d62","datavalue":{"value":"0777.06004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209661$50E56EE3-D7C3-43A6-9524-F746B75B6300","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"61fc79e46ef761445988bce21468ee12d4b02cb2","datavalue":{"value":"10.1016/0378-3758(93)90012-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209661$68CECD5A-2233-4809-AFC9-28388FD99A00","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1814572f6f5cc98a1bdac6b4fecbd84381c8ff3","datavalue":{"value":{"entity-type":"item","numeric-id":187128,"id":"Q187128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$4EC7BCAC-AFD2-4841-A570-2ACE9015EF9D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c4f1d146edae4b7d1fb7c199d8e4d54181e32d52","datavalue":{"value":{"entity-type":"item","numeric-id":62245,"id":"Q62245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$2DAE3C81-7868-4AE7-9BD5-611BFC0E1C27","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1209661$6F3167F0-F411-423D-A10D-B527EF83C3C7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1dce389f90281d235c69438337f6a23582cd66be","datavalue":{"value":"The generation and counting of order ideals and antichains in a given partially ordered set \\(P\\) of \\(n\\) elements is one of the basic, frequently occurring problems in combinatorial optimization and operations research.   Counting the ideals of a general poset was shown to be \\(\\# P\\)-complete by Provan and Ball in 1983 even in the case where \\(P\\) contains no chain with more than two elements.   This paper presents a new polynomial time algorithm to count the number of ideals of any fixed cardinality in 2-dimensional ordered sets. It also gives some bounds for the number \\(\\text{NO}(P)\\) of all ideals. These bounds depend only on the width \\(w(P)\\) of \\(P\\), the maximum size of an antichain in \\(P\\). These bounds are:  \\[ 2^{w(P)}+n-w(P)\\leq \\text{NO}(P)\\leq [(n+w(P))/w(P)]^{w(P)}. \\]  Finally, the paper reports on a computational study that used 300 randomly generated posets of varying sizes and different values for the width and density of the posets. The study supports that a large part of the variation in \\(\\text{NO}(P)\\) amd SMAX can be explained by simple regression equations using the width and density as independent variables.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$05D2D17B-86DB-4700-919D-EDB00EB2BDCF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209661$BAB7C9F3-0960-4A9D-AA2E-FB16ABA49701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209661$8B812E9F-8B84-421B-8703-08A97B75CC86","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a3e15b6cd9b4eadccc1adf9921d64895eac9d76f","datavalue":{"value":"168246","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209661$891D5D49-94CA-4530-8800-CF15A2786A74","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$3413EF48-FF83-46D6-A1BA-22EFA3764C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f796ed2b460346bbba92264dac0da22a5120d5d","datavalue":{"value":"recursion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$6C6D78E2-FDAC-474B-B406-73AAC490496A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6be3bd30fa92aef645568f23989ca95a04dae5fa","datavalue":{"value":"order ideals","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$46AA5B26-6F42-47DA-BC3C-3F2D54F48387","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"922c01258e140214b68568956989c4ba97b3c6f4","datavalue":{"value":"antichains","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$1248BFC5-6D0F-435C-9C8C-8BACF3A3C566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdde7b45dbb3f8df248ead9902e8db0fb791e374","datavalue":{"value":"polynomial time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$7F742D92-85EF-411F-907A-3F414DC68031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"960d495c90a1cdb5b07d21fd762980fd138e6f99","datavalue":{"value":"2-dimensional ordered sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$6148A593-D6AD-4CCC-8683-BD1CDD575C14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccdf98bea6de3dcf3a7edd1fca9d3b62359e75d8","datavalue":{"value":"width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$F4DE157A-4E87-4627-93BE-DBFF81AB1A8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a01ee01077a14e69c3c27408efccd7f448855eec","datavalue":{"value":"density","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$20371D6C-6078-4C37-B468-C79A04929538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"91970265fc249ef344fb4d01506952b43cf4fa48","datavalue":{"value":"regression equations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209661$159828D1-654D-4971-943A-570F285B03EF","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$6BF1304A-ED88-4AAA-A540-A06E9B6B13A5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9128591bedd9f799226a001918ad0487b45253a3","datavalue":{"value":{"entity-type":"item","numeric-id":3686053,"id":"Q3686053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$B3ACC4A7-1D4B-4CD4-BFA9-3C6979EFD50F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a860092cae4ad4c5ee631c0a98f0a7ee7f9c9d0","datavalue":{"value":{"entity-type":"item","numeric-id":3241581,"id":"Q3241581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$B80905E7-159D-4C29-A2D4-26C968AFB73D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$D5B06EF6-148F-46DD-A51B-35FC505EF5AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$13CD4FAC-C99E-49DC-B946-B0515012E938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"993ebeadf55a51cd37348fb1f0e335e70c02ca6d","datavalue":{"value":{"entity-type":"item","numeric-id":3756532,"id":"Q3756532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$BD2FB0EB-B786-45CE-86DA-0B8C6EBDE542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbad4944f17afff471966f84ddba81383864ae6","datavalue":{"value":{"entity-type":"item","numeric-id":3292045,"id":"Q3292045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$D9BEC777-B98F-421E-957D-AF0CF37EA948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0f81a612075c3a25dc17eeeb94a2a45198c2ae0","datavalue":{"value":{"entity-type":"item","numeric-id":5331681,"id":"Q5331681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$FC7608F5-A407-4EC0-B27C-690BE43C0AFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cc48ddcc9c1674b67ed1e23be073ed5497f67d7","datavalue":{"value":{"entity-type":"item","numeric-id":3206647,"id":"Q3206647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$FF4D1E11-80AA-4C21-B731-D553D2614C5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfba82c35dc6ea457ce9efae48621ad687750dba","datavalue":{"value":{"entity-type":"item","numeric-id":3951899,"id":"Q3951899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$C0BFF1CE-8D19-4C5E-83FC-83ACC10C41AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7cbae1c1118a2e1a65c80b733f652572b93c30","datavalue":{"value":{"entity-type":"item","numeric-id":4918387,"id":"Q4918387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$BE01BAE9-D484-4F06-A486-9BF1763194DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3798f797f1d96df74883f771f001f3f714b860f0","datavalue":{"value":{"entity-type":"item","numeric-id":3036719,"id":"Q3036719"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$93174794-8C0D-4C50-A124-110ADE06B0F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"012746c120503bc5461364a9fb2df6d0b88646ed","datavalue":{"value":{"entity-type":"item","numeric-id":3351401,"id":"Q3351401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$A9E6D53B-DCEE-4D3F-8324-36B3E77470A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33ebd623f6b8e57b27792095bc1a5f936ffa53ab","datavalue":{"value":{"entity-type":"item","numeric-id":3748279,"id":"Q3748279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$396D5689-3351-44B3-915B-8E2E1DAE70CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4585580cfe9d56f5babd98d6bb6cd8035990427b","datavalue":{"value":{"entity-type":"item","numeric-id":3329201,"id":"Q3329201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$C40B86B1-C193-4071-8460-4CCFA899C9EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb00d0b38a30a9efcc2e710ef5ece605f977bf75","datavalue":{"value":{"entity-type":"item","numeric-id":1086160,"id":"Q1086160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$5858C209-526D-4F3C-AEB6-E88BD2137066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7da38e61e76b02d5c015c037e4e3425434d88e35","datavalue":{"value":{"entity-type":"item","numeric-id":922284,"id":"Q922284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209661$A071B8B5-396F-4182-B4A1-FFCF055B2702","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96971c530c426acf0ab55e0103144dc17c84131c","datavalue":{"value":{"entity-type":"item","numeric-id":1086160,"id":"Q1086160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7226075970ba0934a533d14f205d82983bef838f","datavalue":{"value":{"amount":"+0.8151060938835144","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1209661$372A39B8-3DDF-4556-9345-60098830AF7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e80df015908e0fff5f0dbc6f5b2daa50a905e42","datavalue":{"value":{"entity-type":"item","numeric-id":1362577,"id":"Q1362577"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f33265b2f8cb86b3cc5ac19c5e94cd3d87b06985","datavalue":{"value":{"amount":"+0.797537088394165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1209661$A077BC98-0CEF-43E0-A43E-E9031134F44D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e37dc7c27238d8ed6c0b439e46f0b2f7b2c41a2b","datavalue":{"value":{"entity-type":"item","numeric-id":4318662,"id":"Q4318662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f33265b2f8cb86b3cc5ac19c5e94cd3d87b06985","datavalue":{"value":{"amount":"+0.797537088394165","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1209661$42A7D1EF-6E80-4A62-8613-B7A2D596A0DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5db44028f41cc145d381cee1429eb837b72d00b","datavalue":{"value":{"entity-type":"item","numeric-id":3360658,"id":"Q3360658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93559394e9c59d5058af653a088dce123a27f31c","datavalue":{"value":{"amount":"+0.7961650490760803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1209661$3D19F79E-CC84-4914-9415-61B349EC120D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a7c5c2b1de0cc013dae4c7b0c6d70e19d8f69a4","datavalue":{"value":{"entity-type":"item","numeric-id":3760585,"id":"Q3760585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f423812a0bc513023c9af3f046f090f1e4d78e4","datavalue":{"value":{"amount":"+0.7795575261116028","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1209661$E62C49A6-CEBC-4F9C-8062-23C3CA3582BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On estimating the number of order ideals in partial orders, with some applications","badges":[]}}}}}