{"entities":{"Q1361811":{"pageid":1372550,"ns":120,"title":"Item:Q1361811","lastrevid":68819481,"modified":"2026-04-13T02:16:54Z","type":"item","id":"Q1361811","labels":{"en":{"language":"en","value":"The \\(d\\)-step conjecture and Gaussian elimination"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1040620"}},"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":"Q1361811$3024814E-AF00-4CB2-BC6C-78EEB14241A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e5560331012a54147fdc33dd59fde3dee146116","datavalue":{"value":{"text":"The \\(d\\)-step conjecture and Gaussian elimination","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1361811$A8E3401C-71C8-46B7-825D-2D6D0931C358","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"851cc1206f826f97c454666bbfcc01f1bf8c0171","datavalue":{"value":"0883.52008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$7518E1A5-9925-4485-AC0D-FFEBB47F7A06","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"19b141cbe0055f24d160e6e7dc2e585868961bde","datavalue":{"value":"10.1007/PL00009308","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$437934EF-EB98-4611-B651-1773B8672D86","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2e6a0353a5a7b0d82ef9ca7c50f143590a03fea","datavalue":{"value":{"entity-type":"item","numeric-id":1349019,"id":"Q1349019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361811$C3D4546E-1F1E-4537-A783-E90CF7AA33BB","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":"Q1361811$9F174544-4D27-47CC-A0EC-030981F1D3DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bfdb3be97d698c9f52a1cf98ba0c4754ce65b7a6","datavalue":{"value":{"time":"+1998-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1361811$5EBFF068-3315-4007-AFA5-79506C9143CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e3545e823834220f7f6c002bb05c255ac23a01e3","datavalue":{"value":"Let \\(\\varDelta (d,n)\\) denote the maximum diameter of a graph of a \\(d\\)-polytope that has \\(n\\) facets. The \\(d\\)-step conjecture was formulated by Hirsch and asserts that \\(\\varDelta (d,2d)=d\\). It was proved by different authors in many special cases (see, for example, a survey by \\textit{V. Klee} and \\textit{P. Kleinschmidt} [Math. Oper. Res. 12, 718-755 (1987; Zbl 0632.52007)]). Moreover, counterexamples have been found for slightly stronger conjectures.    In the paper under review the \\(d\\)-step conjecture is proved equivalent to the following statement: For each ``general position'' \\((d-1)\\times (d-1)\\) real matrix \\(M\\), the set of \\((d!)^2\\) matrices \\(\\{Q_\\tau MQ_\\sigma : \\sigma , \\tau \\in \\text{Sym} (d)\\}\\), where \\(\\text{Sym} (d)\\) is the symmetric group on \\(d\\) letters, contains at least one \\(Q_\\tau MQ_\\sigma\\) having a positive Gaussian elimination factorization (that is the equation \\(Q_\\tau MQ_\\sigma =L^{-1}U\\) holds in which \\(L\\) and \\(U\\) are lower triangular and upper triangular matrices, respectively, that have positive nontriangular elements).    The number \\(\\# (M)\\) of pairs \\((\\sigma ,\\tau )\\in \\text{Sym} (d)\\times \\text{Sym} (d)\\) giving a positive \\(L^{-1}U\\) factorization is proved to be equal to the number of \\(d\\)-step paths between two vertices of an associated Dantzig figure. Numerical experiments presented all satisfy \\(\\# (M)\\geq 2^{d-1}\\) for \\(3\\leq d\\leq 15\\). The authors prove this inequality for \\(d=3\\) and suggest that the \\(d\\)-step conjecture may be true in all dimensions in the strong form \\(\\# (M)\\geq 2^{d-1}\\). Nevertheless in a note added in proof the authors announce that this strong \\(d\\)-step conjecture has been proved for \\(d=4\\) and disproved for \\(d\\geq 5\\) by F. Holt and V. Klee. The \\(d\\)-step conjecture remains open.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361811$B3C6335B-9C17-4179-AB3E-A53094C2F4C6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"78931806833c54190437f3675cf624ba3d256107","datavalue":{"value":"52B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$0513EBAA-474E-473C-ADB9-4E7AD2CBCCF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"798eea1f37baf19c7c9678fe1fc9dd8eadfa6f52","datavalue":{"value":"52B11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$EF46CBFD-19E4-470C-8253-F26A8735008C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9885aef811aa349f50c28b046ac04fbe99524c67","datavalue":{"value":"65F05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$8E80FB24-C697-4E52-AB50-7BBFEEA0DDC2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6c792abe69c2426b0f2ef02743bf95dc64e34a89","datavalue":{"value":"1040620","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$7A898A5C-588E-469A-A762-3846834F7AC3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"475c0ce07b1edcf27adda7f2ef814668fcd02f3a","datavalue":{"value":"structure of convex polytopes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361811$FB95F73F-3021-4AA8-8FFC-48D131B769E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"438ae43626caa1e9ffa59580f6e4781069cd9e12","datavalue":{"value":"Hirsch \\(d\\)-step conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361811$9C4ADDB3-FA83-4508-A914-C25978F18D48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39582725d773f66ea7b763bc55e831ca75ab427","datavalue":{"value":"Gaussian elimination","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361811$F7C68BC1-8385-48CE-833E-1A060A0E327E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b29d832d20b72d714b7ae54ca89ca5dbf8848b38","datavalue":{"value":"associated Dantzig figure","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361811$9A7BDFBA-F235-4343-B7B6-5A5B6A9FECBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa6a334de0f15d24fe0d677e5da8c8011ced4fbb","datavalue":{"value":"simplex exchange conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1361811$00AD071C-A9A7-4554-BFE3-D188A2041E07","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"701be6ec4b25c9dfd38ab9bbe2b2271154404d34","datavalue":{"value":{"entity-type":"item","numeric-id":205832,"id":"Q205832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1361811$678E96A5-3DBD-4C91-9CC9-7EE802157872","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":"Q1361811$235766D4-3798-484E-94BB-AC02ED6AFFA6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"bc1919421a013095c225cff0850dc100d56b1c50","datavalue":{"value":"Q123007407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$F910502B-FE23-43CC-95C9-07210E442773","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9460b872a4a050249266435703b56f361c27941c","datavalue":{"value":"https://doi.org/10.1007/pl00009308","type":"string"},"datatype":"url"},"type":"statement","id":"Q1361811$CDC131A8-A09B-48E6-9FBA-AE57D216C706","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ddc146beadb359f7783da38c7f1c4f4e7807e4c7","datavalue":{"value":"W1966479255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1361811$F8674A5D-390C-4334-95BD-C0F71DDE9DE2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ef679b28f60150157d59c50848ecf42b5d72967","datavalue":{"value":{"entity-type":"item","numeric-id":3769521,"id":"Q3769521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2cf6d0848c0b96384ce648337be38bd0da4fe9d","datavalue":{"value":{"amount":"+0.9004236","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$07308A55-356C-4054-8472-792D27877B2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90785dbba6b6220c3e64edeb91d08b38aaddb658","datavalue":{"value":{"entity-type":"item","numeric-id":4721511,"id":"Q4721511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1c6491a9d4abadd393d62375a2dd5d7a9b0d4ec","datavalue":{"value":{"amount":"+0.8717753","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$FAABD4A6-77E3-402E-A6FD-DD720273D7BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c0c359d8e269d92cb5ba519fb1d4421d94f22d3","datavalue":{"value":{"entity-type":"item","numeric-id":5578437,"id":"Q5578437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"25d96ed4efd9e93e67aa08c96d9299d937158f45","datavalue":{"value":{"amount":"+0.8659494","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$41F9D7EF-71EA-4D81-9FD0-34C3ED9933A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2e676afb20f8222e4847affe71f3e7d8a0b227e","datavalue":{"value":{"entity-type":"item","numeric-id":4226934,"id":"Q4226934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00d0819cdec09f3752261c9b69243c558f052960","datavalue":{"value":{"amount":"+0.863003","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$E87C3749-9135-4B45-B8A6-95A113E62156","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d4c2e17c22b2b11b149bed772ba3e26e5b5d84b","datavalue":{"value":{"entity-type":"item","numeric-id":3325833,"id":"Q3325833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24ee41e7db13e91bb2d9a69448173792a2b35705","datavalue":{"value":{"amount":"+0.8566615","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$7C917EA4-3DB8-47CD-925E-73EE69F26AA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a1f57c8c4cd4a01e391b1157caf8abdcfd08172","datavalue":{"value":{"entity-type":"item","numeric-id":4322522,"id":"Q4322522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cf0a5fb9c4febda4c3459e71467a4c922f7994f","datavalue":{"value":{"amount":"+0.8565103","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$13844733-859D-48A5-AF44-9E192619A259","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"527eb99bb847e44d18f3497769dcb2bafaa7e238","datavalue":{"value":{"entity-type":"item","numeric-id":5203559,"id":"Q5203559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd5d6851adc7b0b47b2b1ddce8c216d9318694b9","datavalue":{"value":{"amount":"+0.85564023","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$6696A51C-94EF-45EA-B9CA-5BAF57D0C7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e20d84ffe8e48456c41a2ae95b13df8ca4a346a","datavalue":{"value":{"entity-type":"item","numeric-id":4438100,"id":"Q4438100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b10d520007c0498811be51c9f822c70cbfc36db","datavalue":{"value":{"amount":"+0.85558105","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$AE3B47AA-E2AB-412A-AA81-15768A8A1FC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d82ea9e8a077a60dd96b17d80439abd72d1a33b","datavalue":{"value":{"entity-type":"item","numeric-id":5708148,"id":"Q5708148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd9ee22373cba935bcffb05e6ae70251fd75f698","datavalue":{"value":{"amount":"+0.855473","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$48175FDA-5E0A-4A95-B353-B7975D5BA4DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b50902ed69c4246683abb4e69f9e957ba42b1747","datavalue":{"value":{"entity-type":"item","numeric-id":5073965,"id":"Q5073965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"262d64426a0504ac6a397c08baa85109499864e1","datavalue":{"value":{"amount":"+0.8532733","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1361811$17F6AE6B-BA3C-492A-9998-E6FD4062FEAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The \\(d\\)-step conjecture and Gaussian elimination","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_%5C(d%5C)-step_conjecture_and_Gaussian_elimination"}}}}}