{"entities":{"Q1612288":{"pageid":1623028,"ns":120,"title":"Item:Q1612288","lastrevid":72339873,"modified":"2026-04-14T04:14:50Z","type":"item","id":"Q1612288","labels":{"en":{"language":"en","value":"Sparse universal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1787592"}},"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":"Q1612288$11657EA4-A51D-452A-8280-4096BF6C44ED","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7af3608685258558460dd54ccc31b016ffde8fa1","datavalue":{"value":{"text":"Sparse universal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1612288$1CBC7E11-8F16-4673-B287-563981A435CA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fe92f2653c4899379cf84ffbcf8bcc6685a1ab62","datavalue":{"value":"0997.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612288$E72750C7-5E20-41D5-A901-3585361552FA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d1566fa244f8d8c508dac77fc421d57dcfa73f5","datavalue":{"value":"10.1016/S0377-0427(01)00455-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612288$DC6A283B-F7C2-4902-8560-7A884AA85877","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c61d0b4df374523ec5b59f8a7d6c81266878fe30","datavalue":{"value":{"entity-type":"item","numeric-id":178698,"id":"Q178698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$76594DCE-5792-408C-9394-4830300200DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3aa2374e85de5ef7d92bbbf6b0fb5e7c7c081b66","datavalue":{"value":{"entity-type":"item","numeric-id":850072,"id":"Q850072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$1886E60B-D5AD-4CAA-867C-62DA450845AD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9291c21615d62497aa2bb6404791ba4d7844695d","datavalue":{"value":{"entity-type":"item","numeric-id":61355,"id":"Q61355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$042F1082-CB95-4193-BFCD-8FD7131FA5CB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"85457954b4986af9d8102fe1df325031037075bd","datavalue":{"value":{"time":"+2002-08-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1612288$9AEEBDA1-9066-48F5-9980-9C49A4191E3D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2f681f63f4cc4117a80fd24b9399a4a0613c4e61","datavalue":{"value":"Improving a recent result of Alon et al., Alon and Asodi give an explicit construction of a graph of order \\(n\\) having \\(O(n^{2-\\varepsilon})\\) edges, for \\(\\varepsilon=0.133\\dots \\), that is universal for the graphs of order \\(n\\) and maximum degree three, i.e. it contains all such graphs as subgraphs. As a second main result the authors prove that the minimum number of edges in a graph that is universal for the graphs having at most \\(n\\) edges and no isolated vertices is \\(\\Theta ( \\frac{n^2}{\\log^2 n})\\) which proves that a corresponding lower bound due to Babai et al. is essentially best-possible. The proofs strongly rely on probabilistic methods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612288$7F4083AD-6C79-4DB7-B7FF-EE0A2359ED46","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c21cb54e7c2c469712a9307e52fa5ab7414ba5da","datavalue":{"value":{"entity-type":"item","numeric-id":186196,"id":"Q186196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$607611C8-0653-41E3-AB25-F3AF8DD2862E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612288$92BB20C2-BE85-405C-B408-E513694C6981","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e040333fe72965b6b40b6dfdf7be79dd19481ee1","datavalue":{"value":"1787592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1612288$6522940D-3F13-4F46-9AA4-29FFC41FCF36","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e739df749d6c867acd2763fc312bf2853a82972b","datavalue":{"value":"universal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1612288$0A3C5842-2409-4991-938D-07F5B42050E1","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":"Q1612288$0166649A-D21B-471C-A603-9F76C998E3AC","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":"Q1612288$F1F0667D-7846-49DF-B6F4-2B38ECAB2BEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49b0527b2dbc74fe5624d65b15c19bef0a8fa837","datavalue":{"value":{"entity-type":"item","numeric-id":3958492,"id":"Q3958492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$2D50C0D2-38A4-48E4-BEAC-F8800684226B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b3a2e4c716ab825aeba6702363f0e901a216767","datavalue":{"value":{"entity-type":"item","numeric-id":3828026,"id":"Q3828026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$A838E0A2-14F2-4728-BD28-C0CB82564602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27fb952c73266a9a8d0cf9ad69484104871cd714","datavalue":{"value":{"entity-type":"item","numeric-id":4252284,"id":"Q4252284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$A0101922-2760-4FAC-B813-2259DCDEB3CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"959a035785b8bb151ea48bb5de13d71b12af84e9","datavalue":{"value":{"entity-type":"item","numeric-id":2819605,"id":"Q2819605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$1ECB3069-C2EB-427A-8D00-02502E426636","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"64952174b7e458f68d238f7503791acd723ac33c","datavalue":{"value":{"entity-type":"item","numeric-id":5620621,"id":"Q5620621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1612288$55413CB2-4A36-49E5-860C-3A7B16EF0A66","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f2372fdda3f84f03e96efabd87ac08f3d8b3623","datavalue":{"value":{"entity-type":"item","numeric-id":5433254,"id":"Q5433254"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47c2e60c8a753a63b8f8addabf336757d2b3e453","datavalue":{"value":{"amount":"+0.885924756526947","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":"Q1612288$424205DE-A1F2-4F97-9277-3BCFF48B3D43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93323b75f3a0c09731dc91ab1dbd574dda7cea4a","datavalue":{"value":{"entity-type":"item","numeric-id":3061179,"id":"Q3061179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1cbb52ee9944983308324ad43394643765b25b0f","datavalue":{"value":{"amount":"+0.8703834414482117","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":"Q1612288$F9DAC962-D31E-4435-BF32-9F35FEC443A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e387ac10fb4447281a68835bebabd7f68f393cb9","datavalue":{"value":{"entity-type":"item","numeric-id":4780792,"id":"Q4780792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1510b1aaed168a70aca4a3e53344d035c746980","datavalue":{"value":{"amount":"+0.8693087100982666","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":"Q1612288$CBA718BB-60C0-4EAC-8EA7-4705C8A91A2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e047744bb64c2926c0dc33bc19d74f7d2e7b54a","datavalue":{"value":{"entity-type":"item","numeric-id":633606,"id":"Q633606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2a62461852aff4da59eb38461dc4a8bbee3a95f","datavalue":{"value":{"amount":"+0.8654341101646423","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":"Q1612288$E5A0292F-E61C-4752-B189-8382744412FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a763e1f6273fd14ff400333fc613cfe95829e9b9","datavalue":{"value":{"entity-type":"item","numeric-id":2819605,"id":"Q2819605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"940d05c4406a5fd5381cdcdcfe77e9e01b252661","datavalue":{"value":{"amount":"+0.8343878984451294","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":"Q1612288$17CB79DB-FCF4-4173-AE6A-5E76AA660FB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Sparse universal graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Sparse_universal_graphs"}}}}}