{"entities":{"Q1010914":{"pageid":1012762,"ns":120,"title":"Item:Q1010914","lastrevid":66004575,"modified":"2026-04-12T06:53:06Z","type":"item","id":"Q1010914","labels":{"en":{"language":"en","value":"On the locality of the Pr\u00fcfer code"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5541075"}},"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":"Q1010914$ED102962-6AB2-4E54-A11B-8F1AC927514A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1fc62001586743f81ca8e556914938ad2f4db3e1","datavalue":{"value":{"text":"On the locality of the Pr\u00fcfer code","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010914$9A42CFFE-00B3-4BB3-973E-2ED352188640","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f88998b0a3898c52dd7cdb68915c982684b02714","datavalue":{"value":"1178.05096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010914$ACB7911C-417B-447B-A8BF-BC87E3E0DDC2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a609e068ad37e32df37f0921f359b8b2412d6ed4","datavalue":{"value":{"entity-type":"item","numeric-id":1010913,"id":"Q1010913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010914$BE0C7270-2C0B-4AF7-9AD6-05F2BB65421C","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":"Q1010914$862700CC-A744-4315-B601-555DF1D142C3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010914$918A9B24-4C2F-49EA-A3B4-BD102D0F411C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b2b7e7ae8143b1aca4c8878249d20384ac632276","datavalue":{"value":"https://arxiv.org/abs/0802.3514","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010914$E0973C6E-12CA-4219-8C77-9B51C3193186","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7d2f79a179039fbe7ae13b3db716c8cdd1bb2e5a","datavalue":{"value":"https://eudml.org/doc/117294","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010914$A59560D6-E420-4AD6-A7F7-E67C16E4411F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"84e9a830c8abeec845a08e0c613bb4d5510ded18","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_16/Abstracts/v16i1r10.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010914$542D30FC-C398-4C47-A2F9-1C3150F725B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8b498715e930193c71413a9d97d0ac402c732de8","datavalue":{"value":"Summary: The Pr\u00fcfer code is a bijection between trees on the vertex set \\([n]\\) and strings on the set \\([n]\\) of length \\(n-2\\) (Pr\u00fcfer strings of order \\(n\\)). In this paper we examine the `locality' properties of the Pr\u00fcfer code, i.e. the effect of changing an element of the Pr\u00fcfer string on the structure of the corresponding tree.    Our measure for the distance between two trees \\(T\\) and \\(T^*\\) is \\(\\Delta(T,T^*)=n-1-| E(T)\\cap E(T^*)|\\). We randomly mutate the \\(\\mu\\)th element of the Pr\u00fcfer string of the tree \\(T\\), changing it to the tree \\(T^*\\), and we asymptotically estimate the probability that this results in a change of \\(\\ell\\) edges, i.e. \\(P(\\Delta=\\ell\\, | \\, \\mu)\\). We find that \\(P(\\Delta=\\ell\\, | \\, \\mu)\\) is on the order of \\( n^{-1/3+o(1)}\\) for any integer \\(\\ell>1,\\) and that \\(P(\\Delta=1\\, | \\, \\mu) = (1-\\mu/n)^2+o(1)\\). This result implies that the probability of a `perfect' mutation in the Pr\u00fcfer code (one for which \\(\\Delta(T,T^*)=1\\)) is \\(1/3.\\)","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010914$B94221C9-9319-4055-B387-3E1F5E29122C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010914$D25E3BDF-4D0C-430F-8B9C-83CA5076C769","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6193e54a528e593ba9991064272457ec7c6d23af","datavalue":{"value":"5541075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010914$F81E1E43-2E15-4153-AAA3-2122F5202F3A","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":"Q1010914$2BDAE70B-B20A-432C-A356-0F76F4E6E3A2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"18a11dae53cc5cf8a3e3a93aeeb825ada306a39a","datavalue":{"value":"bafkreigaxnvagwmdt6xflmrucmmx2qoao2ocz6xeaozfgmpn3myqdw6u6a","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010914$A4449D0E-A5A3-45D9-A1E3-B9B014EE43E7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"886f963523bf27c17ea7167de96f3c1ef2495417","datavalue":{"value":{"entity-type":"item","numeric-id":1010611,"id":"Q1010611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a96c56b3b8fe53e460f4c5839fa99d1aec9d313","datavalue":{"value":{"amount":"+0.9219200015068054","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":"Q1010914$BA205713-9250-4D44-92E8-E0DD71E56790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cfbc6690f9e11d8466daf5f039ac3d569711220","datavalue":{"value":{"entity-type":"item","numeric-id":4329049,"id":"Q4329049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8181779236fd26b6efb0ba216b70869d65c9550a","datavalue":{"value":{"amount":"+0.7798884510993958","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":"Q1010914$7746B3E5-D32D-4A5D-9BAA-6DA150D0EBD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9285ed340ca0956fb45851398c29daa13047eec1","datavalue":{"value":{"entity-type":"item","numeric-id":5716943,"id":"Q5716943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d373864a042bdf72b53e8c76203c07861f20377","datavalue":{"value":{"amount":"+0.7559301257133484","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":"Q1010914$EDE8DE0D-F4BE-4EF7-B21A-14D1B50F0AB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2b4e3254f32ebea6b1d62dddcdad2da50023d22","datavalue":{"value":{"entity-type":"item","numeric-id":1969439,"id":"Q1969439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72293240dcd29eb91c03928806238fa20e21942f","datavalue":{"value":{"amount":"+0.7501529455184937","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":"Q1010914$F0E19FCC-FC36-4BDB-8DE5-D64198E03CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1be0973900a5bf03e1ef401612e2f91f993f89a","datavalue":{"value":{"entity-type":"item","numeric-id":1566573,"id":"Q1566573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"454229085a631cb8aa29a544c8e1d78c68be17ac","datavalue":{"value":{"amount":"+0.7495960593223572","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":"Q1010914$16FF2BCA-BFCD-4225-A5B5-CC32F882B63E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the locality of the Pr\u00fcfer code","badges":[]}}}}}