{"entities":{"Q580382":{"pageid":582149,"ns":120,"title":"Item:Q580382","lastrevid":62922354,"modified":"2026-04-11T09:00:33Z","type":"item","id":"Q580382","labels":{"en":{"language":"en","value":"Random graphs and covering graphs of posets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4016965"}},"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":"Q580382$9B6C03E2-F616-4014-9A48-9FF7D85340BD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ac1d388eced661e83c9cb6b6070d7c4a4a841682","datavalue":{"value":{"text":"Random graphs and covering graphs of posets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q580382$B90D2856-69A0-4A1E-B6B3-E500B2593C1D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"83ce78b1ed4a19fcc72b39e8638d1d4b2ab63fac","datavalue":{"value":"0626.06005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$586EE016-9867-488D-987C-DA0D49E321F5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8ff0166f6aa8c8eee903fa37b9bc41751e4ea4e6","datavalue":{"value":"10.1007/BF00400288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$B125068A-C8E1-40A1-A821-D6161327D555","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a14bac90927db699ac4af297f1d406f2762c11d","datavalue":{"value":{"entity-type":"item","numeric-id":168581,"id":"Q168581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$767B4731-3838-426F-9F8B-438F127BB10A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9380c4124a5ef272e2152da1b5d415130e3e64f8","datavalue":{"value":{"entity-type":"item","numeric-id":175596,"id":"Q175596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$C355F857-DF64-40AB-B2EC-66AAAE564F46","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":"Q580382$C52A42CF-A34F-4619-85D8-41DA08F6937B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e2599ed8061d57585b4363072a1afceea2452436","datavalue":{"value":{"entity-type":"item","numeric-id":172073,"id":"Q172073"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$29CA93CF-61E0-4E8A-8C1B-E36DCE5B7513","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q580382$319FEA59-C464-483C-A5C2-8AF7A21B01B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2416bc686f098eb238e26352d716a81dcb2bccf4","datavalue":{"value":"As some of the main practitioners of the associated art demonstrate once again in this very interesting paper, for finite graphs and posets the essential unmanageability of search-and-exhibit methods can often be circumvented by the introduction of probability and statistical tools via the construction of special random-variables and analysis of their associated densities to retrieve desired conclusions. Thus if a probability can be estimated to be positive then this often means that an existence result has been obtained. Thus, using the main result of the paper the authors show somewhat readily that (Ne\u0161et\u0159il and R\u00f6dl): for any integer g, there is a graph G of girth g which is not a covering graph.    Given a (finite) graph G, c(G) is the minimum number of edges which must be deleted in order to make G into a covering graph of some poset P ((x,y) is an edge of G if and only if x covers y or y covers x in P). If \\(G_ p=G_{p,n}\\) is obtained by joining pairs of n distinguishable vertices independently, each pair joined with probability \\(p=p(n)\\) then a probability space is constructed in which G's have measures as \\(G_{p,n}'s\\). The main theorem of the paper is the following best possible result: suppose \\(p=n^{-1+\\eta (n)}\\), where \\(0<\\eta_ 0\\leq \\eta (n)\\leq 1\\) for some \\(\\eta\\). Then there is a constant \\(K_ 0=K_ 0(\\eta_ 0)\\) such that for almost every \\(G_ p\\), \\(c(G_ p)\\geq K_ 0n^{1+\\eta (n)}=K_ 0pn^ 2\\). Here the ``almost every'' terminology means that \\(\\lim_{n\\to \\infty}\\Pr \\{c(G_{n,p})\\geq K_ on^{1+\\eta (n)}\\}=1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$0301263F-5292-4509-A54A-AFD996BD8964","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$6AE8E632-BF7C-40EA-96D6-C742D8C6BAAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$FC96A5F7-FC92-4B0A-BB84-8196D0D76397","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4b7275e0d4b526075acce84a242d8537e929bb2d","datavalue":{"value":"60C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$66D0619F-6958-4109-BCAE-2E9377C869B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$FDF09691-0829-4BCB-A45A-2E74CC66617C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0ece987abe6c18f5b0bd95ad0d0f7a30478f12ae","datavalue":{"value":"4016965","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$4E68126F-FCF8-4170-975D-D680E8C9E30D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d729c402ba86b0653b3a28e225fa5726cab5467","datavalue":{"value":"finite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$48F465CE-E37F-4F02-AB7B-5966E12E7A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55ed4e02075ed4e4b1b42997cccad7cede0fb5bc","datavalue":{"value":"posets","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$6A2C5077-E300-4429-AF7E-10A38679C2A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aba1c0bab80977791cec268f5c4e1b88cc70d9cd","datavalue":{"value":"random-variables","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$A7CB2C89-8C4D-4A6C-B526-37E4F9302483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9d25444a154e506d2caf86a4e52f5686b70e491","datavalue":{"value":"densities","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$749A39CA-DC4A-4D7B-AA0B-759146F4C0E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73b4c65f1932723e758d611f0e45f29f11ae5669","datavalue":{"value":"probability","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$1F3A0A71-0B41-4563-9524-A037E5DF1554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$05852C49-76FE-447F-B0F3-89D7E6827AB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0dd8f6863138771bbebc289bdc9ec5e11396e78a","datavalue":{"value":"covering graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q580382$539636CB-0421-4300-BBC7-54EAC67882D1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b626688718ca3d61fce8479b1c17fa40d92d8dda","datavalue":{"value":{"entity-type":"item","numeric-id":233347,"id":"Q233347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$8F10114C-1B34-41C8-954D-084A4F4EFAF2","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":"Q580382$F0E7D4BF-D80A-4BBB-83DE-3853CD1779CB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9602222e5a47f4cdffba25fcbf24545caa12e3c4","datavalue":{"value":{"entity-type":"item","numeric-id":1245243,"id":"Q1245243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$2BB6FA27-EA0F-4DC5-8A68-47BCCD06CF4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$8616C9AB-BB77-43B1-A1A2-4FB728A4BF8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a3e770ee75376f4cc53272c6f2ca696e7e9ea87","datavalue":{"value":{"entity-type":"item","numeric-id":4182520,"id":"Q4182520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q580382$B17C9611-CD9D-4677-90EF-8E98F46EFD52","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d83935982b6c7572e158891d6343388984792983","datavalue":{"value":"https://doi.org/10.1007/bf00400288","type":"string"},"datatype":"url"},"type":"statement","id":"Q580382$1B51D7B3-2863-4ABA-B196-E371D5EA7F21","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5a589a74130e85fc0eca13c283798edd9683f356","datavalue":{"value":"W1969653383","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q580382$92AB2859-746F-4CC1-B3D2-189E0C28EB12","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e9e9acbbcf81950a961f62089aa2ec0d9b19641","datavalue":{"value":{"entity-type":"item","numeric-id":700369,"id":"Q700369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5175b505c86a623ce3d5783cd15ef37801bf8766","datavalue":{"value":{"amount":"+0.8278435468673706","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":"Q580382$5378C9F1-0399-4C08-8894-C9BABDA472A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"464560f9761402c08323b4e21e977f4a2be9f51e","datavalue":{"value":{"entity-type":"item","numeric-id":5696365,"id":"Q5696365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99ff49c30b7ae52f764753bd0684c5aa78fb538c","datavalue":{"value":{"amount":"+0.7991546988487244","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":"Q580382$659F5C27-94E7-46B5-9E12-F9D57101AE2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dbbeed64653c9aac17b6253baf23e3d930791431","datavalue":{"value":{"entity-type":"item","numeric-id":1199484,"id":"Q1199484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe6306332ea2e3fb12e4df8b8e58b9bb26b00ef9","datavalue":{"value":{"amount":"+0.784371018409729","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":"Q580382$92F7E347-454F-41A0-8E1C-FFAB57CC11FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d98af2e8cbc521849f7edd27e740f33aff4ea02c","datavalue":{"value":{"entity-type":"item","numeric-id":1092067,"id":"Q1092067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d5c9c00801f13b266a2233e420db6068ece309b","datavalue":{"value":{"amount":"+0.7842158079147339","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":"Q580382$0976C061-7947-4E8E-B4BF-B964C87277B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6c82f8b0a0b410d83ce843118515d467fd3b633","datavalue":{"value":{"entity-type":"item","numeric-id":2367438,"id":"Q2367438"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00c87fe686eb64ab00006891fcfb4be181e1302e","datavalue":{"value":{"amount":"+0.7819979786872864","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":"Q580382$7B5D53BE-D508-48C6-BC4D-8C386E4D1CB6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Random graphs and covering graphs of posets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Random_graphs_and_covering_graphs_of_posets"}}}}}