{"entities":{"Q1378433":{"pageid":1389173,"ns":120,"title":"Item:Q1378433","lastrevid":46953960,"modified":"2025-12-25T22:25:07Z","type":"item","id":"Q1378433","labels":{"en":{"language":"en","value":"Bases for primitive permutation groups and a conjecture of Babai"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1117773"}},"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":"Q1378433$534C5187-E377-4D28-B01C-10D20B9AFE37","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c9ad0366a47d1766f99e83990a3f4a203bd5c08b","datavalue":{"value":{"text":"Bases for primitive permutation groups and a conjecture of Babai","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1378433$C72920EA-B521-4A54-8910-C8B599A2DE9C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c69cdc80c44cc3cbe4c7febacf4cada9f52c1913","datavalue":{"value":"0897.20005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$924B7CFD-92A1-45E5-9D0F-27BC95733EBD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d0fb32536a169e14855444bb4f9c351cd7b326a","datavalue":{"value":{"entity-type":"item","numeric-id":343634,"id":"Q343634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$A8805461-864B-4D15-B83C-F940E7E1557B","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":"Q1378433$DC59E114-1EA2-41A0-BC37-FA8A2F0D329C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da0639bf661f9c8dfb2a37e7b3c2263b9677bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":220675,"id":"Q220675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$216655FF-758D-47DF-A9E5-781A6E08D5D9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"93541bb195a0809b1f249396bcebe99d047e6b6c","datavalue":{"value":{"entity-type":"item","numeric-id":161561,"id":"Q161561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$AB10FD7E-7E94-4A11-BB90-CFED3873A5B8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3db2eb2e003c0308e77b1da3e621f97dd9657c54","datavalue":{"value":{"time":"+1998-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1378433$1A7AEAF3-D9A8-4EB1-9945-3AF83D7CB5DD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7b04088e5fe9ececaf9743df1584c133152c1230","datavalue":{"value":"https://semanticscholar.org/paper/15dbe045dc4d384d9afe827b266d5c6e9dc478e6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1378433$94FCAB80-498A-4A44-B57F-C7894A43590C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c4d0006d79507770daa2122f64ea5b15cf7ca6e","datavalue":{"value":"A base for a permutation group \\(G\\leq S_n\\) of degree \\(n\\) is by definition a sequence \\(B=(\\beta_1,\\ldots,\\beta_M)\\) of points in \\(\\Omega\\) such that in \\(G\\) only the identity fixes each point of \\(B\\); \\(M\\) is called the size of the base \\(B\\). Denote by \\(\\Gamma_d\\) the family of all finite groups such that \\(G\\) has no alternating composition factor of degree \\(>d\\) and no classical composition factor of rank \\(>d\\).   It is proved in Theorem 1.2 that there exists a function \\(g\\colon d\\mapsto g(d)\\) of positive integers such that if \\(G\\leq S_n\\) is primitive and \\(G\\in\\Gamma_d\\) then \\(G\\) has a base of size at most \\(g(d)\\). Moreover, \\(g\\) can be chosen as a quadratic function. It is shown that the greedy algorithm can be used to produce such bases. The theorem confirms a conjecture by Babai.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378433$B47AF4DC-7DF7-4B3F-83D1-C2DCC5D9D3D6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3367018dbe2ad5da0826b32cb1ef14710133d281","datavalue":{"value":"20B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$5346CAD6-99DD-4FD1-88B6-381E157DF5C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"635c77a39b27ee22a5bfcde299ab7a563c7614e1","datavalue":{"value":"20D60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$DFDC520C-B698-4F30-BCB6-3F5BCE00B963","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2e13b93ae23ab302987e2841111eae8d33fac71d","datavalue":{"value":"1117773","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$8F6BE6BE-0117-4A7C-AF21-D4E11E0E2A05","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b07fe34f0773cdffa0944406228855f3aed26f5","datavalue":{"value":"bases","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378433$80C92A44-1D45-433C-97C1-AA096C23D925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1a61b2a172f5869253edd96e89bf25d5f6f6089c","datavalue":{"value":"base sizes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378433$3E035F57-4678-4643-8362-0507BBC37003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"901a9df279aa2ad41eaee88407011e6ef2970601","datavalue":{"value":"primitive permutation groups","type":"string"},"datatype":"string"},"type":"statement","id":"Q1378433$2359B4A5-2A0A-4072-8152-1155891A028D","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":"Q1378433$A38569B7-C03B-4949-AB92-8F3F36A2D1AE","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"99bf7d9484cf6f73cbc0efacbfe7db5319f3a072","datavalue":{"value":"W1996938202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$AE1B1D75-F2F5-4519-9474-FC491C21E180","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2fc386985eef6432b464b56a6d18a2fe1ce30bd8","datavalue":{"value":"Q123138859","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$F0D90489-3F50-4DE4-8E56-EBA276DAB731","rank":"normal"}],"P223":[{"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":"Q1378433$B39C0859-7398-4C34-91A9-D283DF1B3058","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a30855408a0aeeb826f54eccde04e276d0f15df3","datavalue":{"value":{"entity-type":"item","numeric-id":4289292,"id":"Q4289292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$9952F48A-065A-4FA6-823D-37F2BAA9BFBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa5c0aa6c81cc0d66ae9f76144e781a146e3473b","datavalue":{"value":{"entity-type":"item","numeric-id":1064400,"id":"Q1064400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$2001D0CA-9535-45DC-B362-FB8ADEB65FB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97654eaa6344954ff92e116f8b05b82baf9bc761","datavalue":{"value":{"entity-type":"item","numeric-id":1824687,"id":"Q1824687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$EE80AE06-8261-413B-8D71-850565C943DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf66bcfab6fc3a3664696902ccf48c3f244efdce","datavalue":{"value":{"entity-type":"item","numeric-id":4265462,"id":"Q4265462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$B3AEF570-7BED-4E27-9CAA-5B192734985D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf549ab96001983adefe8ae7db075248c6194842","datavalue":{"value":{"entity-type":"item","numeric-id":5577154,"id":"Q5577154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$2499ECF2-B981-4F8E-B5FE-88B37113F42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"814694d1e1620844e9c6e796f00873200ca16bdf","datavalue":{"value":{"entity-type":"item","numeric-id":4025285,"id":"Q4025285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$B98B98B2-F3C8-4B30-B22A-142A36DBE8A9","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":"Q1378433$A7026B24-4AA7-427C-8F70-611442C0FBFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6dfbb8de8ebe678649cccab00d03a5d557f26b9c","datavalue":{"value":{"entity-type":"item","numeric-id":3791327,"id":"Q3791327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$9ED39EDA-66F1-4493-8798-A35FBC997BF5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be883cfffd784f24e0e2b9455eeb73a912154d68","datavalue":{"value":{"entity-type":"item","numeric-id":3472282,"id":"Q3472282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$B3A82816-4F18-425C-AE6F-AB1D521AE0F2","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":"Q1378433$6339BB5D-B22B-421D-9E4A-ACB3A4D6393B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"067e393b8b4356a444ebb86fe4868b077a480748","datavalue":{"value":{"entity-type":"item","numeric-id":4273608,"id":"Q4273608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$0FBBACE0-879A-4322-813D-3743B4EAFC38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6dca6e4a9c4213d1d9359ac472682848672775f","datavalue":{"value":{"entity-type":"item","numeric-id":4273611,"id":"Q4273611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$A6B4672B-48FD-4C1D-BF8C-FF900F46A0FD","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":"Q1378433$34F57A11-543B-455A-953F-790C6F89C4AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56ba5b2183815c2cc66a473df7832b17d3b68cf5","datavalue":{"value":{"entity-type":"item","numeric-id":4894502,"id":"Q4894502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$F4BB317B-711A-4276-901A-6EAAC54C6154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17816cffc2fa882a86a6f7a15f1f47aa9771e439","datavalue":{"value":{"entity-type":"item","numeric-id":4354175,"id":"Q4354175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$38ED9B8F-AF05-4D90-9B78-CBFA17DBE35F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d545d46281c27f7c22d936768292713b57021712","datavalue":{"value":{"entity-type":"item","numeric-id":5617749,"id":"Q5617749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$9884447A-0B4B-4AFC-866C-3CCA1391FA72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62b61d3b3afc5d4c5f6840743f22bcddd28ebac1","datavalue":{"value":{"entity-type":"item","numeric-id":3712472,"id":"Q3712472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1378433$CE77B52B-A684-4AE0-BBAF-49863AE5BD4A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d3250c2c5248b6391289f25e7c2662a1b7342a5c","datavalue":{"value":"10.1006/JABR.1997.7149","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1378433$0DEE7D17-DBE1-40DB-A89F-45CA48F8E985","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1a61ed41e007e2f7a5a6f43ac9a7a0f3295a754","datavalue":{"value":{"entity-type":"item","numeric-id":4426042,"id":"Q4426042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fd6f8dd2cf482763d0e6ebf02ce181907bcfa0d","datavalue":{"value":{"amount":"+0.906197428703308","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":"Q1378433$004991D6-5E65-4FE7-B08C-AF4D1FB31013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06f933e6faefb7d27307df66cddff371429b34ac","datavalue":{"value":{"entity-type":"item","numeric-id":1755548,"id":"Q1755548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcdd466f7cd8ffc9139a9f4713a175386c373938","datavalue":{"value":{"amount":"+0.8792744874954224","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":"Q1378433$686B64F2-DE86-4C0E-AC13-95F6E35DCE50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"138efe82689ba96637d94a32b7d2fb683f180440","datavalue":{"value":{"entity-type":"item","numeric-id":5251609,"id":"Q5251609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15a3b55a321ac559e36a40b39ed5bce2e4605e62","datavalue":{"value":{"amount":"+0.8721569180488586","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":"Q1378433$965B5EC1-3852-4172-A9C9-02A62DD72760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"88c3ba2371450180b80cb3f478048543b19a5aae","datavalue":{"value":{"entity-type":"item","numeric-id":796623,"id":"Q796623"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e05ce5bdfad26c817411312b50790606026769a0","datavalue":{"value":{"amount":"+0.862640917301178","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":"Q1378433$7F346F8F-2250-488A-BBA1-D144C8A308C2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1378433","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1378433"}}}}}