{"entities":{"Q1924487":{"pageid":1935229,"ns":120,"title":"Item:Q1924487","lastrevid":69674424,"modified":"2026-04-13T08:37:56Z","type":"item","id":"Q1924487","labels":{"en":{"language":"en","value":"All 0-1 polytopes are traveling salesman polytopes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 936869"}},"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":"Q1924487$4EC4A6FC-7E03-48F3-AAB6-8303C6EDEE92","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ed8e49ee5043c9f64a4d7d04a0d3a8a3d2a4837","datavalue":{"value":{"text":"All 0-1 polytopes are traveling salesman polytopes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1924487$F7668F91-C1F4-4DF0-8168-E8E7CD3244D1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f1d0bbd6449bcdc89a4506f1243d1d9adc14c3ba","datavalue":{"value":"0859.52002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$4C28D4C9-B036-45A8-8D3D-B9040EF11606","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3949785bfba5ce0ce6302177e486679f0a698e5f","datavalue":{"value":"10.1007/BF01844844","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$BA3EAC18-E3E9-4987-9102-D7BE2BE25E26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ee31b78a253b55143e6fdc173b73eed5c226d92c","datavalue":{"value":{"entity-type":"item","numeric-id":1356084,"id":"Q1356084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$E1FDB2FF-60D3-4BEE-B79F-82B5CEB026C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec53c52d3473e8744dd98741117aee8c49ad84c8","datavalue":{"value":{"entity-type":"item","numeric-id":162908,"id":"Q162908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$ADFC7D43-B73C-4E0D-A050-24123D519596","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$566FCB3C-7E1A-4C56-82CA-AAD15278F424","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"18c3bb1a11dba9f99423cf053a5921485bdadd22","datavalue":{"value":{"time":"+1996-10-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1924487$BE7580A0-32CB-42F4-9C9B-890FC9F4E058","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5a60b55db0a87d71662e1faff94b1bfe3369f356","datavalue":{"value":"Two permutation polytopes are studied: the assignment polytope \\(B_n\\), defined as the convex hull of the set of \\(n\\times n\\) permutation matrices, and the asymmetric traveling salesman polytope (TSP) \\(T_n\\), defined as the convex hull of the set of those \\(n\\times n\\) permutation matrices corresponding to \\(n\\)-cycles. It is proved that the face lattice of \\(B_n\\) is isomorphic to the lattice of all elementary subgraphs of \\(K_{n,n}\\), the complete bipartite graph with colour classes of size \\(n\\) (the elementary subgraphs are those having the property that each of its edges is in some matching), and that all faces of \\(B_n\\) have the property that any two vertices are contained in a cubical subface of dimension at most the integer part of \\(n/2\\). Concerning the TSP, the authors prove that any 0-1 polytope \\(P \\subset R^d\\) with \\(2^d-k\\) vertices, \\(k>1\\), appears as a face of \\(T_n\\) for \\(n\\geq (4k+1)d\\) and is the asymmetric TSP of some directed graph with \\(n\\) nodes (the asymmetric TSP \\(T_D\\) of the directed graph \\(D\\) is the convex hull of the set of permutation matrices associated to the tours in \\(D)\\). The maximum diameter of \\(T_D\\) over all directed graphs on \\(n\\) nodes is proved to be the integer part of \\(n/3\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924487$125E9C4A-3081-4C9A-A370-1B3766880BDC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$6911FD8A-6B5F-4230-8AAA-1714FE2BF814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$8D7C5E30-1490-4B96-A3C5-2611A4681AF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$8B89BD4B-5888-4186-B928-0E0AB00142BD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"04dbf425e098f7000ccfecedf44963ab7af6a98d","datavalue":{"value":"936869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$6D825EBE-0145-42E2-A08C-F400A3CCE9A7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4a17f0ded126fefc772d17e962d584f9a1f40b8f","datavalue":{"value":"permutation polytopes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924487$F5D359C9-5A04-4AA3-8AD7-EF6EE5E2CF2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8633bec3cf09e680221c191f8feb0b3206dfdbfe","datavalue":{"value":"assignment polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924487$7246A2C0-D4E0-48BA-A755-F534C7CFDB69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6cd25ce9b252b29da3135d4a186137b1916fd5ff","datavalue":{"value":"asymmetric traveling salesman polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924487$25733605-DF95-426C-A33D-3122C7D0A531","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7ebcf234160d8cb41585f7ceaaefc5d828eba52","datavalue":{"value":"0--1 polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1924487$4596C2D4-8F24-4B37-97BE-C062A620D8C9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b318ed39513978bb8b4ec7cd640a287b23ae9923","datavalue":{"value":{"entity-type":"item","numeric-id":242552,"id":"Q242552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$B485F8A4-0BA3-40D1-A2B7-4FCAF739FAD5","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":"Q1924487$330739A3-EA06-4C2C-BEF0-08956C250E64","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f7c91d07f8da6f141bde7b59eb876224c598c75","datavalue":{"value":{"entity-type":"item","numeric-id":4026491,"id":"Q4026491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$34FDBA6C-396A-499B-811B-1FCF2B33DED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"256a1ca42e8b51711c418b56df6e4b357d669a29","datavalue":{"value":{"entity-type":"item","numeric-id":4867143,"id":"Q4867143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$A5946574-07CA-4256-8150-2078981A2E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ec3f0850b5052d599eb8128d6f1fe3684916d2","datavalue":{"value":{"entity-type":"item","numeric-id":1242975,"id":"Q1242975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$C9674B3F-25D3-4330-A251-BE5D1943549C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31c01dca2db0d76af49bd8fcbd6cb144a377835a","datavalue":{"value":{"entity-type":"item","numeric-id":4116282,"id":"Q4116282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$094064E9-FA05-4681-B304-223D99123D14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ce2a67917373e5b4e39d7c86d75e3ad261de966","datavalue":{"value":{"entity-type":"item","numeric-id":4323295,"id":"Q4323295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1924487$F77C9FF0-1343-44DB-AD00-FE4BC8F6E717","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0aeb3e81dc930838b0df91e815f8e447df46be04","datavalue":{"value":"https://doi.org/10.1007/bf01844844","type":"string"},"datatype":"url"},"type":"statement","id":"Q1924487$6FC57AA9-2CEF-473A-AF33-16205870D19C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"58e44f1cf6a927f3af10e2116e2a107a08a09a02","datavalue":{"value":"W1989428327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1924487$14B83E22-A3F7-42BB-AC99-DFEE6F853643","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f68f35ee4143958619afa48905f641defa3eb66","datavalue":{"value":{"entity-type":"item","numeric-id":4867143,"id":"Q4867143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9bab5b2b7d47d2b7f9fe40c55a0b999ff34d337a","datavalue":{"value":{"amount":"+0.8355457782745361","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":"Q1924487$36054FBE-9DED-45A4-A43E-5548D2E99F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c79a3cdc9e3573b0779a0cd6fa46661c68236e4","datavalue":{"value":{"entity-type":"item","numeric-id":1271383,"id":"Q1271383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1311eff4e099c74825088fe60583e8c890044440","datavalue":{"value":{"amount":"+0.8293212652206421","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":"Q1924487$60A361AB-D65D-4220-A116-10CD7EC54B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e616bac174445964f185aa34994a627cceaf1fd","datavalue":{"value":{"entity-type":"item","numeric-id":5203058,"id":"Q5203058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ade59d07617a6657cba4728a6a740da55e67db98","datavalue":{"value":{"amount":"+0.8257650136947632","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":"Q1924487$A7426DC0-5DB1-4264-BA28-2D3A08EFFC63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"729b0c19636bc4061ca20d8be33e042919194c6e","datavalue":{"value":{"entity-type":"item","numeric-id":4210210,"id":"Q4210210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"802c981ca314024a81ae30d1e4569650912d3385","datavalue":{"value":{"amount":"+0.8122913837432861","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":"Q1924487$56430797-F7B1-41BA-9C73-AD7C38AB2DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97c6a0cba5cc451dec6180629069752591c7b06a","datavalue":{"value":{"entity-type":"item","numeric-id":3714900,"id":"Q3714900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"802c981ca314024a81ae30d1e4569650912d3385","datavalue":{"value":{"amount":"+0.8122913837432861","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":"Q1924487$FE1C2240-1513-4EC2-AC4B-6108593F190C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"All 0-1 polytopes are traveling salesman polytopes","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/All_0-1_polytopes_are_traveling_salesman_polytopes"}}}}}