{"entities":{"Q1601467":{"pageid":1612207,"ns":120,"title":"Item:Q1601467","lastrevid":57417456,"modified":"2026-03-30T21:05:05Z","type":"item","id":"Q1601467","labels":{"en":{"language":"en","value":"On the \\(k\\)-systems of a simple polytope"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1760709"}},"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":"Q1601467$5692C795-271E-4D0E-A0AB-FA650DDC9210","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7b07b450cd08f48b2a9a5e00355038a20343de27","datavalue":{"value":{"text":"On the \\(k\\)-systems of a simple polytope","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1601467$0BEF36E1-757D-48A3-B2F8-D856ECD96E88","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3a572734bb4bd70660a145705d9aa136641faf56","datavalue":{"value":"1009.52021","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1601467$1E1FE5F4-A493-4DC4-8826-36D39C708F88","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"335d24a09bd1c2c8383bbe30b396d1ff40015c70","datavalue":{"value":"10.1007/BF02773157","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1601467$E920402D-44B1-40BA-87EC-ABED3C1AC596","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a6986bb527e83e2bf53668515812c8836a263dc","datavalue":{"value":{"entity-type":"item","numeric-id":161115,"id":"Q161115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$3869A4EE-4B7D-4979-B5D2-268FAB7DA2BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"99fc10592751b4edb3eda1b3a996a05ee49279ec","datavalue":{"value":{"entity-type":"item","numeric-id":193593,"id":"Q193593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$98323A31-167C-46AB-84CE-CDBD09987FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"973c8256939d159f34e22108aa6cffadb792a03b","datavalue":{"value":{"entity-type":"item","numeric-id":1601466,"id":"Q1601466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$B77839CC-F615-4C50-BE91-177537285A32","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$91287821-DF5E-4689-88B6-066C795D4724","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"28382a85cc516e2eceee710edeafb5a093421018","datavalue":{"value":{"time":"+2003-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1601467$ED17054C-2003-4154-B433-4E35680324B9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0e52993969f74e14202fb2c81d99da4f1504b9e","datavalue":{"value":"https://arxiv.org/abs/math/0012204","type":"string"},"datatype":"url"},"type":"statement","id":"Q1601467$F3201BDE-9640-42B3-AF67-A07D67025BEF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9d9d96c50fe337545733f7fde6ccd74c29fe92ea","datavalue":{"value":"It is known that the combinatorial type of a simple polytope is determined by the isomorphism type of its edge graph \\(G\\) [\\textit{R. Blind} and \\textit{P. Mani-Levitska}, Aequationes Math. 34, 287-297 (1987; Zbl 0634.52005)]. Algorithms exist which perform this determination, however, the best known algorithms are exponential in the size of \\(G\\). The reader is referred to the work of \\textit{G. Kalai} [J. Comb. Theory, Ser. A 49, 381-383 (1988; Zbl 0673.05087)].   The article under review examines subproblems relating specifically to Kalai's algorithm, with a view to finding polynomial-time solutions to them. The work is done in terms of \\(k\\)-systems. A \\(k\\)-system of \\(P\\) is a set of sets of vertices of \\(P\\) satisfying certain properties given in the article. An example is the set of vertex sets of the \\(k\\)-faces of \\(P\\), but other examples exist.   The article should be useful to anyone concerned to find efficient algorithms to characterize simple polytopes from their edge graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1601467$415EA4AD-6CA5-4197-9658-BCBD619BAA6A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1601467$8524541B-89BB-4784-894D-3BF9CAC612AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1601467$0D8ADA9C-BB6A-41F8-A158-49E96FE94378","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a844f7d54eca833552c38569473fdf7b06b5c38c","datavalue":{"value":"1760709","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1601467$23A38564-1ACA-4D22-B982-041F53D99441","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d587e2c9e536d32a8cd4af0998dc4218d8cab36","datavalue":{"value":"simple polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1601467$781A2CB4-E5F0-42FA-965F-E0A4086792CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8b1936e13b5ec3462e1c5d85d91d643107e5ac4","datavalue":{"value":"edge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1601467$4A50EAE5-10D8-4BF5-B1C7-79F06DB0B129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b013cd229123bab075c6ef1680648158ad7223e2","datavalue":{"value":"abstract objective function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1601467$AAD5E6F5-6623-4976-B4C5-D33FD7B16E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"93077cc6db36e07d535db7c75a2f03eb0743cd04","datavalue":{"value":"algorithmic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1601467$E77E665C-5E45-455A-BB43-FBC5E6D2497A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"376fa15aafb227798cafee22da9fffa941ad0904","datavalue":{"value":"Q117245117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1601467$B23D1FD3-E4C2-45CC-902E-A7D06B765933","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c2263347f4dc691a1bce54afbb8c496450d9f186","datavalue":{"value":{"entity-type":"item","numeric-id":596649,"id":"Q596649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$88DBE64A-A130-48D8-B80D-3B2031872513","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":"Q1601467$2C4ABAD9-A9E1-471D-B1E5-678301A2FB96","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c72384c3a66e4494a5c7cefa5603749eb8211c80","datavalue":{"value":{"entity-type":"item","numeric-id":4518986,"id":"Q4518986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$8D2CDCE4-0ADA-4F20-8349-BA81F54625BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5920b164a562492807aefc925d0692341a7d0d5b","datavalue":{"value":{"entity-type":"item","numeric-id":1096888,"id":"Q1096888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$0383948D-7627-418C-9033-3F76F1F07E90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$5207F3EA-0250-4BAF-8EBB-CD8217A28E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c39738cea79e11456d6583aec1786d79af209b23","datavalue":{"value":{"entity-type":"item","numeric-id":5341586,"id":"Q5341586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$CAF62A39-8A57-4A9F-BD4E-94617B1C7364","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29d5a9cf2fb8af94b5f34c994bd2c19561534d70","datavalue":{"value":{"entity-type":"item","numeric-id":1611070,"id":"Q1611070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$0D239C4B-5FEA-4E75-BF09-0B2455859DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e2849a6120bed643fb8994467168125e6f30ef9","datavalue":{"value":{"entity-type":"item","numeric-id":3820646,"id":"Q3820646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$E815A0EC-30B5-4A2F-B67D-0A3786B7C253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226a340089088b39adcc1021928877b4b1249b42","datavalue":{"value":{"entity-type":"item","numeric-id":1120602,"id":"Q1120602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$CEF86EEC-31CF-4319-8B9C-99F53C7EC91F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec5c47757e33444de8c499d42f7a7ae1cd1b586f","datavalue":{"value":{"entity-type":"item","numeric-id":2564767,"id":"Q2564767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1601467$1465B1F0-A707-4BBB-BBF6-4CD8BC3662AA","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":"Q1601467$1F072021-0182-4B29-8837-9657DC0F67BB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9453df3606843d6d2ea942f2c25980d330f5483e","datavalue":{"value":{"entity-type":"item","numeric-id":1017924,"id":"Q1017924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c6b094b4fbc08321f0de24c3888d34c8c6bebab","datavalue":{"value":{"amount":"+0.777229368686676","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":"Q1601467$0268EF37-7768-467E-850C-A75EE33C9305","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65de17d5fc2e8e6c77fe7bd185622b12f871d7ea","datavalue":{"value":{"entity-type":"item","numeric-id":4414641,"id":"Q4414641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd0f51aae9f383f89442b0e6667933a34bd5ffcd","datavalue":{"value":{"amount":"+0.770660400390625","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":"Q1601467$D0B0FD90-083E-46DC-8C4D-AC48983E881F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d44d6a6415a812f33b77bcfc4e8ea58a57ffe1","datavalue":{"value":{"entity-type":"item","numeric-id":1120602,"id":"Q1120602"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd0f51aae9f383f89442b0e6667933a34bd5ffcd","datavalue":{"value":{"amount":"+0.770660400390625","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":"Q1601467$CAC617EC-51CB-44DC-AFE2-DA3F66AA9E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b949b5816890097484f4ddda157c2415c1567f8a","datavalue":{"value":{"entity-type":"item","numeric-id":4518986,"id":"Q4518986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b5a0e95600bcf9d9243f1c470207f74f22cfab4","datavalue":{"value":{"amount":"+0.7659054398536682","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":"Q1601467$A6711960-86FB-418A-B118-766896BEED02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2174f9a70ea2c6c840c802246a697b0002be6873","datavalue":{"value":{"entity-type":"item","numeric-id":1334609,"id":"Q1334609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b5a0e95600bcf9d9243f1c470207f74f22cfab4","datavalue":{"value":{"amount":"+0.7659054398536682","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":"Q1601467$D0D338B2-207D-4D4B-9157-7C62E3AC2B70","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1601467","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1601467"}}}}}