{"entities":{"Q1201273":{"pageid":1212022,"ns":120,"title":"Item:Q1201273","lastrevid":47117761,"modified":"2025-12-31T17:55:05Z","type":"item","id":"Q1201273","labels":{"en":{"language":"en","value":"The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 97518"}},"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":"Q1201273$4C67AD56-20E3-4019-A4A0-3B19CB203321","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"46378390910d47fa074813dadfdecc73ffea6035","datavalue":{"value":{"text":"The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1201273$3370AD31-95FE-422A-9B86-A028A69E7FE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8bb472165ff9440af195216e0b5e8a73b979d3ae","datavalue":{"value":"0776.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201273$5C75C8CA-FF55-42D0-894F-433F61EF3EB0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"618b6c6b2d7603ed871775d2ebc06c47c5573227","datavalue":{"value":"10.1016/0012-365X(92)90691-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201273$932AA165-5EBA-4DD0-AC14-0DBA23549232","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201273$DB90D418-3032-421C-B2D9-E0B89D8915E0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1201273$6A9809B6-3FD9-4D00-A4F0-62229D5F2BF1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e73cb5d2b1a29bf24f7ab60d0e12ea694471fefe","datavalue":{"value":"Using a noncomplete extended \\(p\\)-sum of graphs [see, e.g., Section 2.5 in the book by the reviewer, \\textit{M. Doob} and \\textit{H. Sachs}, Spectra of graphs. Theory and application (1980; Zbl 0458.05042)] the author constructs an infinite sequence of graphs \\(G_ n\\) in which \\(\\text{rk}(A(G_ n))\\leq O(n^ 3)\\) and \\(\\chi(G_ n)\\geq\\Omega(n^ 4)\\), where \\(A(G)\\) is the adjacency matrix of \\(G\\), \\(\\text{rk}(M)\\) is the rank of \\(M\\) and \\(\\chi(G)\\) is the chromatic number of \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201273$F8EDE01C-FF26-44EF-9CE8-6E581B13B0EA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201273$7DBE8A7F-963F-467D-B578-6D03B80DDBEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201273$9B2BB079-7AD9-49B1-902B-76DD820F1B16","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a3816866adb39a6679d1e25bc12e54e1fda2ec19","datavalue":{"value":"97518","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201273$77B65F55-1937-44D0-82EF-E4D8B54D14CB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc95e5f05c3d9f83a111dedb75f49c2d26fec40f","datavalue":{"value":"adjacency matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201273$E2E2419F-4D7F-4EEB-ADE4-D98CF616158D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1201273$8ADF13A1-3853-4C77-9087-EB721F757B6A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c0bcfb4eb9a7ab6903b269f394ffde6834d9319","datavalue":{"value":{"entity-type":"item","numeric-id":1370854,"id":"Q1370854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201273$2940923C-0775-4BAD-9737-F6EAF95B107A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b3577c3d7f986f4c743a6ff2b0869a6edb9e5611","datavalue":{"value":{"entity-type":"item","numeric-id":1299997,"id":"Q1299997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201273$69B682C5-FC57-46CC-A883-9A471287E6F1","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":"Q1201273$D9E832E2-1E2E-4C8D-BAB3-4B53C7055AB9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"eefedcdc477e12e593dc7a8afc9d4cbaff06e74c","datavalue":{"value":{"entity-type":"item","numeric-id":3828021,"id":"Q3828021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201273$00A98A8C-B647-481C-B956-6E77A56ABD25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5cc6577b87eca431887bce74244e5ed68b9fc11b","datavalue":{"value":{"entity-type":"item","numeric-id":4327350,"id":"Q4327350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1201273$33D66D45-7F99-4B17-9EE7-3261C0DFCD93","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f6eb92d1cfa0b585c0615f4fa45aa5f8b83b636d","datavalue":{"value":"https://doi.org/10.1016/0012-365x(92)90691-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1201273$2A4282A9-2701-4993-9AF5-3EFE61EB17A7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6745cf26961c108ea1439b8fff00b17f75d75e02","datavalue":{"value":"W1968769959","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1201273$D056FC03-85DB-4DDC-89B7-E22E2C178DC3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd2ac8d899f13450d540f436893f67c1dcf5a99c","datavalue":{"value":{"entity-type":"item","numeric-id":3828021,"id":"Q3828021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b1503418a9b614b843fc04b9bd9bf5de06b77d9","datavalue":{"value":{"amount":"+0.8199922442436218","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":"Q1201273$8A885692-D7DC-478A-8AF4-5F055A04B745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31f1fdd66589f2021a19302d98d6d9daae1070ab","datavalue":{"value":{"entity-type":"item","numeric-id":1850515,"id":"Q1850515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51582e4d23b88f763aad6cae5e7c748cbbc66b24","datavalue":{"value":{"amount":"+0.8116326332092285","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":"Q1201273$EBA1BA72-CEAB-4470-B07D-1C15C86710C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa1a033ec033217138994eecefc6e738b3dda207","datavalue":{"value":{"entity-type":"item","numeric-id":1764180,"id":"Q1764180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5362e07e4ae9849fb86c82dc864540fd04b0ae6","datavalue":{"value":{"amount":"+0.8105023503303528","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":"Q1201273$3D9E814A-E3EE-4EE3-B033-8A113E1F5FF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f58981c98da38871643221000b6844306b50d7c9","datavalue":{"value":{"entity-type":"item","numeric-id":713979,"id":"Q713979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d432d3bf18869dbbfe5d32e4a00a98b937a54d2a","datavalue":{"value":{"amount":"+0.7896037101745605","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":"Q1201273$F391AAC8-E1C4-4108-8F03-C78F5BD5849D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e13107eed0451d6a0760f446936eb9be889855cc","datavalue":{"value":{"entity-type":"item","numeric-id":1373644,"id":"Q1373644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e1a874aa96b4a8fa1c66e297b57e30e095a396c","datavalue":{"value":{"amount":"+0.7758434414863586","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":"Q1201273$A88FDCE7-B4A3-48A1-9CB2-88B9F829853B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1201273","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1201273"}}}}}