{"entities":{"Q1041604":{"pageid":1043452,"ns":120,"title":"Item:Q1041604","lastrevid":66610347,"modified":"2026-04-12T11:16:53Z","type":"item","id":"Q1041604","labels":{"en":{"language":"en","value":"A bipartite analogue of Dilworth's theorem for multiple partial orders"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5641710"}},"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":"Q1041604$B184256C-8720-451E-9C63-D716AC5563D8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"30909d11fc2a99115db1dbd31fb061921c1a53c5","datavalue":{"value":{"text":"A bipartite analogue of Dilworth's theorem for multiple partial orders","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1041604$2C4DEAED-E019-4DF2-B0EA-C6E8AB00A49F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5947b73432117dc7e72e9ccb56ccd7509c52482d","datavalue":{"value":"1185.06002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1041604$AFF2E75F-2D64-40B9-91CA-36789EF76024","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"576bcceabff8dce115427e52f43e894dfd6284df","datavalue":{"value":{"entity-type":"item","numeric-id":290804,"id":"Q290804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$1B635C6A-2BD0-41EF-8F14-1E3C9C004E52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b81a4dc49f2cef20908ab5b4ec5273f96d074360","datavalue":{"value":{"entity-type":"item","numeric-id":188717,"id":"Q188717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$8D5B25E6-0FD5-4A6B-9758-12FEC279D3D8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$3A24CAB8-1A89-48F4-BDD5-598E45CFD2A3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05684a6a76ae208e2fab322cb348b334f82a2986","datavalue":{"value":{"time":"+2009-12-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1041604$1568159E-10F0-4BBF-813C-9175A7A0DE79","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f8d859a9381426a6f215ed4c24765501d75033bb","datavalue":{"value":"http://infoscience.epfl.ch/record/129370","type":"string"},"datatype":"url"},"type":"statement","id":"Q1041604$32822255-8143-46DC-A1B2-0DC34C905647","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"af65d326eb3c1d2ea2a1453c9a6f5863957692d2","datavalue":{"value":"If \\(\\prec\\) is a partial order in \\(P\\) and \\(A,B\\subset P\\), then \\(A\\prec B\\) (resp. \\(A\\perp B\\)) means \\(a\\prec b\\) (resp. \\(a\\perp b\\)) for all \\(a\\in A\\), \\(b\\in B\\), where \\(\\perp\\) means incomparable. Then the authors prove several Ramsey-type theorems for multiple partial orders: Let \\(r\\), \\(n\\) be positive integers and \\(<_1,\\dots,<_r\\) partial orders on an \\(n\\)-element set \\(P\\). Then there are two disjoint subsets \\(A,B\\subset P\\), each with at least \\(n/2^{(1+ o(1))(\\log\\log n)^r}\\) elements such that either \\(A<_i B\\) for at least one \\(i\\), or \\(A\\perp_i B\\) for all \\(1\\leq i\\leq r\\).  Another theorem shows that this is not very far from best possible: Let \\(r\\) be a positive integer, \\(0<\\varepsilon< 1\\). There is a constant \\(C(r, \\varepsilon)> 0\\) such that for all sufficiently large positive integers \\(n\\) there are \\(r\\) partial orders \\(<_1,\\dots,<_r\\) on an \\(n\\)-element set \\(P\\) with the following properties: {\\parindent=6mm \\begin{itemize}\\item[1.)] \\(<_1,\\dots,<_r\\) have a common linear extension.  \\item[2.)] For any \\(u\\in P\\) and for any \\(i\\) \\((1\\leq i\\leq r)\\) the number of elements in \\(P\\) comparable with \\(u\\) in the partial order \\(<_i\\) is at most \\(n^\\varepsilon\\).  \\item[3.)] For any pair of disjoint subsets \\(A,B\\subset P\\), each with at least \\(C(r,\\varepsilon) n{(\\log\\log n)^{r-1}\\over(\\log n)^r}\\) elements, there exist \\(x\\in A\\), \\(y\\in B\\), and \\(i\\) \\((1\\leq i\\leq r)\\) such that \\(x<_i y\\) or \\(y<_i x\\).   \\end{itemize}}  As a corollary the following is obtained: Any family \\(C\\) of \\(n\\) convex compact sets in the plane has two disjoint subfamilies \\(A,B\\subset C\\), each with at least \\(n^{1-o(1)}\\) members, such that either every member of \\(A\\) intersects all members of \\(B\\), or no member of \\(A\\) intersects any member of~\\(B\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1041604$99AEFA51-4AF6-4346-BD98-3E58588D66E9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c80e484e125b4b2e6f1eb4b1b0abd66d7cb4aba7","datavalue":{"value":{"entity-type":"item","numeric-id":587966,"id":"Q587966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$BAF1A2F6-6C82-4296-878C-F9AD6F6E65D8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1041604$AA72AFAE-8756-470F-9B3F-9CAFC7BD7557","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c72dbba128ca14caacad822dc6abdfcb8f13547","datavalue":{"value":"5641710","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1041604$1AB22C09-BA03-42D6-A5BC-57D05105B82B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4d09e438694ec4bbdcb420829405ba32befaca3","datavalue":{"value":"Dilworth's theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1041604$DFEC9C22-6C1C-428A-83E5-8572D83A7B4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26b21a231e1a4e7d4575b29ead4f80a851528206","datavalue":{"value":"mulitple partial order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1041604$81200F95-FB7C-4B5A-9361-65B653C2030E","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":"Q1041604$138AC492-295A-4A35-9177-4E3FDAD2F0BD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2ab82e0e43cbd4ab04c343747d433da256571157","datavalue":{"value":"W2163407691","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1041604$298267F6-0F81-4FD2-96AF-21E4CD7C1A26","rank":"normal"}],"P223":[{"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":"Q1041604$7840D3CF-DD8E-4596-8236-62C006125F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bdd29e00cad75ea5f28fb83745cc4247657b4262","datavalue":{"value":{"entity-type":"item","numeric-id":3752383,"id":"Q3752383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$2A74B717-0007-4982-9283-58B699FC7A79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f65a6538200e554e0b902be272e1fa6197fea6dc","datavalue":{"value":{"entity-type":"item","numeric-id":5905915,"id":"Q5905915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$B1A80FA6-D700-45A0-A9B9-AE5553DB4014","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fcfd47c3fe9e0f097b76c7c78a15869fd96ffd9","datavalue":{"value":{"entity-type":"item","numeric-id":4004146,"id":"Q4004146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$EBE79850-8D41-4743-A5CE-A36629FEB914","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf44df8f782f3afcfc8d0ff3e7dc83f61925841","datavalue":{"value":{"entity-type":"item","numeric-id":2489017,"id":"Q2489017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$8BE5B5F8-43D5-4884-B02A-6CD318B70EED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2919e1346493daff537dc3f51d36ba8d62aceef9","datavalue":{"value":{"entity-type":"item","numeric-id":1606025,"id":"Q1606025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$2AB65766-2A3C-40C6-823D-BFD089EC3C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b9df05cfadd429c919e2c6f49687688f6d1327d","datavalue":{"value":{"entity-type":"item","numeric-id":5759552,"id":"Q5759552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$898F543F-961D-47E9-88D7-8D0B76B5E0DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd09f6109a2a26b7c54c3011537519d170fdb9ba","datavalue":{"value":{"entity-type":"item","numeric-id":4314565,"id":"Q4314565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$4EFEE088-E06B-482D-B5B8-22EBFFCC79CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fc3ececa13d0a020f6daca5d5aafdc66a408338","datavalue":{"value":{"entity-type":"item","numeric-id":1330876,"id":"Q1330876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$79BC3ED4-439D-47E6-AF30-94CC9F76E94E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a423e0dca68bd9832034adcbc5f3024591bfa6d","datavalue":{"value":{"entity-type":"item","numeric-id":1971016,"id":"Q1971016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$2475229F-C8A6-4D2E-A48E-3A91EE6ED2C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f44d7abb175171c5fca45f1c262d30f7bf95b434","datavalue":{"value":{"entity-type":"item","numeric-id":4938791,"id":"Q4938791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$47423059-EB06-4940-B633-8D37BE5F8C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92b4b16abcd5ba3cd7963268649b1762088d6ea5","datavalue":{"value":{"entity-type":"item","numeric-id":3990611,"id":"Q3990611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$241FA1EE-4E6E-467B-95B1-5B8C4EC8A330","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b85e56909bcffe16fdb358401cf0bf9d66a0bd1f","datavalue":{"value":{"entity-type":"item","numeric-id":5618375,"id":"Q5618375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$846ECE17-8434-4FD6-A690-0D205F2A71E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f935ca970c1341c7c4f810e85d0118f5600c70","datavalue":{"value":{"entity-type":"item","numeric-id":1380815,"id":"Q1380815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$BF66307C-1763-4DAF-B21E-25324D39E81B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcaebbac4d0ffcbd204c4ac3a7045a03a28c5467","datavalue":{"value":{"entity-type":"item","numeric-id":4525053,"id":"Q4525053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$706ECBBC-617D-4FEA-9CD0-8D0B1CACABE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"086d4f066f2e4993a9be99afc4ef9eee0dd0160e","datavalue":{"value":{"entity-type":"item","numeric-id":862983,"id":"Q862983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$3195FFCB-E06B-45FE-BBC6-00B9EAA0F195","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f328509acb0571d87afc1743c4a2a8f4764d8e68","datavalue":{"value":{"entity-type":"item","numeric-id":5474627,"id":"Q5474627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$93EB1AC7-331B-420E-8A9F-4F9B8F67C315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8cfed7f4900e3e265b78f148b39a5857eb957a6","datavalue":{"value":{"entity-type":"item","numeric-id":1172652,"id":"Q1172652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$135FF418-5AB2-483C-B68E-5AAB65973109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"388626df503ec22598f2d56af043cdc1d19e4a4b","datavalue":{"value":{"entity-type":"item","numeric-id":607823,"id":"Q607823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$7ED5584D-301B-4CC8-90E1-3976E49323F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77c85a18150720b13a8b29643e8007718b0fbdca","datavalue":{"value":{"entity-type":"item","numeric-id":5392191,"id":"Q5392191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$CBD66772-DDA2-4B20-876B-67B737E02D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dea6ee8014164ea0b4ab25365a13b2deaaced58b","datavalue":{"value":{"entity-type":"item","numeric-id":751670,"id":"Q751670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$60075581-C20B-40D9-82E5-57D955008AF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36237799563eb11da5ea9c8cc21b382615052515","datavalue":{"value":{"entity-type":"item","numeric-id":2566809,"id":"Q2566809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1041604$4EF2E446-76BA-4725-A634-A3E74A17BCFD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4eae1be0cd68c1ed8199b9e75f287399f68b8f37","datavalue":{"value":"10.1016/J.EJC.2008.12.004","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1041604$1583AB3C-930C-42E8-97F9-E29CA9E8081D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e8ca94ac07125243279e94cb42d75d0c6e7e7d8","datavalue":{"value":{"entity-type":"item","numeric-id":862983,"id":"Q862983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83e4f2626d6b90234e70cf86daec7b32c78ca7dc","datavalue":{"value":{"amount":"+0.8480448722839355","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":"Q1041604$3539BCC7-4C76-4FBA-928A-6EABAE0C1E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd54cbf25c9f7d8550d7788fc906293a8fa331a2","datavalue":{"value":{"entity-type":"item","numeric-id":2520724,"id":"Q2520724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a13a823bb663cbb6abe31c3d106124d6f287a80","datavalue":{"value":{"amount":"+0.7880582809448242","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":"Q1041604$DBAB7B6E-0B9E-44BF-AC98-17E027C4DBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b4726d5677b8b93d4cec296f9b7d5d5a28619b3","datavalue":{"value":{"entity-type":"item","numeric-id":1330876,"id":"Q1330876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bf365f170e8a13fd4c4d775dd5e80c5714d1b47","datavalue":{"value":{"amount":"+0.7710106372833252","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":"Q1041604$90416DF6-4057-48E4-977F-35DCBB41CC80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51d167990bef8e789a44df8a814580f265523873","datavalue":{"value":{"entity-type":"item","numeric-id":4342018,"id":"Q4342018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f1bf9c0a99517309fdfc7a7ee481ba409eb8326","datavalue":{"value":{"amount":"+0.7688677906990051","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":"Q1041604$22A7E971-218D-40D9-95B0-E5C330CE9472","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23bbd25d1e4afc85327fe94c0a9de5d89e24b73d","datavalue":{"value":{"entity-type":"item","numeric-id":607823,"id":"Q607823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9dfe8f7d2b9551af50a665d455939cc99d8a3b30","datavalue":{"value":{"amount":"+0.7376492023468018","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":"Q1041604$8218B731-CBEC-435F-A546-2E9FD3CE6C0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A bipartite analogue of Dilworth's theorem for multiple partial orders","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_bipartite_analogue_of_Dilworth%27s_theorem_for_multiple_partial_orders"}}}}}