{"entities":{"Q1964591":{"pageid":1975333,"ns":120,"title":"Item:Q1964591","lastrevid":47445274,"modified":"2026-01-01T18:47:23Z","type":"item","id":"Q1964591","labels":{"en":{"language":"en","value":"Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1404390"}},"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":"Q1964591$6D9B7BED-19C6-402D-9F92-EA0D5277FB3A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"50b7a7c6383e7c5826c449d20caf40a9b061f200","datavalue":{"value":{"text":"Isomorphism of coloured graphs with slowly increasing multiplicity of Jordan blocks","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1964591$43ED6D04-E219-41A6-960D-FF38CEA03297","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"03c21432efd8b2ef37db4f6d0a0731f8fc9abe9b","datavalue":{"value":"0932.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$6D3B399E-A330-459E-B8FF-01AC1C99B88B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ffc4ca9ffe9b521823c53470cb477649b8ecdfa","datavalue":{"value":{"entity-type":"item","numeric-id":190545,"id":"Q190545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964591$6E06DF3C-6478-4241-978D-D0C9B164C872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"954ce4c1c3c6681916e1d055d84b8f311ee401fe","datavalue":{"value":{"entity-type":"item","numeric-id":1669755,"id":"Q1669755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964591$3B246C38-A9D2-47AC-9ADA-A41FB41342BB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964591$8752E50A-B78A-4CB7-935F-D838B9C0C04B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b17fbfec200bcf11c37dd1a72a5e177de6557760","datavalue":{"value":{"time":"+2000-02-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1964591$FDEFB56C-7B42-45FF-9DF6-6F85EC6FB8EE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"434eb01e4d284d88f31ce6bbdb74db1745d24582","datavalue":{"value":"The complexity of the graph isomorphism problem is unknown: for general graphs with \\(n\\) vertices the best known upper bound is \\(n^{O(\\sqrt{n/\\log n})}\\). If the multiplicities of the eigenvalues of the graph are bounded by \\(k\\), an algorithm of complexity \\(n^{O(k)}\\) is known. This is now reduced to \\(c_k n^{O(1)}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964591$D1E18DB1-A905-4AC5-B721-F92C0EC7DDDF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964591$53E09ED3-80FB-42A5-A85E-E7D93371A98F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$34FEC437-06DA-4C8D-8C23-0D515F4A41E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$E0E7C128-E1D0-4988-94D3-B07B3077FDF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"86c47e3aedde4615dd16421ee43ac00d4048a5ec","datavalue":{"value":"05B30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$E4F11914-FD35-470F-95AB-F2102039D086","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c046afb507fdbb4fafc5f6cedad958de2e3de406","datavalue":{"value":"1404390","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$59E969EC-BB49-41E7-BF33-0B5A9F3EBA05","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09576650caae668aaffec950873b8e2e60af4088","datavalue":{"value":"coloured graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964591$F118209C-9E13-41A8-A56B-6138B36CE324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1ecd9c7b4f2442ba13bbaf86ca3447d9fa71ad","datavalue":{"value":"Jordan blocks","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964591$DCB8DCCB-0DE2-48B9-A043-382141EB471D","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":"Q1964591$9D069873-11D1-433A-9283-BDA929887967","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"570e89477634f81c0084b4117253fc9c1cb11685","datavalue":{"value":"https://doi.org/10.1007/s004930050059","type":"string"},"datatype":"url"},"type":"statement","id":"Q1964591$00F45412-7CBD-40AE-833C-EC90AE3241E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d8584c8db1792b9a4ab4ec5bf074022effe08226","datavalue":{"value":"W2035859428","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$9F652F6B-23CB-4B2A-BB5B-A41FDB6AE0AF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c2bd38796e383b2c295507e257e298f4732d7efe","datavalue":{"value":"10.1007/S004930050059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964591$60383DEF-C3EE-4468-BC58-055D05C36DD2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0b5e37371c99e25be61bc3415a93d8593494d95","datavalue":{"value":{"entity-type":"item","numeric-id":896861,"id":"Q896861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52642eb65c4842233d888b0088ae852e472b3e87","datavalue":{"value":{"amount":"+0.8459019660949707","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":"Q1964591$1BEF1C39-043D-48BB-B5F0-12ADF2F739E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"020ed30bac7022552f1230de21dd8f858d34771b","datavalue":{"value":{"entity-type":"item","numeric-id":4628505,"id":"Q4628505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dd1c29f5ea455f55cb75d10793131a4634b5f42","datavalue":{"value":{"amount":"+0.8140496611595154","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":"Q1964591$C7FD39BB-4EFA-4866-B37F-70EDA473C01D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"795e4678d341f9f755f5982ad54550ca4f0e4423","datavalue":{"value":{"entity-type":"item","numeric-id":1328437,"id":"Q1328437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2898f678005e88a5a2a0a6e2a9dda75bfc718df4","datavalue":{"value":{"amount":"+0.8124589920043945","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":"Q1964591$0DE26B54-9A47-4D43-A832-8CAD7CFB1FB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbbde873cb0f98b9c983dff91a4b70e261d410aa","datavalue":{"value":{"entity-type":"item","numeric-id":4736833,"id":"Q4736833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f9fdae383d60f9bb67e77d8050da8802431d419","datavalue":{"value":{"amount":"+0.8082383275032043","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":"Q1964591$B3C9223A-93C0-4F97-8E56-541876A6A50C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6fd98be4342853169e7482647385dbe4c0a0b58","datavalue":{"value":{"entity-type":"item","numeric-id":4710599,"id":"Q4710599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c246db0075e38e6101084b0e862d73ff2a81d05d","datavalue":{"value":{"amount":"+0.79458087682724","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":"Q1964591$24C3A4DC-4999-412C-A274-F1E3337B3774","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1964591","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1964591"}}}}}