{"entities":{"Q685701":{"pageid":687550,"ns":120,"title":"Item:Q685701","lastrevid":63462384,"modified":"2026-04-11T13:20:01Z","type":"item","id":"Q685701","labels":{"en":{"language":"en","value":"Poset matching---a distributive analog of independent matching"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 423589"}},"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":"Q685701$725C4C2B-B566-48B6-B5AF-B851D949E157","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2fcaf36383e31db1286fc5d3698286c5a3ed20af","datavalue":{"value":{"text":"Poset matching---a distributive analog of independent matching","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685701$B2FDA690-5572-4B51-BA6C-2687E2F8B009","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5dcbf2501418c2ad6e96e35f5afc1e267276ae38","datavalue":{"value":"0783.05037","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685701$172D2E2E-C6B3-45CF-A42B-1CBA59D3F547","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5979606ef9bc8b3e05379a00ab1d1b39c363f95f","datavalue":{"value":"10.1016/0012-365X(93)90380-C","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685701$0E77F9E4-C365-4245-A2FE-30598A7D0ECE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d9b3fb3ff79ebe0e00ad86f0808334d1b6856038","datavalue":{"value":{"entity-type":"item","numeric-id":584288,"id":"Q584288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$2DB2DE03-77C9-425E-9F09-5F4D29F94769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bf796f2d45c0b21846e6c9c8fc9105d6adc804d","datavalue":{"value":{"entity-type":"item","numeric-id":186254,"id":"Q186254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$6E03AED0-3B99-45CC-9F8A-F5B95E18CE16","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$ADF31128-624F-40FF-8C30-F629A611443A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a4582cf37b19337c7eae16fd67b6e107844c9e6","datavalue":{"value":{"time":"+1993-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685701$11698A74-8398-4CCD-A691-F2A47D126B6C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92e65f8fae7bc956c88a9b4cf24e716c0c0400b8","datavalue":{"value":"If \\((P,\\leq)\\) is a finite poset, \\({\\mathcal F}={\\mathcal F}(P)\\) is the lattice of order ideals and an hereditary system \\(D(P)\\) consists of a collection of order ideals \\({\\mathcal I}\\) (called independent) satisfying: \\(0 \\in{\\mathcal I}\\), \\(A \\leq B \\in{\\mathcal I}\\), \\(A \\in{\\mathcal F}\\) implies \\(A \\in {\\mathcal I}\\). A poset- (or distributive super-)matroid is a \\(D(P)\\) such that T 2.1. giving several equivalent conditions (e.g. (2) \\(A\\), \\(B \\in{\\mathcal I}\\) and \\(| B |>| A |\\) implies \\((B-A)\\) contains a minimal element \\(b\\) such that \\(A \\cup \\{b\\} \\in{\\mathcal I})\\) holds.   The study of poset matroids is among possible generalizations of matroid theory. The authors demonstrate further how useful this generalization is in a variety of ways. The key result is a (cardinality) poset matching algorithm matching independent ideals of \\(D(P)\\) to those of \\(D(Q)\\) terminating after \\(O(N^ 3)\\) appeals to the independence oracles where \\(N=\\max \\bigl\\{ | P |,| Q | \\bigr\\}\\). Specializations of \\(P\\) and \\(Q\\) provide well-known results, including algorithms, while other equally well-known results can be made consequences of the same algorithm. Thus analogs and generalizations of these results are obtained, including an interpretation of the Dilworth completion of a poset matroid in terms of matchings which is used in reducing weighted poset matching to weighted matroid intersection. Along with a selection of examples, the techniques employed provide promising insights into the working of the theory at its present state of development.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$8282C5FC-13D5-4503-8B79-446BFEE777CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685701$1A98BB9F-D714-40E5-A6B8-02BA05B024E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685701$F0B9D088-04C9-49D5-AE2B-B25C77E387DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f3d0b1de78ad0e32d646815f9dc7561538cada7","datavalue":{"value":"06A07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685701$9785A665-80C3-486A-B2D5-C7DA2FE41790","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c7e502f3a2086e535d4bc7dbe8ef97c7e0014c7","datavalue":{"value":"423589","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685701$3FDCD14F-0A7A-4364-9AA2-8DE994B84053","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"916cdd3d2a6f5f57db6bd562990e6d44b7fb3b1d","datavalue":{"value":"transversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$74D67719-3BD4-4C94-A6D9-06B578C590B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6575997fe34f5b3b31e4bef320f03458bbb69c1a","datavalue":{"value":"finite poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$B9636FEA-AA31-4DC0-89B8-FC3A1953F15F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e172629663780e971698d7d841046893adba3be5","datavalue":{"value":"matroid","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$C64F3189-5FB6-4313-8299-EF1932466344","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dcc85f2815db878afee24736da85a916090ce484","datavalue":{"value":"poset matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$B1075D7C-CF93-4FE4-A196-12B1FFC97C21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2eb1b200752208ab0ce08739faeed6d9c7488392","datavalue":{"value":"poset matching algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$CA38DE83-BA4E-48CD-B8F8-C3F402819359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f688ae621af73201a019c8f1194e5d3f579b7573","datavalue":{"value":"matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q685701$27B83F07-5363-4B82-9EBE-7080129888E3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$131091D4-6DD7-427E-A437-3DC741ED1E0B","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":"Q685701$7FC796A4-0F10-40B4-BC0D-0BEE4B2A9363","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e11dedc43587c23aa79cbd80cb927064416a9c4","datavalue":{"value":{"entity-type":"item","numeric-id":5622205,"id":"Q5622205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$B961A373-74A9-47B4-8486-E9C484A9981B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6efee905eeefb30c6a0f645a494b50984e3b482e","datavalue":{"value":{"entity-type":"item","numeric-id":3767357,"id":"Q3767357"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$635D148E-F09C-4F77-B4C2-0274C758F8AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"805453163e57fab8236adc164453eada062acea2","datavalue":{"value":{"entity-type":"item","numeric-id":2652475,"id":"Q2652475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$698A8BC0-6460-4347-A544-0CAB1B7B7599","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"145268d761c65c4413252c4f38f08de69481f3c9","datavalue":{"value":{"entity-type":"item","numeric-id":5516086,"id":"Q5516086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$AE99FD5E-FA4B-4070-892C-CCF3E0711154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb97aa0ae022d4dc38b27f53ae16228cc4072891","datavalue":{"value":{"entity-type":"item","numeric-id":5684698,"id":"Q5684698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$C1430981-C8E6-4ABC-8723-2D7F66539EE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2f1418cda1b0b9a975cd52bf50e78acbd1bc719","datavalue":{"value":{"entity-type":"item","numeric-id":3205244,"id":"Q3205244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$507D8C55-18E0-4D20-BA7E-86D01D01C835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"21e1382e754bf8a68a06b8952808c1a5bb071097","datavalue":{"value":{"entity-type":"item","numeric-id":1140103,"id":"Q1140103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$D8DDA009-C7A5-41A0-9CAE-A1C7CEFFB31C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49f477cb346718646a53a8d5bbd366a232882fdf","datavalue":{"value":{"entity-type":"item","numeric-id":1238815,"id":"Q1238815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$497746F6-F381-4258-84C4-30EBDC56C0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e575039716a0322d9dfa13dd40bf0ddc37088a1","datavalue":{"value":{"entity-type":"item","numeric-id":792355,"id":"Q792355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$44A478C4-F522-45E8-B76D-B66C8AEFD84C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84e98ed7418ceeb8b21234ed45ee16df099c58f3","datavalue":{"value":{"entity-type":"item","numeric-id":3682497,"id":"Q3682497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$B53BB9A4-3D6A-431E-A8C5-B52389CDDF52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77f5d7c11dbdc3a777a1afd6d44a0f41d5c4fdf0","datavalue":{"value":{"entity-type":"item","numeric-id":3768918,"id":"Q3768918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$40A6509F-CCFF-40F6-AC2A-46BDDD0444EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"163439bf15333d78c5f11564941a2c37f94759b7","datavalue":{"value":{"entity-type":"item","numeric-id":3942972,"id":"Q3942972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$CB58EB91-83C0-47F7-9E2E-35F6B833FC54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4387e90954322066e9e805ab9b1ae41440f81e1e","datavalue":{"value":{"entity-type":"item","numeric-id":2556336,"id":"Q2556336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$6DB31472-47BA-4274-829E-DDF2902B56AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$3E9C5019-E35F-4F16-AAF4-912483D26F3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb3759593a12fa6d86fc95ba8c7912d33e4c8752","datavalue":{"value":{"entity-type":"item","numeric-id":4083682,"id":"Q4083682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$B0A261D7-0109-4410-860B-49889123274C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdd0c89aa944e4c2338cc85d129375a6ff616a6","datavalue":{"value":{"entity-type":"item","numeric-id":5566538,"id":"Q5566538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$C7447721-89F7-4B7E-9892-4FF050B4ED13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003460025a2adeabab464a37e821a46c8fa8e444","datavalue":{"value":{"entity-type":"item","numeric-id":4166767,"id":"Q4166767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$AC1DF8A9-E66B-4B66-8B7C-5823ECFA09CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94c5b1899a6a3d61a6406ff24f93eb29bcd034c4","datavalue":{"value":{"entity-type":"item","numeric-id":803140,"id":"Q803140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$256CC13B-F33D-4390-A26A-7EB19BF9D71D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685701$48A135EF-407F-42B9-8A7E-2A21C018A97B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"633cde6e682a15a2165f8690542e46954cd74caf","datavalue":{"value":{"entity-type":"item","numeric-id":792355,"id":"Q792355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"001c11caa355265e826d2bd4598b377a5864d996","datavalue":{"value":{"amount":"+0.8683882355690002","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":"Q685701$DA5374FA-7987-4B7C-B893-0EC8E6659869","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a2c3a4115864a71e8fbf7ea47867f13ea692045","datavalue":{"value":{"entity-type":"item","numeric-id":803140,"id":"Q803140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb43a40e7ba4c30f1eb0dbfb1e1ef96ab979c92d","datavalue":{"value":{"amount":"+0.7814996242523193","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":"Q685701$DA1BD254-C06C-4AEE-B4C4-3D3570890488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fc5c9f3e095f5e06cecf9b0e226e47329386c8e","datavalue":{"value":{"entity-type":"item","numeric-id":1271880,"id":"Q1271880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90077ed9725e6fbb76d4e145c4d1f15c48416aeb","datavalue":{"value":{"amount":"+0.7802630662918091","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":"Q685701$2D2F083A-2438-4C18-B69F-3225D96B952E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b91926af1098fea29f193ab1e8850e9ebe2e91e1","datavalue":{"value":{"entity-type":"item","numeric-id":1812751,"id":"Q1812751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90077ed9725e6fbb76d4e145c4d1f15c48416aeb","datavalue":{"value":{"amount":"+0.7802630662918091","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":"Q685701$43247671-F72E-46C1-9CD0-27E9D2D45503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8284b6caab01f569b3235530f8e156b54aebe093","datavalue":{"value":{"entity-type":"item","numeric-id":5946805,"id":"Q5946805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"687150dcfbaa7e1f5a192e0e4d4f0a0fdad126ed","datavalue":{"value":{"amount":"+0.763156533241272","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":"Q685701$F612E19D-FEB7-42AC-AD8E-7854F12DFB89","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Poset matching---a distributive analog of independent matching","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Poset_matching---a_distributive_analog_of_independent_matching"}}}}}