{"entities":{"Q789399":{"pageid":791247,"ns":120,"title":"Item:Q789399","lastrevid":64352544,"modified":"2026-04-11T19:17:10Z","type":"item","id":"Q789399","labels":{"en":{"language":"en","value":"Packing and covering of crossing families of cuts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3845617"}},"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":"Q789399$B25FF01E-3994-4F1E-8288-81A22E47F672","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3c03a62fb6bb86b390127fad9163394713add797","datavalue":{"value":{"text":"Packing and covering of crossing families of cuts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q789399$28560855-4AE2-4775-9E6B-7F2B0858F8C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a6f0b1283c38909101a047a8a6a75e47ccf49c20","datavalue":{"value":"0533.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$9A12AD5A-1C34-4997-A0C4-25691EC49AB6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9cfb689d4f0149f49c722dcdf5eeb81abce7d64","datavalue":{"value":"10.1016/0095-8956(83)90066-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$1E82A03A-E538-4DD7-A386-A4D70024EBA5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$56E550AA-A9B4-4922-A529-21252485B827","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q789399$AC3DC643-8D6C-4767-8BD5-46DD6D9DC8DC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3e6da941b05229469cdbe8f69c745e36d813761a","datavalue":{"value":"https://ir.cwi.nl/pub/10050","type":"string"},"datatype":"url"},"type":"statement","id":"Q789399$7F4D02ED-8153-416B-A3A0-0B9A8833AD33","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd799385929326511197b98a5fa0c2787073e94f","datavalue":{"value":"The author's summary: ''Let \\({\\mathcal C}\\) be a crossing family of subsets of the finite set V (i.e., if T,\\(U\\in {\\mathcal C}\\) and \\(T\\cap U\\neq \\emptyset\\). \\(T\\cup U\\neq V\\), then \\(T\\cap U\\in {\\mathcal C}\\) and \\(T\\cup U\\in {\\mathcal C})\\). If \\(D=(V,A)\\) is a directed graph on V, then a cut induced by \\({\\mathcal C}\\) is the set of arcs entering some set in \\({\\mathcal C}\\). A covering for \\({\\mathcal C}\\) is a set of arcs entering each set in \\({\\mathcal C}\\), i.e., intersecting all cuts induced by \\({\\mathcal C}\\). It is shown that the following three conditions are equivalent for any given crossing family \\({\\mathcal C}:\\)    (P1) For every directed graph \\(D=(V,A)\\), the minimum cardinality of a cut induced by \\({\\mathcal C}\\) is equal to the maximum number of pairwise disjoint coverings for \\({\\mathcal C}.\\)    (P2) For every directed graph \\(D=(V,A)\\), and for every length function l: \\(A\\to {\\mathbb{Z}}\\), the minimum length of a covering for \\({\\mathcal C}\\) is equal to the maximum number t of cuts \\(C_ 1,...,C_ t\\) induced by \\({\\mathcal C}\\) (repetition allowed) such that no arc a is in more than l(a) of these cuts.    (P3) \\(\\emptyset \\in {\\mathcal C}\\), or \\(V\\in {\\mathcal C}\\), or there are no \\(V_ 1\\), \\(V_ 2\\), \\(V_ 3\\), \\(V_ 4\\), \\(V_ 5\\) in \\({\\mathcal C}\\) such that \\(V_ 1\\subseteq V_ 2\\cap V_ 3\\), \\(V_ 2\\cup V_ 3=V\\), \\(V_ 2\\cup V_ 4\\subseteq V_ 5\\), \\(V_ 3\\cap V_ 4=\\emptyset.\\)    Directed graphs are allowed to have parallel arcs, so that (P1) is equivalent to its capacity version. (P1) and (P2) assert that certain hypergraphs, as well as their blockers, have the \\(''{\\mathbb{Z}}_+\\)-max-flow min-cut property''. The equivalence of (P1), (P2), and (P3) implies Menger's theorem, the K\u00f6nig-Egervary theorem, the K\u00f6nig-Gupta edge- colouring theorem for bipartite graphs, Fulkerson's optimum branching theorem, Edmonds' disjoint branching theorem, and theorems of Frank, Feofiloff and Younger, and the present author.''","type":"string"},"datatype":"string"},"type":"statement","id":"Q789399$9981F41D-AF4A-4ED0-9119-87670FE0B3FB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$599ED896-9710-44DF-A085-67BA46B6F36F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$312ADDA7-8696-4DF7-B0D0-2761E5AFBF31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$87D0BC98-7FC1-440F-A72E-C68A2E26B729","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"90b3c3d46eb91efc4aa3e62279e6b06d0080e82e","datavalue":{"value":"3845617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$95243A7F-C877-4336-A8F4-FACD4E1C9714","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92aadd2f584a4cda8cbdac97b8054f4c456d8e79","datavalue":{"value":"crossing family of subsets","type":"string"},"datatype":"string"},"type":"statement","id":"Q789399$7F5154C2-378B-4420-BD1D-E4B630B56D4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d142027bf3153eebb876131ac5297907f4e838","datavalue":{"value":"covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q789399$4FF0224A-02BE-4B91-8013-8A0A9FBD2346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e984adb86ecfd745f8c2b2f4daabbab1477ce54","datavalue":{"value":"minimum length","type":"string"},"datatype":"string"},"type":"statement","id":"Q789399$B17695C7-AB0E-4E14-A048-008958C4151E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3a4fd1d48c8b6c2d23f1aaef9ccba0abd10cbf8","datavalue":{"value":"max-flow min-cut property","type":"string"},"datatype":"string"},"type":"statement","id":"Q789399$E0453C9E-67C1-43FA-821C-89B60961CC7E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"384e76e68b4ad8fc5526b0946faf98184da0b8ee","datavalue":{"value":{"entity-type":"item","numeric-id":1844682,"id":"Q1844682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$A755760D-7A28-4220-A68E-562881F02780","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":"Q789399$0409992F-F403-4526-A51F-3D8E9C33521A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"953d5c421d36ad3fb5e3114eacb473e8c123aa00","datavalue":{"value":"W1992939576","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q789399$90F8D0C3-F4DB-42B9-97B9-0BF9166F01EC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"15f52f870ad292e6859cff707a0a4972166341df","datavalue":{"value":{"entity-type":"item","numeric-id":5636932,"id":"Q5636932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$752FCF3A-7CA5-4471-9237-4D4C1F0D7C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43798c19208231d39c6c4f059a0476d674a2816f","datavalue":{"value":{"entity-type":"item","numeric-id":4149476,"id":"Q4149476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$9F73D6C7-4E1A-4BD5-BB13-04F329FA8D6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"346ef1e2101e3cfc3087ff5451189e85d86b41fc","datavalue":{"value":{"entity-type":"item","numeric-id":1101126,"id":"Q1101126"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$79DC3AA1-051B-4099-99B3-80268B7409EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5a9d0d3f3eed97c046667c6b73bcfa8b563580e","datavalue":{"value":{"entity-type":"item","numeric-id":3859792,"id":"Q3859792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$9F535EDA-0768-477F-B17A-F531985CD80F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f70d362cfa7331a9394c39182700aab103850eb0","datavalue":{"value":{"entity-type":"item","numeric-id":5572841,"id":"Q5572841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$C01579E4-9B07-48DE-9866-ADB8C3E4CD41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cad6d6356fb2aabced35b1a059812873a319983d","datavalue":{"value":{"entity-type":"item","numeric-id":4769069,"id":"Q4769069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$EB3F9BEB-F955-487B-AC6E-4B3B9042B96F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f466a34af260f693e4133c37ba4502bfc87bc5d1","datavalue":{"value":{"entity-type":"item","numeric-id":5722271,"id":"Q5722271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$FC3ABD26-46DE-45D9-8E9B-8E5E19ACA1E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"004607767258f476a197c3a5eaf971a22c094d9a","datavalue":{"value":{"entity-type":"item","numeric-id":3236252,"id":"Q3236252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$2314EFF0-34CF-437E-A4E9-18A7F11B23BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4a40eec7c3892237ba8733670ebe1f5506614d1","datavalue":{"value":{"entity-type":"item","numeric-id":1229885,"id":"Q1229885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$30E7DF85-414F-4EB2-ABA6-768FB13AA810","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b04f097f7dc1fd904f6cdf5a8381ac06fb83404","datavalue":{"value":{"entity-type":"item","numeric-id":4173379,"id":"Q4173379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$ADA12E08-1F3A-4D80-B683-E07D0F5F99CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4354f78f20cfb241d0c5cc1f9148754b47c7b23c","datavalue":{"value":{"entity-type":"item","numeric-id":1145156,"id":"Q1145156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$1575B821-EA09-45CC-A497-49D6711B60AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4c401dbe104705de719d56e47bb57853d326cd99","datavalue":{"value":{"entity-type":"item","numeric-id":3960724,"id":"Q3960724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$05143114-30C8-4E3A-BFBB-CEDD7548B368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bb206c347ef9d68a06fab9ec3fc669614a833ba","datavalue":{"value":{"entity-type":"item","numeric-id":3313630,"id":"Q3313630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$DD9BFEF0-FC2A-4C39-938E-96EB405206F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"119d14273a5178c9fdb0109f5da7d88db66c689c","datavalue":{"value":{"entity-type":"item","numeric-id":1245970,"id":"Q1245970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$CE9E1430-9B86-4E26-A30F-C0C2785F9F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e99da589d7100fee8c775ba840d0a2287dbe7cc7","datavalue":{"value":{"entity-type":"item","numeric-id":4198789,"id":"Q4198789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$5E42BD79-240B-4D64-83FF-80C649F5B8FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c9b20e00a8b8099c56cf57c76c00569db5d91d2","datavalue":{"value":{"entity-type":"item","numeric-id":1216325,"id":"Q1216325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$5C666ADA-B288-4289-95A7-E0E04F0F7984","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2dbf8d5cbd9ece6bead4e0fa5d545881c7f63f46","datavalue":{"value":{"entity-type":"item","numeric-id":6481473,"id":"Q6481473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q789399$A5F82FC8-382A-46E0-B4A4-9DB992A07F56","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bd1c4aa1f0797f1888499f72b7b827d5253cadd","datavalue":{"value":{"entity-type":"item","numeric-id":3688403,"id":"Q3688403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3be87809a8911aad18d78f16a67cb62b150fd5ee","datavalue":{"value":{"amount":"+0.8342145085334778","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":"Q789399$583F94A3-71E4-490B-B456-A1366EED19EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bcc731f11439faad88ef194d0e1757840189a210","datavalue":{"value":{"entity-type":"item","numeric-id":1082240,"id":"Q1082240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea9e232e7b299e7feed341e3d80028137bad2180","datavalue":{"value":{"amount":"+0.811013400554657","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":"Q789399$6ED90D89-23C8-433C-9392-DC5641CEAC4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f4f313d0520d12370c3fe7f4af9ee3def17b09","datavalue":{"value":{"entity-type":"item","numeric-id":1300055,"id":"Q1300055"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a3c845231ca766e5dad514cc793fd180c3c81ff","datavalue":{"value":{"amount":"+0.7924599051475525","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":"Q789399$EFD2FD54-DC03-4C8F-BB76-D1BF370010D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eec7f01293ffe234c97da08c516144dff180913f","datavalue":{"value":{"entity-type":"item","numeric-id":873653,"id":"Q873653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50c536378acf3126b17015e9adca079bc90e479b","datavalue":{"value":{"amount":"+0.7842274308204651","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":"Q789399$F38C0C64-2527-4782-92F4-91E5B9A961B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"336616a0057ec4829c585514a4d2a216a03ad34e","datavalue":{"value":{"entity-type":"item","numeric-id":3330974,"id":"Q3330974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb90b57591bac91abf37a483eaff31721a04d295","datavalue":{"value":{"amount":"+0.7809238433837891","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":"Q789399$FF88BE59-0330-41A8-AFD7-885DBB997063","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Packing and covering of crossing families of cuts","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Packing_and_covering_of_crossing_families_of_cuts"}}}}}