{"entities":{"Q1842142":{"pageid":1852884,"ns":120,"title":"Item:Q1842142","lastrevid":71436498,"modified":"2026-04-13T22:15:16Z","type":"item","id":"Q1842142","labels":{"en":{"language":"en","value":"The Vapnik-Chervonenkis dimension of a random graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 743995"}},"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":"Q1842142$57AFA243-92F0-4FC1-8FC0-52A97DAE4196","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5bd884b8810582bbc5cd0f504bcf7090f1eae3fe","datavalue":{"value":{"text":"The Vapnik-Chervonenkis dimension of a random graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1842142$E775112C-D298-4BCB-8644-5E5ED876E437","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"789b757e4a6c1f87d5647723e27fee7a0a4c9481","datavalue":{"value":"0824.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842142$792C2ED1-4FC8-4407-A1BE-5C8B1B6F6C8F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7fb00bd0a961e01c73d961f9d8e3492493b87eea","datavalue":{"value":"10.1016/0012-365X(94)00187-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842142$0672910A-D88C-4ACF-B15B-D63EA46214DA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae0ca88e1940a7483721540124193708ea9c15bf","datavalue":{"value":{"entity-type":"item","numeric-id":260010,"id":"Q260010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$2A5F3074-F1BB-425C-850C-D52FB0EDC9AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fa1c283669072b9efd9a8b4d0e623734e03b4535","datavalue":{"value":{"entity-type":"item","numeric-id":918998,"id":"Q918998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$606F091D-AE55-4094-835C-FF3889502971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"af07c36948eced54f1dc55426fb5b21ba52f6793","datavalue":{"value":{"entity-type":"item","numeric-id":266694,"id":"Q266694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$9EA70C9E-7E86-4867-84EB-2FC814F24E52","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":"Q1842142$1E80F680-460F-4B29-A31D-8FF6A1922DD5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b2b926a98d60413f2c345d61fda0b910a41b8086","datavalue":{"value":{"time":"+1995-10-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1842142$3B1E5041-ACE0-4156-97B3-F2CC828DE3DB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fae64bcb8d198f631863785ea6c37b5cf5de7f82","datavalue":{"value":"A set \\(D\\) of vertices in a graph \\(G\\) is shattered if for each subset \\(R\\) of \\(D\\) there is a vertex \\(v\\) such that the closed neighbourhood of \\(v\\) intersects \\(D\\) exactly in \\(R\\). The Vapnik-Chervonenkis dimension of \\(G\\) is the maximum size of a shattered set of vertices. For each fixed positive integer \\(d\\), the exact threshold function is given for a random graph \\(G(n, p)\\) to have dimension at least \\(d\\). This turns out to be about \\(n^{- 1/d}\\) for large \\(d\\). The case of \\(d\\) going to \\(\\infty\\) slowly with \\(n\\) is also considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842142$C8A5A93B-CE2F-4264-925B-7636FEB74198","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842142$D928BD6F-9CA5-42B8-83BA-BDB8766AF661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842142$4BB4BE9C-D923-4A5C-8CAD-44188CC59C17","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0f6446ac65f467cb243e3d4ee6d24550025f4325","datavalue":{"value":"743995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1842142$930D604D-9DBF-4FED-9CAC-8ED44C09065C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20f2bd4a4fc8cec853b42b2143124c7d15e194ab","datavalue":{"value":"closed neighbourhood","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842142$60BAD284-13A2-49EC-A0EE-3708CB634F1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"14db18e473ffe9a47f0a11a343dd092fb9e834dc","datavalue":{"value":"Vapnik-Chervonenkis dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842142$D4E95613-169E-4CAA-8908-97F163B28DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cff30fca62ebd21e79df5fc65c8261cbb652a68","datavalue":{"value":"shattered set of vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842142$4104BD0C-1FF5-4727-BF7E-EF47AD80FF45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54d97135ee37d781fff98dec84799a78e3481e9b","datavalue":{"value":"threshold function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842142$8D425DA9-45BA-45F0-ACE0-F1244E1053C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1842142$50B70425-2C2A-4B04-A6CE-E3DD22D2A283","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f6b4f90049fe624e4c23d9606bae564b5e305267","datavalue":{"value":{"entity-type":"item","numeric-id":1227010,"id":"Q1227010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$BF09960D-39A4-4219-A0A5-B9B32EB37E09","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":"Q1842142$8D678342-5B43-4CA6-B4A1-D354D195BCE9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"4799e5a32c687eea79d573479ff8c58240f3cb62","datavalue":{"value":{"entity-type":"item","numeric-id":4004078,"id":"Q4004078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$5200DB1E-00A2-426E-AAD9-82B7A67290E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e1547c029b3c302e23edd15066e5320703a8c3b","datavalue":{"value":{"entity-type":"item","numeric-id":4004178,"id":"Q4004178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$697415A9-0877-4A50-B07A-477DC8FB8899","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d532500415a9d97abe530df2db2357e124dbd89","datavalue":{"value":{"entity-type":"item","numeric-id":1897365,"id":"Q1897365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$C39BAACC-42C9-4D25-8EC8-46DDC78538B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5eceee8709c432551836aeb4f4aa8499755cd2c1","datavalue":{"value":{"entity-type":"item","numeric-id":3474905,"id":"Q3474905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$E6F230D1-8300-4B1E-AC54-C8AC086532F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72bdc200c096a90cb093d01083b69c58672a0aa3","datavalue":{"value":{"entity-type":"item","numeric-id":3682518,"id":"Q3682518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$188FCA84-9047-43EC-8258-40FA26BCFB9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c67cd1fc5f79128afc0722554e08faf0c36cc03","datavalue":{"value":{"entity-type":"item","numeric-id":3726125,"id":"Q3726125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$394CE912-DCAC-4C97-BA89-4A11ED754B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d50f8d7f7fb78d13d9136abf1be65711198cfd6","datavalue":{"value":{"entity-type":"item","numeric-id":1089803,"id":"Q1089803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$B81C3E93-D174-46B2-AB4A-1180A9F3666B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7547c7d15ba0cd72d0a481cd1eeb64380256e66d","datavalue":{"value":{"entity-type":"item","numeric-id":5896394,"id":"Q5896394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$90902CEB-0F7E-43F4-8778-A2D9885074EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4428d340462fbd97ac894b54031481a9db2218c1","datavalue":{"value":{"entity-type":"item","numeric-id":1328754,"id":"Q1328754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$147912E1-04D9-41C3-B856-1AE8768696B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f864b63782981aa340c4711720e26058b856d78","datavalue":{"value":{"entity-type":"item","numeric-id":1171840,"id":"Q1171840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$D46E0BE8-2EF5-48F1-95A5-ED31109D25DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e55670eeffeb14e6ce51166fb8470acff9c12ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5660314,"id":"Q5660314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1842142$BA3975FC-33BD-48ED-8E7B-2C70B865812B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba2b2c5c8283257a84cec5b39f536490a2d62e32","datavalue":{"value":{"entity-type":"item","numeric-id":5297140,"id":"Q5297140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce1edf34b185c5ff76f498ef3ea70a9cd57d7479","datavalue":{"value":{"amount":"+0.861832320690155","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":"Q1842142$2D4A6E3E-60E8-439D-B5F6-5F3A37D9B844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f27ced1bd412152542b4c15bfe72b2316ea81b3","datavalue":{"value":{"entity-type":"item","numeric-id":5387734,"id":"Q5387734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9eacee3d10540cf6a0bf5d033f6f66506cc2036e","datavalue":{"value":{"amount":"+0.7964262962341309","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":"Q1842142$BD403D44-606F-41B4-95A2-132CC519DC93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ed98fb601c7ae65463b7a03fdc4fe1810f571b2","datavalue":{"value":{"entity-type":"item","numeric-id":5744825,"id":"Q5744825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8503bd3140683d693d7b07b19e7b02cbfdaabaa9","datavalue":{"value":{"amount":"+0.7697279453277588","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":"Q1842142$F1F854D4-B1E7-4AAF-A30B-AE11EE9131D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b4837adf87a97011a7935b0cedcae33b1d79c13","datavalue":{"value":{"entity-type":"item","numeric-id":1364472,"id":"Q1364472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"444c4e76686c51a8cf34bc1b45149f4811b3af52","datavalue":{"value":{"amount":"+0.7667500972747803","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":"Q1842142$EB946CE0-A361-487C-8B35-99645D85061B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"309a2fb4e011b1b545830376ccc8db6d1922db89","datavalue":{"value":{"entity-type":"item","numeric-id":470957,"id":"Q470957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20b89354d88ba123ec28a21b260d93eab224b803","datavalue":{"value":{"amount":"+0.764980137348175","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":"Q1842142$47B3E8D8-9298-46D4-85F8-6CEB8137E0C7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Vapnik-Chervonenkis dimension of a random graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_Vapnik-Chervonenkis_dimension_of_a_random_graph"}}}}}