{"entities":{"Q2351019":{"pageid":2361762,"ns":120,"title":"Item:Q2351019","lastrevid":57875769,"modified":"2026-04-02T22:00:37Z","type":"item","id":"Q2351019","labels":{"en":{"language":"en","value":"Small extended formulations for cyclic polytopes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6450888"}},"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":"Q2351019$D39A52FD-6EDE-474E-804C-0D4284620F81","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1341f28b109f57d6de7fa04f8c483471a00ff808","datavalue":{"value":{"text":"Small extended formulations for cyclic polytopes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2351019$7BDAC0D2-9CA2-41E9-B205-2808C35D45ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a43a9b1437bd6449118ec0b7d4b54bba0c1dfa9e","datavalue":{"value":"1354.52013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$D8745783-0322-41D4-9C39-EE1AA93B845B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a62faf59eb1f66c3822e5e1d665d326cce184ae6","datavalue":{"value":{"entity-type":"item","numeric-id":2351017,"id":"Q2351017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$9E3191C0-3432-4AB2-B3EA-B5450E925F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6be138e27f4fbac72f6efdc6dc3eb9c65525ae8a","datavalue":{"value":{"entity-type":"item","numeric-id":210516,"id":"Q210516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$2ECF23D5-E286-4E8E-B681-EE8A534BC160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec1eea64dd04befec6ae613d9611d6f2d0cf5a19","datavalue":{"value":{"entity-type":"item","numeric-id":263203,"id":"Q263203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$002E9D6E-D7AF-491F-A466-23E6210056E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"53cb81cdd53968aea8fa23485cb8bd36b9aef8cc","datavalue":{"value":{"entity-type":"item","numeric-id":1741476,"id":"Q1741476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$4E86F272-223C-4C0F-971F-AE6183F7BE9A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b6f367138a9ac2b85113cfed5a6fd5bedcc8944c","datavalue":{"value":{"entity-type":"item","numeric-id":178842,"id":"Q178842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$E0AC7401-3E0F-42A0-AB42-0DA6940CA7C6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4795efe26ace72ea33e5b50072c8db0e5047722","datavalue":{"value":{"time":"+2015-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2351019$27A5339D-E2F2-45D8-9A40-8EC78F7B9EA1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"956be8c913197b6825eaefbcbe47e928eb6b762e","datavalue":{"value":"https://arxiv.org/abs/1401.8138","type":"string"},"datatype":"url"},"type":"statement","id":"Q2351019$5D36C28D-F779-4DEE-9392-1B5F85EBA997","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eac62fcd49a5b777dfe7d0dca62b5534f4bb9a32","datavalue":{"value":"The extension complexity of a convex polytope P is the minimal number of linear inequalities describing a polytope that projects to P, i.e. the minimal number of facets of such a polytope. In general, the extension complexity of P may be much less that the number of facets of P itself. See [\\textit{M. Yannakakis}, J. Comput. Syst. Sci. 43, No. 3, 441--466 (1991; Zbl 0748.90074)] for a linear-algebraic reformulation of this notion.  The main result of the present paper is as follows: the extension complexity of the d-dimensional cyclic polytope with \\(n\\) vertices does not exceed \\(O(\\log n)^{\\lfloor d/2 \\rfloor}\\). For cyclic polygons, the proof is based on an explicit construction of a covering polytope with few facets. For arbitrary dimension, the proof is less straightforward and is based on the aforementioned algebraic reformulation of the extension complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2351019$D5DADA16-B0F0-4271-9DFF-EA988A28E953","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$0322A49F-C277-44C9-A6ED-BBC63AACD6EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"798eea1f37baf19c7c9678fe1fc9dd8eadfa6f52","datavalue":{"value":"52B11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$034FD811-AD5C-4FDF-8691-CB2FF5B03CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8ede024a2e42be41193baf32f90dd58f10db2ea3","datavalue":{"value":"52B12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$7FF0C49F-D0B1-4076-A8CA-3CA133CD3FC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a6a2c74d94f9e1338e2e240249058bd2aa872fba","datavalue":{"value":"52B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$1DD549DC-B6F1-4262-A43B-9E1C80F886CA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b116e0dec83404cbc32e8f15b94f2fded8e1b2d1","datavalue":{"value":"6450888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$CDAD7131-45D8-4F18-832C-F3A346216E38","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b85a35423d79438ae794574da31bce9c9328255c","datavalue":{"value":"polytope extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2351019$C4A3ABBB-10E1-403A-8F67-798D8326585A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ac23b4c07abc06c0458571ed46654a74a8f62f0","datavalue":{"value":"cyclic polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q2351019$72F4C403-FF3B-4D99-8A26-08130D9C63E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e0d72863ba55487de80523c9d2e5dabda94ece2a","datavalue":{"value":"nonnegative factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2351019$BC9EEBB2-6C22-4CFF-880D-C0B0A793FD89","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0d0ca208637869600b02d1c1bf38d240daf9aa29","datavalue":{"value":{"entity-type":"item","numeric-id":303593,"id":"Q303593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$2771E382-5E80-4134-8B9B-675BD11092AC","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":"Q2351019$E58B6879-BAE5-4145-8B2F-D5EE885BD5ED","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"85aeefaf5b296b58a6ad411425d24c61cba69516","datavalue":{"value":"W3101583628","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$340A315B-8064-4A10-B35B-CDA78765590E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e74e2ed89e403009f54a72e385ad2f986b561062","datavalue":{"value":{"entity-type":"item","numeric-id":1759811,"id":"Q1759811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$DBF0C9B2-D1EA-44D1-8F33-29D651F52CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf6f62ac0f38c43941d5f3ab2ee8aef0a7907f3b","datavalue":{"value":{"entity-type":"item","numeric-id":714985,"id":"Q714985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$37B21593-E1D0-4F0B-B11D-7110DD49661B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb36df73a03f449f5e819e41d24c4099708bbd4b","datavalue":{"value":{"entity-type":"item","numeric-id":4434671,"id":"Q4434671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$688C56B3-1BAF-441D-8D20-78B8C2B723EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b04f51ad425b4d13fc4f51a11e18e7c0666c3798","datavalue":{"value":{"entity-type":"item","numeric-id":5265165,"id":"Q5265165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$D07417B4-B507-4774-8587-58CF512C2DD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3c1f607610f03c3a8eea425b05e4e8f743f94a3","datavalue":{"value":{"entity-type":"item","numeric-id":1186549,"id":"Q1186549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2351019$5D5440F8-1326-457B-AEBA-4A4C13C21844","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":"Q2351019$792F69B3-8965-4B8F-9258-F3064004F20E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d8e3a53a50a9012ea39b2cd1a0a5db9901fb231d","datavalue":{"value":"10.1007/S00454-015-9682-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2351019$A3BC1796-87DB-4193-8B7B-D11DB3890ABA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4549b647dc0df093403d703f741b50dde5a0a18","datavalue":{"value":{"entity-type":"item","numeric-id":1759811,"id":"Q1759811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8223a3969b69c366a93a422a3e72ffb5f1dbd02e","datavalue":{"value":{"amount":"+0.8253837823867798","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":"Q2351019$D0EA7D16-8304-425B-9C07-1D48D328624E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b7a79bbd5da357156d1766c54d8e897f298e29a","datavalue":{"value":{"entity-type":"item","numeric-id":3167620,"id":"Q3167620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e44688fefc45aff59dee461e84e08e110825664e","datavalue":{"value":{"amount":"+0.7945619225502014","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":"Q2351019$DD822546-9984-47FF-ACE4-0269EAF57DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca44a70ec9c29a8fa4488014cd0a22fa46468f37","datavalue":{"value":{"entity-type":"item","numeric-id":3569814,"id":"Q3569814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f7200007d5a339190692daac4774d60050fe82b","datavalue":{"value":{"amount":"+0.7805620431900024","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":"Q2351019$AB1FE4F5-CAC2-438A-8431-C7A61C15A70A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc204f7dd2d8474459f53577b1aaac5dac42cb4b","datavalue":{"value":{"entity-type":"item","numeric-id":4899066,"id":"Q4899066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7212d633723ac03de1ff78b04e54d2b8c74ed562","datavalue":{"value":{"amount":"+0.7732925415039062","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":"Q2351019$83B154D9-6CEC-405D-8585-F2B05B9E72BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"046f00895382653dabb7ae5f4517fac446d30171","datavalue":{"value":{"entity-type":"item","numeric-id":714985,"id":"Q714985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"217b91882b579cf9c90384374177de3fdda36b97","datavalue":{"value":{"amount":"+0.7646883130073547","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":"Q2351019$F3F94A1E-895D-4EB7-A7A5-9A692BA915C5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2351019","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2351019"}}}}}