{"entities":{"Q2500985":{"pageid":2511728,"ns":120,"title":"Item:Q2500985","lastrevid":73500051,"modified":"2026-04-14T16:14:17Z","type":"item","id":"Q2500985","labels":{"en":{"language":"en","value":"Permutation reconstruction from minors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5050784"}},"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":"Q2500985$C1D8E6A0-1499-4B5A-B005-472367AEA53F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"887feb47ee195145815a3537cca744a9b63d5c75","datavalue":{"value":{"text":"Permutation reconstruction from minors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2500985$EF82C376-0572-4D64-8888-DADD52F2BE96","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"414a7ade9f5edce6c2b4d655a7175ea17187ce61","datavalue":{"value":"1096.05003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500985$CAFBB681-A07F-4FE8-80F3-C9C8B036A40D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60257d349b95b60ba6d4b231a228e3d2c95b6a90","datavalue":{"value":{"entity-type":"item","numeric-id":776018,"id":"Q776018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2500985$6AFEE1E4-76D9-4E7F-8908-117F8DF6E783","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2500985$65690761-DF3D-406C-8498-0327AF0E3E61","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ce041d4734364c3a206df997bf620f42fb038366","datavalue":{"value":{"time":"+2006-08-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2500985$DC276600-D927-4112-9356-9A04F7358E19","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a6e7a34e8ad08e0182c751bceeb701b1283ea8b6","datavalue":{"value":"https://eudml.org/doc/126401","type":"string"},"datatype":"url"},"type":"statement","id":"Q2500985$FB79525B-5288-4C0A-9710-B5B61415BD11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa5bb1105c6b5d363a402ff0e0b8796ec81d62f6","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r66.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2500985$D74489CA-E551-4BD9-835B-1D1842F3A48F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"228a81f57837b1ec8b001ef26d43fbc268e1010b","datavalue":{"value":"Summary: We consider the problem of permutation reconstruction, which is a variant of graph reconstruction. Given a permutation \\(p\\) of length \\(n\\), we delete \\(k\\) of its entries in each possible way to obtain \\({n \\choose k}\\) subsequences. We renumber the sequences from \\(1\\) to \\(n-k\\) preserving the relative size of the elements to form \\((n-k)\\)-minors. These minors form a multiset \\(M_k(p)\\) with an underlying set \\(M_k'(p)\\). We study the question of when we can reconstruct \\(p\\) from its multiset or its set of minors. We prove there exists an \\(N_k\\) for every \\(k\\) such that any permutation with length at least \\(N_k\\) is reconstructible from its multiset of \\((n-k)\\)-minors. We find the bounds \\(N_k > k+\\log_2 k\\) and \\(N_k < {k^2\\over4} + 2k + 4\\). For the number \\(N_k'\\), giving the minimal length for permutations to be reconstructible from their sets of \\((n-k)\\)-minors, we have the bound \\(N_k' > 2k\\). We work towards analogous bounds in the case when we restrict ourselves to layered permutations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2500985$A9F4640D-AE63-4EFB-B01E-D24EEBCB134E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500985$50D7953C-0170-4B06-AFC2-97D5731540F6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e7cd765b9847bd0471a425a486df19ffb92bd291","datavalue":{"value":"5050784","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500985$FD863383-4F2E-48F7-AA34-950D21EBC4AB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f7caf114084cf0b6edafd75016f6ee48cf9337b5","datavalue":{"value":"subsequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q2500985$D1658B79-0A19-4854-8612-154DF21AC618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7bb0e239ebe581c420c1d025b7801ad08bbe4789","datavalue":{"value":"multiset","type":"string"},"datatype":"string"},"type":"statement","id":"Q2500985$9B0CE5EE-9B20-45D8-9985-53E22CFAD47D","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":"Q2500985$A69E9150-2199-42C7-8591-A64A2033B165","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f04185851890e311edbfff4f9c79ed0642eff6ec","datavalue":{"value":"bafkreihm5uyeu252keye342vjmd3u3h7gy4wqtoz3w5muzialglnhj5voe","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2500985$F3BF4CE0-7880-442D-8ED3-28F4BA195652","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a4f53676695b144951076747b4a2ddb1e6e142e7","datavalue":{"value":{"entity-type":"item","numeric-id":888635,"id":"Q888635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f78c84af7894ed153a2fc9159e68dc27f475fa06","datavalue":{"value":{"amount":"+0.9597058","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":"Q2500985$8E10BC5C-6090-49B3-8403-C5A458C2B038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5da8d86c8c56c16d37a978cba24abeed8030172b","datavalue":{"value":{"entity-type":"item","numeric-id":1010923,"id":"Q1010923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8dc98dc9414a2f925ba0f3972d701b8eaa8ffb28","datavalue":{"value":{"amount":"+0.958388","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":"Q2500985$F3A1CAF2-F811-4809-BCDE-68221E645E62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b28c36ce21dea847635da325c3d0dc0d6b8053bc","datavalue":{"value":{"entity-type":"item","numeric-id":290110,"id":"Q290110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91d699cfc6e594457292c55281bb00865fbacdb5","datavalue":{"value":{"amount":"+0.9035612","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":"Q2500985$AFDE3428-C5F3-4D79-AC20-338E33AD4E25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30772b45dc5e6dd8dba37a543bb752062ffc90b3","datavalue":{"value":{"entity-type":"item","numeric-id":2501000,"id":"Q2501000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cfd25f7332edf8900a34010010af7773e6079b2","datavalue":{"value":{"amount":"+0.9022512","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":"Q2500985$241B5B37-FBB4-47C0-B16A-24D355B799B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3017affc27df3ba56631036f3aa745ccbe2c7582","datavalue":{"value":{"entity-type":"item","numeric-id":463039,"id":"Q463039"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7023fef346667593150c1d4d9206b86f6852d4d","datavalue":{"value":{"amount":"+0.89370346","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":"Q2500985$CDE09DC1-739A-4577-81CA-D2A0C279F448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f63405b3f2201de0bba56c44e905b1c45cd8c895","datavalue":{"value":{"entity-type":"item","numeric-id":2969649,"id":"Q2969649"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d9a4a5f03e94a1900b5364c616808a62610a6daf","datavalue":{"value":{"amount":"+0.87740374","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":"Q2500985$4F0B0503-95D5-4C84-8AC9-A5FC967CDEB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77e4d55e485f50717930dd46b6de6ddc6f3f8a4e","datavalue":{"value":{"entity-type":"item","numeric-id":4519041,"id":"Q4519041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ccd04d90f134f4407829999785d2d92daf8196bf","datavalue":{"value":{"amount":"+0.87737864","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":"Q2500985$DBC37F67-C0B6-4861-874F-6253AC0C41F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02e96fccf6ed5e9eaeb4ce0ca90f071a9112bb63","datavalue":{"value":{"entity-type":"item","numeric-id":5488385,"id":"Q5488385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f7832c6c859c78639ae4f5ca8276b367d3ff7f","datavalue":{"value":{"amount":"+0.8723282","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":"Q2500985$C5196959-C8FB-4B64-8B86-E9B3AD036F2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"487793ca9c279370b45a0742a37498816d49ff5c","datavalue":{"value":{"entity-type":"item","numeric-id":2915587,"id":"Q2915587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"835874254c74db9c13639dcdd5d81014f7599e05","datavalue":{"value":{"amount":"+0.87229866","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":"Q2500985$A7C1394B-C962-4703-B965-BBBAA6C982F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24a06782ab74392e2b54df6e9b36d2045f73daae","datavalue":{"value":{"entity-type":"item","numeric-id":630520,"id":"Q630520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"069373ed91faf835a1305986355171f748a08a90","datavalue":{"value":{"amount":"+0.8675654","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":"Q2500985$96C7200F-44DF-43EF-B28C-9DA39A704BBD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Permutation reconstruction from minors","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Permutation_reconstruction_from_minors"}}}}}