{"entities":{"Q2760994":{"pageid":2771733,"ns":120,"title":"Item:Q2760994","lastrevid":83143670,"modified":"2026-05-07T06:17:20Z","type":"item","id":"Q2760994","labels":{"en":{"language":"en","value":"Integral matrices with given row and column sums"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1682808"}},"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":"Q2760994$C1775939-5548-4F7F-AED7-DFD4CEED60D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bae04cf39e207a6658b60d48d4541b1a0b46dd34","datavalue":{"value":"0977.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2760994$E2DEB38D-69D1-443C-BA0C-BDF25262FEA9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a241874cdab558394c3806d25083b628915834e","datavalue":{"value":{"entity-type":"item","numeric-id":209047,"id":"Q209047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2760994$ECBB3215-31D6-42FF-A755-0127986BB60E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"dd43b7556960d36e19e31bfdf153901cadf12bc7","datavalue":{"value":{"time":"+2001-12-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2760994$72CBE544-EE41-4978-92FC-106165C7E884","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2760994$5D82C10E-3D14-43AE-BC5E-172A2B7ADC40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06299a38dab9dd1c28e96fe2a7f8cac0943d746","datavalue":{"value":"15B36","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2760994$BACC3F97-895B-44DD-AC7E-08B3979625B4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"87181d6421f4b72b600c026193fbc39f304051bb","datavalue":{"value":"1682808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2760994$9E4328F6-4166-42AD-A5D8-240280DA516B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ca3d28349ebc12f8dd0268346d24091eae33dae","datavalue":{"value":"integral matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q2760994$128566B9-FAC8-4CA8-8C97-69C4220890FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9527ea6265f63439699edc7d3ec8cd45a55d81c3","datavalue":{"value":"network flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q2760994$D90F4ED8-57C8-4DBF-952D-18EF1BAA3A0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"654a5a58c541017d9e3a13c64325c4e87c3fdf69","datavalue":{"value":"cut inequality","type":"string"},"datatype":"string"},"type":"statement","id":"Q2760994$A4285321-63E2-41FC-8CB3-C1DB140B2E7B","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":"Q2760994$ED59BD36-772A-450A-9BDC-CB9A0423D0A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"351660d92661191e78486ec1704138e89fca7b87","datavalue":{"value":{"text":"Integral matrices with given row and column sums","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2760994$F51D6B36-19AF-497D-8B67-974CAEAE1343","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6f7fbf6651880b9d76c5e78437f7f8284b8f74c4","datavalue":{"value":{"entity-type":"item","numeric-id":6550664,"id":"Q6550664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2760994$B7C590B2-EB19-4D91-A4A3-3981865697A6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1d8eaa1c201ca1a7cf86a04a818a674b300e5de9","datavalue":{"value":"Let \\(Q\\) be an \\(m\\times n\\) matrix with nonnegative integral entries and \\((r_1,\\ldots ,r_m)\\), \\((s_1,\\ldots ,s_n)\\) two nonnegative integral vectors with the same sum. Does there exist a nonnegative integral \\(m\\times n\\) matrix \\(A\\) having row sums \\(r_i\\), column sums \\(s_j\\), and satisfying \\(a_{ij}\\leq q_{ij}\\) for every \\(i\\) and \\(j\\)? By the maxflow-mincut theorem, \\(A\\) exists iff certain \\(2^{m+n}\\) inequalities among the parameters \\(q_{ij}\\), \\(r_i\\), and \\(s_j\\) are satisfied. Generalizing theorems of Gale and Ryser, Anstee and Chen, the author proves a theorem containing a hierarchy of weaker conditions for \\(Q\\) and \\(s_j\\), under which the existence of \\(A\\) is equivalent to (in \\(n)\\) polynomially many cut inequalities. For example, if NEWLINE\\[NEWLINE\\sum _{i=1}^m(q_{ij}-q_{ik})^+\\leq s_j-s_k+1\\quad \\text{for}\\quad 1\\leq j<k<nNEWLINE\\]NEWLINE, then \\(A\\) exists if and only if NEWLINE\\[NEWLINE\\sum _{i=1}^m \\Bigl(r_i-\\sum _{j\\in J}q_{ij} \\Bigr)^{+}\\leq \\sum _{j\\not \\in J}s_jNEWLINE\\]NEWLINE for every initial interval \\(J=\\{1,2,\\ldots ,h\\}\\) (\\(x^{+}=x\\) for positive \\(x\\) and \\(0\\) else).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2760994$08071AF8-9D9D-4D28-BC9C-F4229C427201","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6f1020581485ed0765aa827546a5c57c3b02d582","datavalue":{"value":{"entity-type":"item","numeric-id":627537,"id":"Q627537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2760994$DDBCD28C-FEC6-4C03-9C94-C093892BA2C2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3758ec6e4019535568337b7d53064f80d0c45656","datavalue":{"value":{"entity-type":"item","numeric-id":1199992,"id":"Q1199992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1bda3ddfb8ee238691e1fb5e9e81c12007d9c70","datavalue":{"value":{"amount":"+0.8547794818878174","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":"Q2760994$3CD7F691-34A6-45D0-BCE8-8A477B75D4CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37ce37a83fb87d662e7c08b1a1d312efd0a6535c","datavalue":{"value":{"entity-type":"item","numeric-id":840652,"id":"Q840652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90b37b0173963ff3417ec51a4b19e65b20e9813d","datavalue":{"value":{"amount":"+0.8420007228851318","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":"Q2760994$68ED4416-F692-45B7-8B01-2DB03898A4AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"834855869ecf9e0e1c8e4b443c452a6cefe51c29","datavalue":{"value":{"entity-type":"item","numeric-id":5935360,"id":"Q5935360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b169dd824a97ea074986323f512d3b1687a563a3","datavalue":{"value":{"amount":"+0.8178420662879944","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":"Q2760994$360B2B0D-856E-4B88-B77B-C9A118CC9026","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"511283d0831efb3350f40f78f97114d261430b1f","datavalue":{"value":{"entity-type":"item","numeric-id":763063,"id":"Q763063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b169dd824a97ea074986323f512d3b1687a563a3","datavalue":{"value":{"amount":"+0.8178420662879944","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":"Q2760994$8EE61284-CCF7-4A51-91D7-E52917321E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5cdedbc1ca8f75838a57b695228b1019bf2387a","datavalue":{"value":{"entity-type":"item","numeric-id":763065,"id":"Q763065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfa53901765295ae213bef64170ea362bca7b1d6","datavalue":{"value":{"amount":"+0.8141430616378784","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":"Q2760994$E2803735-5A50-4000-881A-C80EC4816C1C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Integral matrices with given row and column sums (scientific article; zbMATH DE number 1682808)","badges":[]}}}}}