{"entities":{"Q1197618":{"pageid":1208367,"ns":120,"title":"Item:Q1197618","lastrevid":69866991,"modified":"2026-04-13T10:52:21Z","type":"item","id":"Q1197618","labels":{"en":{"language":"en","value":"On the diameter of permutation groups"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 91732"}},"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":"Q1197618$81632776-5BE6-49D6-B2C9-D665DE4FF6E3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"05713e323cc9caab1f13d93faa16f9c75f30d9e3","datavalue":{"value":{"text":"On the diameter of permutation groups","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1197618$E9B85773-6B84-4C8C-9D56-B9DDEC412431","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bc01e116ac25d120b830f8cd1200fa3eda068195","datavalue":{"value":"0783.20001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$71148A0F-93E6-43E0-8934-61D37E51DFF3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e6531c45f22383b281a9f28590708a23b86f1703","datavalue":{"value":"10.1016/S0195-6698(05)80029-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$B67725D3-8817-4062-BE90-1AFB6C8E2044","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$0DD5E18C-70AE-4D7A-8AA2-CC5A4DFD519D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1197618$3FD30692-4E90-4AC5-896B-0ADC53CC92AC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88d46f0e89e98f26cb128cc2b0fde58f704e8b6f","datavalue":{"value":"The authors give an asymptotic universal upper bound for the diameter of all Cayley graphs of all permutation groups of degree \\(n\\), namely, they show that for any set of permutations \\(S\\) in \\(S_ n\\), every permutation in the subgroup generated by \\(S\\) can be expressed as a product of length at most \\(\\exp((n\\cdot\\ln n)^{1/2}(1+o(1)))\\) of factors belonging to \\(S\\cup S^{-1}\\). This estimate is the best possible, since by an old result of Landau the same asymptotics holds for the largest order of an element in \\(S_ n\\). In an earlier paper [J. Comb. Theory, Ser. A 49, 175-179 (1988; Zbl 0649.20002)] the authors proved the same upper bound for the diameter of all Cayley graphs of \\(S_ n\\) and \\(A_ n\\). However, they conjecture that in fact the diameter of any Cayley graph of \\(A_ n\\) is less than \\(n^ C\\) for some absolute constant \\(C\\). This would imply a considerable improvement for transitive groups, since another result of the present paper asserts that the diameter of Cayley graphs of transitive groups is less than \\(\\exp(C\\cdot\\ln^ 3 n)\\cdot \\text{diam}(A_ m)\\), where \\(C\\) is an absolute constant and \\(m\\) is the degree of the greatest alternating composition factor of the group in question.   For the proof the authors develop a quite complex ``asymptotic structure theorem'' for permutation groups. In order to prove the estimates, some consequences of the classification of finite simple groups are invoked.   Remark: The statement of Proposition 3.2 holds only for nonabelian composition factors \\(G_{i-1}/G_ i\\). However, the proofs using this proposition carry through with a trivial modification; all other statements remain correct as stated.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$68CAB3ED-A640-4DC2-BD06-BDFF3151AADF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"40a17c7590d207693a91f511a74f778bb78de167","datavalue":{"value":"20B05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$CA8E3587-EAEA-405F-AF32-FFC7D8F03128","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"913d5faab8506844afe18117d24b66ca7e35db18","datavalue":{"value":"20B20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$26FA4783-386A-4151-A99B-33152FB614FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$301CD4A8-0CFC-4157-8E82-C51236CD7F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"99162f665c9ec138d28e4bea8a477540421995b7","datavalue":{"value":"20B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$E2D28A02-56A7-4FE3-9A4F-1E19835CEE11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$07352807-F1ED-4D4F-8429-64B8716AD184","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9784f76157b94300d134a752eb81bfee3a9e9689","datavalue":{"value":"91732","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1197618$3C32E46D-754E-46B0-9C81-D454EAFE3598","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"817f91d754a6618dd027e0d851a1fc8b7cbc7134","datavalue":{"value":"upper bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$A8D5DCFB-8427-427C-8BAF-E16B9CDC6473","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$123B7366-756C-4D55-9F48-7FCE16EB632E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64e1ee688b6f898d32c9c2776a1d825855a56d60","datavalue":{"value":"Cayley graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$B5A4F21C-83B2-409A-9738-8AD80767D24F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8e3f7e0d18e9c7e5b9f5b19131aa549a1a707c3","datavalue":{"value":"permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$4532B297-D81D-44C4-A2EF-B30A98264B61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5361b9a8090aa7d8fe424d2931b70e1e1421b462","datavalue":{"value":"transitive groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$7028D196-C165-4F4A-A6A2-9202EF830257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e203093c30d6945fc9b0330744ff748530fff607","datavalue":{"value":"composition factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1197618$EDFBA1B2-A5C2-49E2-80F9-1CCD9FEE144D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb810284579fca70d13987c395247bb8f287f16c","datavalue":{"value":{"entity-type":"item","numeric-id":196035,"id":"Q196035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$7FD3F687-D4D5-44ED-836D-5C65BF6EEF3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"306d9099ef8452dabdd265171a602e1aa51bd912","datavalue":{"value":{"entity-type":"item","numeric-id":162994,"id":"Q162994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$3C8F67A4-BA9C-49B4-9DC8-AC6322118C91","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e09d1658cf28d37a07fc64d172ca070f100781f3","datavalue":{"value":{"entity-type":"item","numeric-id":1301643,"id":"Q1301643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$8141F2F9-94A2-4B52-833D-233D4CF68619","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":"Q1197618$6D967604-47AA-456B-8BF0-AF50ECFD708D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"763dbd33af546db139ad22dd7c58cef949a6387b","datavalue":{"value":{"entity-type":"item","numeric-id":792460,"id":"Q792460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$64B1DB65-8912-42AB-A9BD-3A5F5D501EE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c280c94a6139ae504c2ae04c131e74497d2a6d3","datavalue":{"value":{"entity-type":"item","numeric-id":3741778,"id":"Q3741778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$2475969A-955A-4C9A-8A8B-5E6ACB05645D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a60bed8589b999c8e8c14d91d248b5eb8716e13c","datavalue":{"value":{"entity-type":"item","numeric-id":4871775,"id":"Q4871775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$AB158504-E527-49F4-A21F-4A28276EF8F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd01491363e13342f852f5e56870cb013656da81","datavalue":{"value":{"entity-type":"item","numeric-id":1164029,"id":"Q1164029"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$0EB33BD8-A25D-4BAD-A991-2B6E1196410F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a831c17449d5c55666690eb4f4e956acef3fff44","datavalue":{"value":{"entity-type":"item","numeric-id":1821193,"id":"Q1821193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$13C65C2D-AC29-430A-90A8-4DEA90A42C75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"886316b529031905628828a3111a4a5a8f80914a","datavalue":{"value":{"entity-type":"item","numeric-id":1105690,"id":"Q1105690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$9D091F7A-78BE-4E4B-BC96-132F937F2B7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1a1b9b6535e6078ebd7b9be61477d37c230d5ab","datavalue":{"value":{"entity-type":"item","numeric-id":1168415,"id":"Q1168415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$BA41C555-9092-417D-AD92-AC330AB73998","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2885a792bc5f912a0930ebe70d1078c559576e5f","datavalue":{"value":{"entity-type":"item","numeric-id":914696,"id":"Q914696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$08BDDBE7-EF32-4ECE-8ED3-FAED3D7633A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89114344afb55319f83e26b6ed19450dcb689a11","datavalue":{"value":{"entity-type":"item","numeric-id":3913570,"id":"Q3913570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$5C1A9AF7-816A-4A81-AFE9-9E0D4736B0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6158e34ce49168a0963dd4cfac15e6bc492600d","datavalue":{"value":{"entity-type":"item","numeric-id":5662096,"id":"Q5662096"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$999EA333-2A85-4853-BD7E-4282F70E2AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1298636b6db1043655376c8a78d1f5a8bdd9ebcc","datavalue":{"value":{"entity-type":"item","numeric-id":1090414,"id":"Q1090414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$5DEA4C22-7A98-4A5E-B9B5-287460F33D2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6f115af079400928ee78e55b9f09064cf5661cb","datavalue":{"value":{"entity-type":"item","numeric-id":2555922,"id":"Q2555922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$3853C10F-1698-4FA2-8C95-F7BB96911181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f346f6935eab8f7bfd8c5b35d3ff010b785bc3a1","datavalue":{"value":{"entity-type":"item","numeric-id":4860774,"id":"Q4860774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$A23F1ACB-F93B-4104-8604-12E5765629FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5989e7b642a281e076cb0a5451b4d9c25f50f39c","datavalue":{"value":{"entity-type":"item","numeric-id":3253828,"id":"Q3253828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$AD4B4265-0BC2-47FD-B8E5-B61F23A32BBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09e633db0f557b9206d31cddc4d5a1e201d27f97","datavalue":{"value":{"entity-type":"item","numeric-id":1843465,"id":"Q1843465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$D30806B2-781F-4618-9EDA-4839D17A6F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"10c65d75ceee756660145536a51d3f0a8397e623","datavalue":{"value":{"entity-type":"item","numeric-id":3691907,"id":"Q3691907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$EAFCB882-17CB-4842-9FAB-595304C9A3DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2de3ec857f6169c81f2908b5b9720efbe3cb44f0","datavalue":{"value":{"entity-type":"item","numeric-id":1168744,"id":"Q1168744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$41D65590-E0A0-4DE3-93EF-39EFDB0CC9F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9674148e539c769c7cdfd14a34ccd8e74dc136e","datavalue":{"value":{"entity-type":"item","numeric-id":1060843,"id":"Q1060843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$EBA99994-5230-48FF-97B5-E22EF573E3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58ff25799ed82acdaa8e21d406a36c82d65e6cb5","datavalue":{"value":{"entity-type":"item","numeric-id":3907748,"id":"Q3907748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$BE528897-5D97-4F88-819E-3F6D70744448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed5cab814cd603492c1673559e52eda9669c1aa7","datavalue":{"value":{"entity-type":"item","numeric-id":5512231,"id":"Q5512231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1197618$863BD51A-6A1E-4537-B4F8-A85E4E476E84","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df7134707270a586cf95506a0a3970ac8141359f","datavalue":{"value":{"entity-type":"item","numeric-id":2445317,"id":"Q2445317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecd3fa32b1f1e1abbbe83c280dc7995956eeb71e","datavalue":{"value":{"amount":"+0.9310221672058104","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":"Q1197618$7EB03C85-ACB8-4FEE-BC3E-09DDE16BF1DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa102f55c9b8881acb35d5f6dd7ee829682151c8","datavalue":{"value":{"entity-type":"item","numeric-id":1105690,"id":"Q1105690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98538836ab24b480a93889e7d01316f3babdfd81","datavalue":{"value":{"amount":"+0.8922087550163269","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":"Q1197618$804BE41A-E2C8-4C25-BFE2-831FF1790F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad4a8ac725278ead3db532c2c843636b47d55668","datavalue":{"value":{"entity-type":"item","numeric-id":4291197,"id":"Q4291197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"172433023a6acd7870ed7e9c8e16463316dc61f4","datavalue":{"value":{"amount":"+0.8646585941314697","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":"Q1197618$60AF7409-502A-467C-A40A-B031ACC9ABF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d3b098947491358bebd36e41a601b9693ade24fd","datavalue":{"value":{"entity-type":"item","numeric-id":914696,"id":"Q914696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e315f939663eb33b3ecae44f98e5e9b506dea88e","datavalue":{"value":{"amount":"+0.8617587685585022","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":"Q1197618$BE7ED962-77C7-4C84-A923-50732C6C717A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afc92faf3937b9119ef7352e32d9a648528869ee","datavalue":{"value":{"entity-type":"item","numeric-id":402925,"id":"Q402925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd8a0e7f2a1e6a052735fb54fd5509eb525bae2b","datavalue":{"value":{"amount":"+0.8504137992858887","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":"Q1197618$C805DD94-65E5-4292-A6FC-422DAC08E0EA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the diameter of permutation groups","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_diameter_of_permutation_groups"}}}}}