{"entities":{"Q2555083":{"pageid":2565826,"ns":120,"title":"Item:Q2555083","lastrevid":48653446,"modified":"2026-01-05T12:29:25Z","type":"item","id":"Q2555083","labels":{"en":{"language":"en","value":"On the capacity of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3387380"}},"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":"Q2555083$AC91FC0C-2725-4F68-BF05-F12237C8CE40","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"173c731d6fc14efe15e7e11110fa89ea8c699f92","datavalue":{"value":{"text":"On the capacity of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2555083$75B4591C-10A2-4749-95F7-9E316079E7FA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fab810c3a899a156e3a96a0c7677dca4555c1b9","datavalue":{"value":"0245.05112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$0AE53846-A798-46F3-8D34-30479CFCC1A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1876cf840b880784bc9107b4c6e4ce009cf13407","datavalue":{"value":"10.1007/BF02018467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$D8431197-CA2C-4E95-B233-04C91A22A271","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"494f1ab1373bf3235b5cb823eac7ac66915a0004","datavalue":{"value":{"entity-type":"item","numeric-id":190555,"id":"Q190555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2555083$1F44BFE4-0E9F-4BDA-933C-FF8B21D8EF7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb00475fd567190194461a0f087df1793eeae7c4","datavalue":{"value":{"entity-type":"item","numeric-id":6480801,"id":"Q6480801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2555083$677C755E-116E-4A85-889E-AE5E93A832F8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"615950119797f35f49728e278e9727b73c5c7f8e","datavalue":{"value":{"entity-type":"item","numeric-id":168620,"id":"Q168620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2555083$3C9DDB18-1FAC-4F16-80EF-5055AA72A69C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0009eef2e40e65b679945693e20705f9c6245b14","datavalue":{"value":{"time":"+1973-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":"Q2555083$87637D5D-7F23-4169-979B-45A6A414C365","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8bd70317350f8b10d765ef1053039a618824f17c","datavalue":{"value":"Let \\(G_n\\) be a graph of \\(n\\) vertices. Denote by \\(v(G_n)\\) the capacity of \\(G_n\\) (i.e. the number of non isomorphic spanned (in other words induced) subgraphs of \\(G_n\\)). Put \\(v(n) = \\max_{G_n} v(G_n)\\). Clearly \\(n \\leq v(n) \\leq 2^n-1\\). Goldberg conjectured \\(\\lim_{n \\to \\infty} v(n)/2^n = 0\\). The authors disprove this conjecture and in fact prove the following stronger Theorem. For every \\(\\epsilon >0 \\) and almost all graphs \\(G_n\\) (i.e. all but \\(o(2^{\\binom{n}{2}}\\) graphs \\(G_n\\)) we have \\(v(G_n)>2^n-2^{n(1+\\epsilon)/2}\\). On the other hand for all graphs \\(G_n\\) we have \\(v(G_n) \\leq 2^n-2^{[n/2]}-1\\). After submitting their paper the authors found that their main result has been proved earlier in a somewhat different form by \\textit{A. D. Korshunov} [Mat. Zametki 9, 263-273 (1971; Zbl 0206.26201), Engl. translation in Math. Notes 9, 155-160 (1971; Zbl 0226.05118)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2555083$D4428845-635E-4D30-9890-E59850E3FD81","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$4CE6EEBE-F73A-4AD4-B326-0E29CB15562A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$A467B85B-C953-43E8-90AF-71CFA041CFD9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e7c2bd17e448e86ee406a65264192ed08b875c0","datavalue":{"value":"3387380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$6E01DE3B-AC6E-4698-83D9-A54B7008AF22","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"cdb1100c9b9c878bbdc0d93726af1a558a022dd6","datavalue":{"value":"Q105815880","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$CDD1BF3A-8128-43C0-B3AC-83212CD03426","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":"Q2555083$77CF7F25-5FB3-4531-A727-AC03B69EDFFB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1f874b963cb14d726ebb29ea46edb663672be021","datavalue":{"value":"https://doi.org/10.1007/bf02018467","type":"string"},"datatype":"url"},"type":"statement","id":"Q2555083$A0EF0688-5758-4183-BD65-BF92AA754026","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c673745e2dd356c4804453b69fe66a1359f8a5a0","datavalue":{"value":"W2072750184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2555083$F4D4C4DD-8D43-4A42-8435-0188199C786E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f82b3568a09d03d565d02ce101eb79d8d1b4560","datavalue":{"value":{"entity-type":"item","numeric-id":1378288,"id":"Q1378288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cf2810a67c7f13cba9153c03f6b3b0913d1b1e9","datavalue":{"value":{"amount":"+0.7866926193237305","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":"Q2555083$BEE21217-DB86-475B-830D-95C518B04811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4eed5b571af79738e2e3c43145898ea9356dbe1","datavalue":{"value":{"entity-type":"item","numeric-id":4797464,"id":"Q4797464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7949c412c59c767cb2a7e8e8ff44c742f8f3fa2","datavalue":{"value":{"amount":"+0.7565595507621765","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":"Q2555083$C47207CE-FBC7-4044-B370-F7A8AD454D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"73a315b596d5ef991f0767a7dc82dc34b8b9b292","datavalue":{"value":{"entity-type":"item","numeric-id":1334937,"id":"Q1334937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca378150162bbe9a3ebe58f064c5fb6f14998636","datavalue":{"value":{"amount":"+0.7562596797943115","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":"Q2555083$FB536823-9F08-4BAA-BB40-5CFF0C3D926F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed27e02163e2a3ec4629e8db78aa68c2a26a68c5","datavalue":{"value":{"entity-type":"item","numeric-id":759767,"id":"Q759767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb10506093777eaad6341bff100e9997137526a7","datavalue":{"value":{"amount":"+0.7558165788650513","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":"Q2555083$B8CA64AE-8BD7-400B-9B77-9230C38F69A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20c1506eea3c472e2afb18dcefc3f3221d079a5b","datavalue":{"value":{"entity-type":"item","numeric-id":4858441,"id":"Q4858441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30841805296471492052195703e1e55998e93528","datavalue":{"value":{"amount":"+0.7541948556900024","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":"Q2555083$49F23439-B50E-4056-978E-19CB4A5402B4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2555083","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2555083"}}}}}