{"entities":{"Q757411":{"pageid":759260,"ns":120,"title":"Item:Q757411","lastrevid":42677502,"modified":"2025-07-08T09:44:50Z","type":"item","id":"Q757411","labels":{"en":{"language":"en","value":"The edge-orbit conjecture of Babai"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4191697"}},"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":"Q757411$6AF639C2-BECB-4613-A9B6-250376CF66CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b66336fb2c0341736ed76129118b31165a791fac","datavalue":{"value":{"text":"The edge-orbit conjecture of Babai","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q757411$16AFC13B-4A76-4D93-BEB8-1D85CA67B715","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a14a924fa4a5e361e177365edd2890d0be5ad41","datavalue":{"value":"0723.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757411$591B743F-DC03-48F9-8E6D-421FAA30156E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2e84d1e09ed640246d9a468f9d6b9a1df10954f3","datavalue":{"value":{"entity-type":"item","numeric-id":757410,"id":"Q757410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757411$489A3FB5-4008-4BFA-9097-EC8C9C63B139","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757411$749BC30C-3AC3-41E6-8372-5DD71BF64B3A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q757411$3CDA7339-3F3E-4213-8A56-7C02B6EB7B4D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72862c0364924541817c4eb99d624e722bf6b508","datavalue":{"value":"This paper proves the Edge-Orbit Conjecture stated by \\textit{L. Babai} [Combinatorics, Proc. 8th Conf., Swansea 1981, Lond. Math. Soc. Lect. Notes Ser. 52, 1-40 (1981; Zbl 0467.05031)]. A graph X is said to represent a group \\(G\\) if \\(Aut(X)\\cong G.\\) Let \\(m(G)\\) be the minimum number of edge orbits among allgraphs \\(X\\) which represent \\(G\\). The Edge-Orbit Conjecture was that m(G) is unbounded when \\(G\\) ranges over all finite groups. This is shown to be true using \\(p\\)-groups of class two and exponent \\(p\\). The proof uses a characterization theorem from a recent paper [\\textit{L. Babai}, the author, and \\textit{L. Lov\u00e1sz}, Eur. J. Comb. 12, 185-203 (1991)] to bound \\(m(G)\\) from below when all subgroups of \\(G\\) are either `small' enough or `large' enough (so that there will be enough automorphisms leaving any small set of subgroups invariant). Then a probabilistic proof is used to show non-constructively that plenty of groups exist whose subgroups have this property. The proof shows that there is an infinite family of groups \\(G\\) for which \\(m(G)\\) has a lower bound proportional to \\(\\sqrt{\\log | G|}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q757411$C96646CD-9BA4-4613-9D6B-F5889EB7F50F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"049723a0d6b9805299dc5ac60f4b30f3ffca1d3a","datavalue":{"value":{"entity-type":"item","numeric-id":757410,"id":"Q757410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q757411$2E5F793F-0009-4047-841E-D3D6AA0B13AD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757411$07C93024-B165-4DDB-A8FD-B69E82393640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"677f074949b6912a3d5be9a52164e3a800597639","datavalue":{"value":"20D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757411$AC2F15D7-1D36-45A8-8AD2-88C3C1342EFB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ddb89d3f6211390ec1f7df18fb5c04197fe79ae","datavalue":{"value":"4191697","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757411$99EA6B87-72A1-4895-88FA-D7CD5EF5BE67","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ff4015ba676a4825b070600b0457628db92d70d9","datavalue":{"value":"edge orbits","type":"string"},"datatype":"string"},"type":"statement","id":"Q757411$9D250478-BEDD-407A-900A-8C4973CB1157","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":"Q757411$7AC818A5-BA0E-4A19-BCC1-AA56A25DC8A0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"76013026195bd28f3c838ad012715f8a1f7c8af7","datavalue":{"value":"https://doi.org/10.1006/jctb.1993.1003","type":"string"},"datatype":"url"},"type":"statement","id":"Q757411$DC5A63C3-AF3C-43F9-B78D-3953890C064E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f7bfd4f932444f6ccd197e7396c37925c8cba02d","datavalue":{"value":"W2007784827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757411$3CF37FAF-F4F1-4726-AD0D-26392523F9EA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8448cf9d2ef0f5999a3ece9142c14def6cf48da1","datavalue":{"value":"10.1006/JCTB.1993.1003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q757411$2E4A5D02-292B-43C1-A868-DA705F08D566","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f60653ddf4f0360fbc403f63892c702d858cb5e","datavalue":{"value":{"entity-type":"item","numeric-id":1176027,"id":"Q1176027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d408e7babb1ab3bcd44c1405fdbe6e659b68029","datavalue":{"value":{"amount":"+0.8492132","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$F4D42ED0-CE58-4838-AC23-B2394D61DABE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2756c4d9e510ed1e6572b4c99f15d382b5bd6d69","datavalue":{"value":{"entity-type":"item","numeric-id":1122587,"id":"Q1122587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f562e3a3f73fc37d9bec8c85ac4bcc1d5c1afc3c","datavalue":{"value":{"amount":"+0.83046114","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$9485B26C-8CAA-4747-8BED-12605BD6D7B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4685464fd5f7b733ff0a3bfe88d555ae5ae13b28","datavalue":{"value":{"entity-type":"item","numeric-id":1072562,"id":"Q1072562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d3f5c0532bc3b69c522cafabfd55216964cfd32","datavalue":{"value":{"amount":"+0.76165515","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$80A13521-F343-4330-9100-CC4D50D38923","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab20d0a9dff7b864bcbeb98da60287ebedb7c258","datavalue":{"value":{"entity-type":"item","numeric-id":3161699,"id":"Q3161699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5983be76654b73fa391c73fae122e409fea9f4ce","datavalue":{"value":{"amount":"+0.7447251","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$F1A8297C-04C5-4C13-84A6-39FA4C7F9FF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cea98403f21087deafe7345fe92efe016f58e2d","datavalue":{"value":{"entity-type":"item","numeric-id":2164988,"id":"Q2164988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"050fa6415b890a1959e5fbd31c5b31d500276fe5","datavalue":{"value":{"amount":"+0.72015166","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$8B99C633-69E0-4301-8C29-2373DBD58D0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"807f951daeb6d97c6f7b3853753a114c54205e7f","datavalue":{"value":{"entity-type":"item","numeric-id":3436058,"id":"Q3436058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59d97be4ce865e92932fadca084b72d4b895b141","datavalue":{"value":{"amount":"+0.70780313","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$08532C83-C5F0-439D-8F4F-50FD039E3BA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6eeb4fb6c6efcc99a1e7104f2bbdd4d963bf7d45","datavalue":{"value":{"entity-type":"item","numeric-id":510056,"id":"Q510056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c2cedef8e60405102c7990eabbfb28ce8ea9c02","datavalue":{"value":{"amount":"+0.7007123","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$1B865455-293A-485B-A7DE-3EFE9E4178BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2b0a34a61d6a5f9f31a34d075da4bf3de016d91","datavalue":{"value":{"entity-type":"item","numeric-id":2866614,"id":"Q2866614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09706afa7a7b16afdb30735fc30e584d1ff9e1c3","datavalue":{"value":{"amount":"+0.69580036","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$E1A507B3-EE3B-47C2-A3BF-972809DF14F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3c0348ce4ef6d19a30f8664da6dbc7a143cd7bd4","datavalue":{"value":{"entity-type":"item","numeric-id":3446762,"id":"Q3446762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"312e024835aeacb82b31e3bba3e4e2e01b2d8643","datavalue":{"value":{"amount":"+0.6873201","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q757411$FABFC65A-20CC-4929-9D37-7F092EDBA6E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:757411","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:757411"}}}}}