{"entities":{"Q1972677":{"pageid":1983419,"ns":120,"title":"Item:Q1972677","lastrevid":82135973,"modified":"2026-05-06T20:11:18Z","type":"item","id":"Q1972677","labels":{"en":{"language":"en","value":"A note on sparse random graphs and cover graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1431768"}},"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":"Q1972677$A6EBBBE8-39DF-4C1E-BFF9-195B6CC10D32","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cd21d0f9e6c3287d4e5e42501edd4b63f08708e0","datavalue":{"value":{"text":"A note on sparse random graphs and cover graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1972677$C43AF112-791D-4CB9-B339-CA2752ED0D2C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c5bcc9d560cdea53227e9221a4ec2eb51b5f6d23","datavalue":{"value":"0939.05072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972677$6CF9EA97-5714-45BA-AA9D-691DE6DE8AF9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"044c3bdf3596cdc4b56e2781949e43b4aeb4f370","datavalue":{"value":{"entity-type":"item","numeric-id":200901,"id":"Q200901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972677$D9814687-97B5-4F4F-898B-C2FFF9D21129","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1c64a6508853cedfb7cd8fe343defd54c66096a6","datavalue":{"value":{"entity-type":"item","numeric-id":228772,"id":"Q228772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972677$555F0619-8581-4F8E-BF41-F4857D01AE9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"71e44beb8e65ec4b0b2c30fedb6822ccce4f2948","datavalue":{"value":{"entity-type":"item","numeric-id":228773,"id":"Q228773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972677$6F330542-6A9F-4AE0-A421-8D7ABC56B180","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4ee31696a3be6df3bdd79f474603a4526c11abc4","datavalue":{"value":{"entity-type":"item","numeric-id":1577015,"id":"Q1577015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972677$7C405ECF-A3AD-4799-934A-9348C72FBBF6","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":"Q1972677$E6D2818F-5006-44E0-A188-392F72373990","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fd2d1fe82fa6e2c6e97c965e0ca8e16ed58495a5","datavalue":{"value":{"time":"+2000-04-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1972677$48CDF38C-CF21-42BC-B5F1-6999A116725E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9d523d7f6d069bef5a125b7ef59e452208a80da4","datavalue":{"value":"https://eudml.org/doc/120356","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972677$B4656795-EA5E-4D02-94B7-1A7E584A6841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"84e027705f33d775e31793728a1178485ed1d15c","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r19.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972677$EE575F1B-C160-43FB-9755-286FAF2024AE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b916b1134c76f25d0e2148a349eea7a44eaea9fb","datavalue":{"value":"Summary: It is shown in this note that with high probability it is enough to destroy all triangles in order to get a cover graph from a random graph \\(G_{n,p}\\) with \\(p\\leq \\kappa\\log n/n\\) for any constant \\(\\kappa<2/3\\). On the other hand, this is not true for somewhat higher densities: If \\(p\\geq \\lambda (\\log n)^3 / (n\\log\\log n)\\) with \\(\\lambda > 1/8\\) then with high probability we need to delete more edges than one from every triangle. Our result has a natural algorithmic interpretation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972677$9BFEAA8A-E135-47B8-B72B-2EE50140A5B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972677$A86973AB-E5E1-4B31-9728-E10764369C8F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e8f7050a2954020f837ec678b27dfec87693acb3","datavalue":{"value":"1431768","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972677$432E1595-4135-4879-A352-65E048D70E61","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"762a112ef0429a3655234c3e246a242461dca9bf","datavalue":{"value":"poset","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972677$3E66CE45-8502-413D-9689-7FAF05125E15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"df6c9c3c01b5b996760d1ae0bf9e2cef46282302","datavalue":{"value":"cover graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972677$09B10925-E044-4AEA-A884-FCB5B5CD389C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972677$326E2C92-920A-4183-8F83-B016719FC3B1","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":"Q1972677$8EF173D4-ED9A-4AF6-A629-4F9E0C3C0F87","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f8a5dc50d15ef68322b8aa9f62531bc51463b37a","datavalue":{"value":"bafkreifkbpdefi7k7gx2sw4ll4ssjmfjkolpfd7vvul4wbq6rawf7jw4ua","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972677$CC9DC661-40FE-4CC1-AAE0-D8A8CE5731A4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df1a621b72342b59dfa6a8fcd44c992166bee848","datavalue":{"value":{"entity-type":"item","numeric-id":4471288,"id":"Q4471288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acca64f3b3a0d06721f6f6aaba63caed6210bf24","datavalue":{"value":{"amount":"+0.795775830745697","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":"Q1972677$CBD41345-68E0-4BF8-A225-2EA441733359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c876cff77c18ac25f11677b1b0c089eadd291a2","datavalue":{"value":{"entity-type":"item","numeric-id":2084667,"id":"Q2084667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2a8363cb84238b0047d677c14c0bebebcdd1ea6","datavalue":{"value":{"amount":"+0.7935353517532349","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":"Q1972677$D2EFD7B1-F324-4BEA-8862-AA2F576E0AD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65f4fb228c160cd1339693a54cfaa6077c20d70b","datavalue":{"value":{"entity-type":"item","numeric-id":2883851,"id":"Q2883851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"81c49c78a551a734d24c6c2c7ace52be506926d3","datavalue":{"value":{"amount":"+0.7722063064575195","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":"Q1972677$0E09258B-58C7-4BE8-904E-0BFC554C9635","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90dfaa753cf5d80b29c24fde252119d9afdff998","datavalue":{"value":{"entity-type":"item","numeric-id":3168450,"id":"Q3168450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ad35caca44aae19dd550a6a68f0058b1cde9ffd","datavalue":{"value":{"amount":"+0.7719435095787048","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":"Q1972677$8A40FBEA-3440-431C-A0D0-3C6FA4F4A4DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"afeb3e67887cb1f5f052f54b4ef22dd805925de9","datavalue":{"value":{"entity-type":"item","numeric-id":1906846,"id":"Q1906846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e71ddaf4bdfef85cf58c057f0baeb56a839299e8","datavalue":{"value":{"amount":"+0.7703635096549988","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":"Q1972677$E3C02A31-27CE-4FD2-A556-84D91BEA75D2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on sparse random graphs and cover graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_sparse_random_graphs_and_cover_graphs"}}}}}