{"entities":{"Q1820168":{"pageid":1830910,"ns":120,"title":"Item:Q1820168","lastrevid":71358729,"modified":"2026-04-13T21:43:03Z","type":"item","id":"Q1820168","labels":{"en":{"language":"en","value":"Embedding graphs in Cayley graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3993612"}},"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":"Q1820168$69DA22F4-2FA7-4AD3-AA02-B135BF546AD5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e99c7f3beeb5c33165823e33bb8e5e08562f0f3","datavalue":{"value":{"text":"Embedding graphs in Cayley graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1820168$5DC55836-D369-4847-931F-0928F9AA8B0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c304c13aab8d4cd3112961d535580600012e0a1d","datavalue":{"value":"0614.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820168$07DA1675-1AD3-49C8-80C9-2DFF070EE478","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f58e77d81ecea5269c77c0b1cc7b6e4361a6cf2c","datavalue":{"value":"10.1007/BF01788527","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820168$0196FB82-B3B1-4F37-A961-CF2414CE7E56","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"10c07f8b7e3cd9f2923ddf5077d5a80431b6d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":201986,"id":"Q201986"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1820168$FC3DF6A3-60A9-4290-907C-0047500E1D03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6519129f4c80a4bd253ead072640f1b27c60f76e","datavalue":{"value":{"entity-type":"item","numeric-id":750451,"id":"Q750451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1820168$DE64625B-1317-4543-B9F5-43C1E3154B19","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1820168$0613D056-A0BF-4A51-907F-B3076D1AA46D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-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":"Q1820168$8C488416-3852-4C6D-B635-65DB79903B7E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"99bfc38fffc97ab7204faa0a7b126bdd68cd7768","datavalue":{"value":"Over ten years ago Babai showed that for any graph Y and for any sufficiently large group G, there is a Cayley graph X of G such that Y is an induced subgraph of X. The bounds given by him for \\(| G|\\) have been recently reduced by Babai and S\u00f3s to approximately \\(9.5| Y|^ 3\\). Using different methods the present paper reduces the bound to roughly \\(3.7| Y|^ 3\\). Better bounds are given for odd order groups and Abelian groups.    It is noted that while there exist examples which show \\(| G|\\) must be \\(O(n^ 2)\\), no such examples exist which require \\(| G|\\) to be \\(O(n^ 3)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820168$2C3416F9-5FD0-400B-8EBC-E31097BEE93B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820168$49F13CE3-615F-446E-B537-838820236D39","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bfb9e08e0b4d3ad67016e295f2c610b190da5bae","datavalue":{"value":"3993612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820168$06709DB1-5151-427C-8883-C1A4B1A7F2E3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9f046045effe4d96bd7d28b79a6e3ca55890681","datavalue":{"value":"Cayley graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820168$8B36D90B-D9EB-4296-8013-E83B47738C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eb4dbee0d48d17c0702756f23f68f3af28651233","datavalue":{"value":"induced subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820168$A2D1DA5C-71A3-47E6-9147-B9FCC368A095","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":"Q1820168$F5A0D745-3BA9-4875-A33C-10BD0E4480D8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a8d60c975c0d3f7e50a663df7a48724e432a788","datavalue":{"value":{"entity-type":"item","numeric-id":1063041,"id":"Q1063041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1820168$32A34814-C3F5-42DA-AF2A-C9CDA47409C0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"377cb31efe5e2d1faf637c33a97c771b81253241","datavalue":{"value":"https://doi.org/10.1007/bf01788527","type":"string"},"datatype":"url"},"type":"statement","id":"Q1820168$250141FD-BDB4-4C29-88D7-84DC5B04DB57","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c45ceb05f2ed40b227719b81f5e55b429f5314a","datavalue":{"value":"W2013794818","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820168$0E4B43E3-8695-4F81-8BAB-4D06E8459868","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"18f0c9a68341ed369e6d65387776c9efddd29e57","datavalue":{"value":{"entity-type":"item","numeric-id":4273613,"id":"Q4273613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0007243bdc6fb1d0d36dc631175c5175513f221f","datavalue":{"value":{"amount":"+0.8193939924240112","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":"Q1820168$C7D87E7A-B826-4C23-861D-B3BBCEFB2DCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7af80a3a5a5e6da2c237425702d2c86c7bc4e352","datavalue":{"value":{"entity-type":"item","numeric-id":2882819,"id":"Q2882819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48fba3c73157158db44ee7e1498376cc21e5a98b","datavalue":{"value":{"amount":"+0.787293553352356","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":"Q1820168$0AAEE507-AC9D-49CA-AF5F-63EBC4D6C5E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b74a8d9e0a6c680216afc1be368d7b93aa880b50","datavalue":{"value":{"entity-type":"item","numeric-id":1363643,"id":"Q1363643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46a5a759efa72530ad0e30b7fe24d1ee11d131af","datavalue":{"value":{"amount":"+0.7872658371925354","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":"Q1820168$86ED9F9F-79A0-498F-A96D-211386896C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4ba9b7aa7a535e14ca56c9490a64588680c481f1","datavalue":{"value":{"entity-type":"item","numeric-id":1063041,"id":"Q1063041"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3e4f0e14d166abf5de7dde86c0486e8fb2fe3cc","datavalue":{"value":{"amount":"+0.7816661596298218","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":"Q1820168$56613AF3-5D58-40A0-80C1-637724D47A46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67f804a6c2a0a9be55e836c5c5e72624b26ed273","datavalue":{"value":{"entity-type":"item","numeric-id":2441636,"id":"Q2441636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8213569ab3860ae52e8c99facdd96b421dce614","datavalue":{"value":{"amount":"+0.7741625905036926","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":"Q1820168$7B6D2EF7-C0F1-45DD-92E0-5754FDB9727D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Embedding graphs in Cayley graphs","badges":[]}}}}}