{"entities":{"Q5937251":{"pageid":8114053,"ns":120,"title":"Item:Q5937251","lastrevid":93435215,"modified":"2026-06-05T04:23:47Z","type":"item","id":"Q5937251","labels":{"en":{"language":"en","value":"On disjoint chains of subsets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1618732"}},"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":"Q5937251$EBF59DE7-9E72-485B-A3FA-EE94AEBC5CDE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"050975a115504645150cac777eb9ffe4ec089cdd","datavalue":{"value":{"text":"On disjoint chains of subsets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5937251$E9289B1C-CA00-4FAE-9A03-6CABA2955E7D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7aef4ce3ef541209da56e8fdef16fb9a2f5d896d","datavalue":{"value":"0989.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937251$914A034F-9F11-4856-9F6C-9898005B1507","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca5b86eb868915c377d9f8399026f0f4a4bfbb0f","datavalue":{"value":{"entity-type":"item","numeric-id":178476,"id":"Q178476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937251$283E03B0-1279-4606-A86E-DE1DBDA91E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e10480e046eb228ee7883bfe3d51ac4b35b07ad9","datavalue":{"value":{"entity-type":"item","numeric-id":171921,"id":"Q171921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937251$431055C0-E42D-456C-BFBD-87D67A764661","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937251$3BA75014-8778-49B8-BC35-67FDCCDD05F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f0325700ca3bc3f7d102c264ab8870dda2d06b4b","datavalue":{"value":{"time":"+2002-07-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5937251$3181B528-FDDD-4AC0-9FE2-7E5993032E65","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"512bb1b1e1e6d304b6b975d8291072b11f08a9e9","datavalue":{"value":"In this note the authors prove the following theorem. Given a family \\(\\mathcal{S}\\) of \\(m\\) \\(s\\)-element subsets of \\(\\{1,2,\\ldots,n\\}\\) and a family \\(\\mathcal{R}\\) of \\(m\\) \\(r\\)-element subsets of \\(\\{1,2,\\ldots,n\\}\\), with \\(r<s\\), and given a bijection \\(\\phi: \\mathcal{S}\\rightarrow\\mathcal{R}\\) satisfying \\(\\phi(A)\\subset A\\) for each \\(A\\in\\mathcal{S}\\), there exist \\(m\\) disjoint saturated chains in the Boolean algebra on \\(\\{1,2,\\ldots,n\\}\\) that contain all the subsets in \\(\\mathcal{S}\\) and \\(\\mathcal{R}\\). This theorem already appeared in \\textit{O. Goldreich}, \\textit{S. Goldwasser}, \\textit{E. Lehman}, and \\textit{D. Ron} [``Testing monotonicity'', in: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 426-435 (1998)], with the same proof as is presented here. The proof is by induction on \\(m\\) and \\(s-r\\), and uses Menger's Theorem. The disjoint saturated chains cannot always be chosen to refine the chains \\(\\phi(A)\\subset A\\); an example is given to show this.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937251$E5EEA1AA-E116-452E-8F2A-C1D4ACF52512","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"da4d0e7cb40bc0b3317e46d43560da36a2bb5480","datavalue":{"value":{"entity-type":"item","numeric-id":796109,"id":"Q796109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937251$639B013E-6D62-41EB-954A-12D989060DEF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937251$7EDD04ED-6298-40E1-BCD4-467D73D8B74B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"99654c6f8a628147cee45cdfa6f7aaba140cbf55","datavalue":{"value":"1618732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937251$BA673B35-133A-4F3F-B133-44819380487E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b79c0d46aaed6ae08d529961c9f16b783e44803","datavalue":{"value":"Boolean algebra","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937251$62E638F0-4207-4F78-B1C8-36EAEC947066","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afc49132a213976c388e5ff5002ec762e1517aa6","datavalue":{"value":"disjoint chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q5937251$63BFDA21-C895-442C-90E4-9409B6E2A0C1","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":"Q5937251$3F99F631-846F-4CA4-9F56-1B04B2E69795","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52dd163c8b27cd250cc4dd61e7c397fd957e4c06","datavalue":{"value":"https://doi.org/10.1006/jcta.2000.3148","type":"string"},"datatype":"url"},"type":"statement","id":"Q5937251$2638F08F-6201-487D-BE19-7F1B41FE12D3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3d22050cff4178f70d08741d77db5eaf51c95cfd","datavalue":{"value":"W2079996283","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937251$0BFAF8D2-AB46-455D-8451-2F6EA29C32BD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937251$796DF2B6-B2CC-4CD3-AC5E-FF54D54C4847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4dd8e6b39a9c57a40d5ec7b3e1872397957b3b2","datavalue":{"value":{"entity-type":"item","numeric-id":5932642,"id":"Q5932642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5937251$AEB2EFE6-3168-4A5F-AA27-22BF1DAE335D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6de321c2829aea917f9dd3a6c75663c011dacffa","datavalue":{"value":"10.1006/JCTA.2000.3148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5937251$EAFC6698-C0E8-4962-90B4-3276EC2188A8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b1e4f30eeea2764c70c1fabf8637e08a215883","datavalue":{"value":{"entity-type":"item","numeric-id":1919667,"id":"Q1919667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81adddc54dcf5c67b23eeb712b4704d475bdba94","datavalue":{"value":{"amount":"+0.7938433885574341","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":"Q5937251$185A8328-4CD3-4FE7-A59F-F2CCFEDCA495","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da872b773fc403578e4a2f60ab65a7a6fa8ac600","datavalue":{"value":{"entity-type":"item","numeric-id":4583638,"id":"Q4583638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0070067d72c3d2c219b19e399a831faefa5fdd5","datavalue":{"value":{"amount":"+0.791921854019165","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":"Q5937251$E0C3FD76-5FEA-49CD-80B8-27960A8C0A51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3c73c43d79c07c5339ea1b9dd093a8a8f139c63","datavalue":{"value":{"entity-type":"item","numeric-id":4633778,"id":"Q4633778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1fe8437491280a7c628f1e75b71496fab144295","datavalue":{"value":{"amount":"+0.7806540131568909","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":"Q5937251$165BFE91-07DD-4BBE-948B-A08B501974B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2984171782d22dad4b1ef09dfa2d3395f81e5c3b","datavalue":{"value":{"entity-type":"item","numeric-id":3537062,"id":"Q3537062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd9f06a34da445abd71acbc90c3a450ad449599e","datavalue":{"value":{"amount":"+0.7748387455940247","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":"Q5937251$47A32B98-F9AD-47B4-858B-D0455D8140F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcbf59b7fb1dea96befeeb21ebd9cc4bd4bdf2a9","datavalue":{"value":{"entity-type":"item","numeric-id":3689191,"id":"Q3689191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f009437ea5e926fd22e5d3cdfbb0064cb341f8ed","datavalue":{"value":{"amount":"+0.7605310678482056","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":"Q5937251$729EEBED-7E58-415E-8BB6-3169F1D133D7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On disjoint chains of subsets","badges":[]}}}}}