{"entities":{"Q426906":{"pageid":428673,"ns":120,"title":"Item:Q426906","lastrevid":61832364,"modified":"2026-04-11T01:58:27Z","type":"item","id":"Q426906","labels":{"en":{"language":"en","value":"Distinguishability of infinite groups and graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6045720"}},"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":"Q426906$44CFD26B-954B-4A96-95E6-3CE7FE23B10B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"286138986321662ef82e59cdcc135288be811dbb","datavalue":{"value":{"text":"Distinguishability of infinite groups and graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q426906$CC1B15A5-F8BB-422D-9E71-87B298058C57","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9dfbf1d2c9e3c60d031ace43aded7ad7d269eb3b","datavalue":{"value":"1243.05086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$3A167AD9-78D0-464E-872F-DC9A6759FDB2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a260a4f6b90720140936bf1db32adbfec655f412","datavalue":{"value":{"entity-type":"item","numeric-id":426904,"id":"Q426904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426906$8BDCAE3D-07AD-469C-988F-42806019FA40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c9bf29c828b7ac351e638d79ef0f2ab08aa30d2d","datavalue":{"value":{"entity-type":"item","numeric-id":276787,"id":"Q276787"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426906$9D2A073E-56AA-4B06-B433-9CD94B07A43C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"07ca714b82feff525ef5fe415b0b0e291c5c714f","datavalue":{"value":{"entity-type":"item","numeric-id":426905,"id":"Q426905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q426906$5D541F0A-A4E6-456C-9B15-3BC1FE110A43","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":"Q426906$E4FD1723-AA01-4C9D-9ACC-0915BE3AC500","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4bc8e8f32e3771ea3dc331f4cf4795267b160813","datavalue":{"value":{"time":"+2012-06-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q426906$343EBFF1-F089-4A17-BA3F-123C8E6CCC8A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3ce1876c4083ce9d005641d74904ed8654ca308d","datavalue":{"value":"https://arxiv.org/abs/1106.4778","type":"string"},"datatype":"url"},"type":"statement","id":"Q426906$837147B9-73D7-4D51-909C-3C3E9CC6B26A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"ec448e7f459252897846fa60b110410b121a39b0","datavalue":{"value":"http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p27","type":"string"},"datatype":"url"},"type":"statement","id":"Q426906$5DC65180-1E79-4C02-891C-BE7B49A8CE92","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b8b07194ca0b3e913373853867fa828ae6751962","datavalue":{"value":"Summary: The distinguishing number of a group \\(G\\) acting faithfully on a set \\(V\\) is the least number of colors needed to color the elements of \\(V\\) so that no non-identity element of the group preserves the coloring. The distinguishing number of a graph is the distinguishing number of its automorphism group acting on its vertex set. A connected graph \\(\\Gamma\\) is said to have connectivity 1 if there exists a vertex \\(\\alpha \\in V\\Gamma\\) such that \\(\\Gamma \\setminus \\{\\alpha\\}\\) is not connected. For \\(\\alpha \\in V\\), an orbit of the point stabilizer \\(G_\\alpha\\) is called a suborbit of \\(G\\).   We prove that every nonnull, primitive graph with infinite diameter and countably many vertices has distinguishing number 2. Consequently, any nonnull, infinite, primitive, locally finite graph is 2-distinguishable; so, too, is any infinite primitive permutation group with finite suborbits.   We also show that all denumerable vertex-transitive graphs of connectivity 1 and all Cartesian products of connected denumerable graphs of infinite diameter have distinguishing number 2. All of our results follow directly from a versatile lemma which we call The Distinct Spheres Lemma.","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$86BDE813-8734-4414-B472-217B01FE515F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$5FD09F87-1DEB-4B2B-8AD0-357DE9C533F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$3929F3E5-62AC-4AC4-8881-C8D006E4CD0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$15C5F3DA-8F1A-4216-9B87-461A8EFEF647","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3367018dbe2ad5da0826b32cb1ef14710133d281","datavalue":{"value":"20B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$18B493C7-E0D5-406A-8B5D-20E3D096A26F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"512f02c3a91060c0a6967ce7e6a4f8fc6304bb6a","datavalue":{"value":"20B27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$4FCB3A17-7934-45FE-AA05-4869513A8FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$B81C0D07-0AF7-438B-8ACF-21BC0DB5CEDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$BDBA29B4-4C0D-4B81-B887-7A31F4515EF3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3d85c16e418da6bb54ab0f732622293429bd3f6","datavalue":{"value":"6045720","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$0069181E-F483-4296-BDCB-65767530791F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f161ce45f2c032a5d05185ff52a7738050ecdea9","datavalue":{"value":"distinguishing number","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$B36AA91D-65E7-464D-8841-BA1E5BC8F772","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8c8f99744a7f0aae8fc0a2a337142f10dc4f721","datavalue":{"value":"primitive permutation group","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$CAF377E2-DE70-4AD5-A047-95A2D92F317F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6807b30d9e2a6cf0d305b0f91b44b367ba3358b9","datavalue":{"value":"primitive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$7E70A1CA-60FD-408C-A009-E0F1589497D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fd83f965f8889eb6ba665bd69eaf11aad7ea5728","datavalue":{"value":"distinct spheres condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$2724A79E-6702-47A5-B488-392B84803CBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0effef6748ed1a9c05674138f14f425a024befa2","datavalue":{"value":"infinite motion","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$4FBAA775-6EEB-49C6-8E67-4A67BB57612A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ede3a47d3a11fccce93579dad1b64259f6783d5","datavalue":{"value":"Cartesian product of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q426906$6025928C-3755-48A4-8E67-DD6B2F93BFE8","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":"Q426906$360B8677-9F4D-426F-ACA6-A8DA099BB7A2","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"0e006ae183480fe98839a1758660c6b368f3a836","datavalue":{"value":"bafkreifhxuhgbwf3tp3x7biskv3465dljftzvfmfn7wzpgl73jzlguerxu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q426906$1BFAE927-0773-4A43-826A-8A448B1EC316","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58a9983fa7b704bcf0ba0e11d2931d958326ad87","datavalue":{"value":{"entity-type":"item","numeric-id":743653,"id":"Q743653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b5135f6989536861f1f40cfae10b31b6fb1d0b4","datavalue":{"value":{"amount":"+0.9015443921089172","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":"Q426906$8BFE1AD5-C62B-4E97-A66A-DDE7F50EA41C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df39062875e10818efb78e987361c0b8872d648b","datavalue":{"value":{"entity-type":"item","numeric-id":764823,"id":"Q764823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e18d6d252025be201b5e9ab989ae207b020a9f54","datavalue":{"value":{"amount":"+0.8455955386161804","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":"Q426906$2467F3E4-A54A-48E1-BA0F-D035DB6B1D92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0b7aa659452c357c5dd4ee4aa6a91e926dc2cbd4","datavalue":{"value":{"entity-type":"item","numeric-id":2372880,"id":"Q2372880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28ea88d29c4cfa2a289a40fdfbb007d36f64cad3","datavalue":{"value":{"amount":"+0.8398376703262329","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":"Q426906$463C0D19-70CA-4DD2-99D3-46307D61E64B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fcf46ca2a3159140e56fe356bd976f25a17300f","datavalue":{"value":{"entity-type":"item","numeric-id":1883683,"id":"Q1883683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a78ce408bc6bfe5b3588719ef15b8919bc82d40","datavalue":{"value":{"amount":"+0.8320889472961426","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":"Q426906$E6E193FC-2236-4499-BE67-C787D7D64018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7988663128e7c16d6d6618d0a59a58639c28b950","datavalue":{"value":{"entity-type":"item","numeric-id":2256057,"id":"Q2256057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb0a690853e17136e5afa12e5d7a16cad0554888","datavalue":{"value":{"amount":"+0.8293782472610474","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":"Q426906$ED039F2A-853F-4793-A279-7C0705945E94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Distinguishability of infinite groups and graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Distinguishability_of_infinite_groups_and_graphs"}}}}}