{"entities":{"Q745680":{"pageid":747529,"ns":120,"title":"Item:Q745680","lastrevid":64024509,"modified":"2026-04-11T17:08:12Z","type":"item","id":"Q745680","labels":{"en":{"language":"en","value":"Tropical lower bounds for extended formulations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6494240"}},"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":"Q745680$ECA6FEBB-7DFF-4D50-8B73-A2E375F9511D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2f6344af06316a33df11a7b9119886a326285abb","datavalue":{"value":{"text":"Tropical lower bounds for extended formulations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q745680$06C03B78-731F-44B0-867A-72AA70D4361D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"52c85e55b467d50539ed66dee79e76fc82dff96f","datavalue":{"value":"1331.15021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$83E06180-E85B-4C22-86A1-791968E10AB9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$B4E65B3E-03BC-4795-A073-A8CFC1F06C5D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a6da9e42eaa58730e2d307270239a6044be72e45","datavalue":{"value":{"time":"+2015-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q745680$98130BA3-89EC-47FE-89FC-61F9DD60F29A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4ab06555a84f66274b84e1227610d99ab300ba13","datavalue":{"value":"Let \\(A\\in\\mathbb{R}^{f\\times n}\\) and \\(b\\in\\mathbb{R}^{f}\\) and suppose that \\(P\\) is the polytope in \\(\\mathbb{R}^{n}\\) consisting of all points \\(x\\) such that \\(Ax\\geq b\\). If \\(s_{1},\\dots,s_{v}\\) are the vertices of \\(P\\), we define \\(S(P,A,b)\\) as the \\(f\\times v\\) matrix whose \\(i\\)th column is \\(As_{i}-b\\) and call this a slack matrix for \\(P\\). The extension complexity of \\(P\\) can be characterized as the least integer \\(q\\) such that \\(S(P,A,b)\\) can be written as a product of \\(f\\times q\\) and \\(q\\times v\\) nonnegative matrices [\\textit{M. Yannakakis}, J. Comput. Syst. Sci. 43, No. 3, 441--466 (1991; Zbl 0748.90074)]. Now consider the Puiseux series \\(\\mathcal{R} :=\\mathbb{R}[[t]]\\) whose elements are formal series \\(a(t)=\\) \\(\\sum _{e\\in\\mathbb{R}}a_{e}t^{e}\\) for which the support \\(E\\) is a well-ordered subset of \\(\\mathbb{R}\\); define \\(\\deg a(t):=\\min E\\) (with \\(\\deg0=\\infty\\)) and let \\(\\mathcal{R}_{+}\\) consist of all elements with \\(\\deg a(t)>0\\). It is known that \\(\\mathcal{R}\\) is a real closed field under the usual operations of \\(+\\) and \\(\\cdot\\) for series. Since extension complexity is defined by a first-order formula, theorems concerning extension complexity over \\(\\mathbb{R}\\) remain valid over \\(\\mathcal{R}\\). The image of \\(\\mathcal{R}_{+}\\) under the degree map \\(\\deg\\) is \\(\\mathbb{R}_{+}\\cup\\left\\{ \\infty\\right\\} \\) and the operations \\(+\\) and \\(\\cdot\\) are mapped onto the tropical operations \\(\\oplus\\) (minimum) and \\(\\otimes\\) (usual \\(+\\)). The author is interested in showing how this latter map can be used to infer results about the extension complexity of a polytope. For example (Corollary 4.2), he shows that if \\(\\mathcal{P}\\) is a polytope in \\(\\mathcal{R}^{n}\\) and \\(S\\in\\mathcal{R}^{m\\times n}\\) is a slack matrix for \\(\\mathcal{P}\\), then the extension complexity of \\(\\mathcal{P}\\) is not smaller than the tropical factorization rank of \\(\\deg S\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$24FFCDC6-6992-4E6F-A62E-355D3225E51E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bac883d785667a63a92fc8927c00d4d1184f1321","datavalue":{"value":{"entity-type":"item","numeric-id":590084,"id":"Q590084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$3BDF3159-4011-4B9C-88D6-8ABA2B6BFAC7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e5bc850efb57718f8497af55f559776989de771f","datavalue":{"value":"15A80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$F2E520F0-5F3E-4D3C-BB72-D4DCDD01F8EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2762df744fec88c5da60f696833f02907bd4417a","datavalue":{"value":"52B55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$6318F735-C5CC-4E46-8DB4-A8663807636E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3a56ed6d195ea3539360546b34a91d2ad94c0346","datavalue":{"value":"15A23","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$77897610-3218-48A7-AF15-F5C4C72225D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"379993e49d6b3bf4f928ea97a76d4470fec7f1af","datavalue":{"value":"15B48","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$2830C69F-EAA6-410E-8F9C-622F9358F254","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d67efd304ba5bc1f422b0c4639f0b97e4366487c","datavalue":{"value":"6494240","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$9A558784-0167-4D81-96B9-C9B8E6504D3F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f8f9eb00f1f59aba58bc14adce059da0c3bb30f7","datavalue":{"value":"convex polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$51DE375F-64CE-4D2A-91AE-A015EF9BC33F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d1b6156e613b6d6a17aa5dd982de085fdf12d59","datavalue":{"value":"tropical operation","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$DBDF9CD7-A350-4EEC-8E50-93F49AC1474F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da556436970dd537a61e65daf87fc60b05dc9fcd","datavalue":{"value":"extension complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$403C5E89-F242-4D46-B05F-5DAB72759776","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2031a54015f2918ffbb20901e81fba20bf1b4fe","datavalue":{"value":"nonnegative matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$8B22BDEF-1B6F-4F94-89BD-1BEC24890479","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f3f32f345cf89fa38fab9c7fec986e6c2a1acd3","datavalue":{"value":"Puiseux series","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$5C97471A-C652-40AF-814E-873E5D5BEB62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fe89e4f08a9ce83e9bc9cfaf8738d758217b4d73","datavalue":{"value":"tropical factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q745680$1E2AC862-2693-4FF5-9E7C-C4F86A2AC863","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c848be20a9df9788b716f450ec8f21487ece7c32","datavalue":{"value":{"entity-type":"item","numeric-id":1668077,"id":"Q1668077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$FB0D5F93-8E83-452D-8E8B-B6D15EE0D998","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":"Q745680$673D182B-93C6-4EE0-AAEE-BFC2DC8D1D45","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d1dc63c494782dba4283e4df8e394a2fe0ecdd6","datavalue":{"value":"https://doi.org/10.1007/s10107-014-0833-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q745680$402AB342-11B6-47B4-BBDA-84DBD910840B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"38fa1da285ec06a42a67faea87bc521c1f9b4039","datavalue":{"value":"W2073007675","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$F55E60F6-283C-4295-A002-741EF9091E14","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d531d3aaf374d197e52b18caca7fcc915fac8f58","datavalue":{"value":{"entity-type":"item","numeric-id":5415472,"id":"Q5415472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$394646E5-186C-45DD-AA57-D574BC3E5A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"821301906c5a663983ec87a18887c0a4b2f744a0","datavalue":{"value":{"entity-type":"item","numeric-id":4880877,"id":"Q4880877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$D968E21C-31DD-4418-A415-056B972C70B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e5bd1e533841d0a8fe86d39861d8aa1b0903ce7","datavalue":{"value":{"entity-type":"item","numeric-id":452818,"id":"Q452818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$9B558BBC-6716-4749-B0AA-5B6911D6DFC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"869168423f451b6d129fcdf4f3b3f871451fa038","datavalue":{"value":{"entity-type":"item","numeric-id":686375,"id":"Q686375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$17049301-1B6C-4982-AEBB-E38886ED796F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abf3c2a0346c47959acbd7b4e85405896297e8bb","datavalue":{"value":{"entity-type":"item","numeric-id":5900907,"id":"Q5900907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$B115E1D4-3BC3-4A09-BE87-9592C946C990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2143fe6ef2ab316c2ea53384e28464f2bcd2a914","datavalue":{"value":{"entity-type":"item","numeric-id":818678,"id":"Q818678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$34F89461-7ED5-4733-8472-2D90833BCF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"77fd56549136e337ad67107d48f2d866cfa772f2","datavalue":{"value":{"entity-type":"item","numeric-id":5290261,"id":"Q5290261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$D9F25297-F46B-4A3B-9CD9-401838C0E4E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d40653fe2efc692581fead1a0ee75e1057e7c0c","datavalue":{"value":{"entity-type":"item","numeric-id":3661541,"id":"Q3661541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$E00F70CE-A1D7-4A87-A150-3FF98C4B8C12","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":"Q745680$CB2F1BB4-D968-4FB4-853B-327AA61B3CF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"520d989531e844bf041ec66cf059ec44aa03e9ed","datavalue":{"value":{"entity-type":"item","numeric-id":445842,"id":"Q445842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$3CF2F202-254C-47A0-A116-19B484AB01CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99457eb3d271dd61db43f0ba6aa392a357279478","datavalue":{"value":{"entity-type":"item","numeric-id":5169664,"id":"Q5169664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$B36098A3-FACB-4826-BEC8-D19F36A14310","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e53bce14d67355446491fb0c42500c619f4385a","datavalue":{"value":{"entity-type":"item","numeric-id":377501,"id":"Q377501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$66F16929-49C4-4E77-BA0F-ED675D7E81C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"299ef996cc50f523ebb471b5a51255a3f8564abf","datavalue":{"value":{"entity-type":"item","numeric-id":1758469,"id":"Q1758469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$658DAB61-BE18-49E5-A073-F7098297B388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d46ab984ecd8f25dea0b1b407e7e25cbd66bfad2","datavalue":{"value":{"entity-type":"item","numeric-id":4063547,"id":"Q4063547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$518FA08B-8299-41CC-BB84-6659A493D1F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4673762fc8600f4d1309e5ca826d1554a0af67e","datavalue":{"value":{"entity-type":"item","numeric-id":2445938,"id":"Q2445938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$B05B7838-227A-4D72-8B90-F83C1083DCB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"231d76003b36a2f3aa7c94a4ea34d5090f183572","datavalue":{"value":{"entity-type":"item","numeric-id":2341256,"id":"Q2341256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$0B1A17DF-FF60-4DEF-BF29-D7BB32955BBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cdfdd3845c38a6224613732df7bf72a748f722ab","datavalue":{"value":{"entity-type":"item","numeric-id":3448302,"id":"Q3448302"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q745680$047FA3CE-3558-4FB9-89E7-CC505B90198F","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":"Q745680$9C1C3E3B-206D-4555-997F-5944964DD28F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0726e2c261d9053c3c5f8d598cb7b2520b3b240f","datavalue":{"value":"10.1007/S10107-014-0833-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q745680$4A358C32-90E3-4B7C-9244-B8E3A24FD7E1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94acbc1c4de2c43a7849d829cf169fc03772aae0","datavalue":{"value":{"entity-type":"item","numeric-id":3120460,"id":"Q3120460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d36434bd743385ca277e108ac7a5f4a0628c268c","datavalue":{"value":{"amount":"+0.7952414155006409","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":"Q745680$44355B9E-62E3-400B-A6FF-AF8B251E2054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b184457ae05b22ed71d0c1b3e7d7c9496378c24f","datavalue":{"value":{"entity-type":"item","numeric-id":5150211,"id":"Q5150211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03a7d78d104769c290792229f1d881cbe133bac8","datavalue":{"value":{"amount":"+0.749811053276062","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":"Q745680$64947192-C3DE-4609-AE05-4C2DC2FF1A9F","rank":"normal"},{"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":"ba2b05c6fff72b44867a97fc7e2cd1d608f6d009","datavalue":{"value":{"amount":"+0.7421179413795471","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":"Q745680$11C609B4-40B1-414A-9629-394CDF4A679F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"878e63430dc6f4ce7c09f26cf08a842e0454cf56","datavalue":{"value":{"entity-type":"item","numeric-id":1875708,"id":"Q1875708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fddcad9024c5360e26a571c1de39cfe2502b324e","datavalue":{"value":{"amount":"+0.7351643443107605","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":"Q745680$1FA6D3AA-2452-43D7-956C-B6547182E7B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba61ece41be8e3afd21c81db7c4b8655125373b2","datavalue":{"value":{"entity-type":"item","numeric-id":3113735,"id":"Q3113735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"633da0dc3f424af1e550727ba96348cb71ffa78d","datavalue":{"value":{"amount":"+0.7313035726547241","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":"Q745680$2B7E296B-DECF-4F5C-A84A-39962ACF3E0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tropical lower bounds for extended formulations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tropical_lower_bounds_for_extended_formulations"}}}}}