{"entities":{"Q1199484":{"pageid":1210233,"ns":120,"title":"Item:Q1199484","lastrevid":80151299,"modified":"2026-05-06T15:33:14Z","type":"item","id":"Q1199484","labels":{"en":{"language":"en","value":"Matching and covering the vertices of a random graph by copies of a given graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 94356"}},"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":"Q1199484$8022D3DA-4BCB-4550-A557-AEBB4BADCB60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7c3b124aa7d1ddf947a63e8bb26289c58be6c409","datavalue":{"value":{"text":"Matching and covering the vertices of a random graph by copies of a given graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1199484$6B70FC8B-B6AC-484F-AD88-1CC92C0F60AC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b97d59eff920411849a8a6b11f9b4e8dd86580ad","datavalue":{"value":"0774.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199484$E249F8A6-4E92-4DCB-90C9-7F7D3F28DBD0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9985c83ef245381c938359e48d586f27b34260c5","datavalue":{"value":"10.1016/0012-365X(92)90141-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199484$B4F0D1E5-016C-4E58-83F8-18FDEEF0374C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dc0952d447fed38177fb32bd92c2d18011c79ac","datavalue":{"value":{"entity-type":"item","numeric-id":226978,"id":"Q226978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$7A9DFB21-817C-4C40-BBD8-F7E6BC1C3524","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":"Q1199484$6CDCDACD-BC9F-42F9-9FCB-E129E08936D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be1a65edbb43ce1fc59464f99e70afbd93e8e2a0","datavalue":{"value":{"time":"+1993-01-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":"Q1199484$FBC61533-0EF4-41F7-BFB7-444243A2D693","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"df5cdfe263b14d17a8c81a1c4e9bf30aa0bc145a","datavalue":{"value":"We partially answer the question: how slowly must \\(p(n)\\) converge to 0 so that a random graph \\(K(n,p)\\) has property \\(\\text{PM}_ G\\) almost surely, where \\(\\text{PM}_ G\\) means that all \\(n\\) vertices can be covered by vertex-disjoint copies of a fixed graph \\(G\\). For \\(G=K_ 2\\) this is the problem of finding the edge-probability threshold for the existence of a perfect matching solved by P. Erd\u0151s and A. R\u00e9nyi in 1966. For graphs \\(G\\) with minimum degree smaller than \\(m(G)=\\max_{H\\subseteq G}{e(H)\\over v(H)-1}\\), we find that the threshold for \\(\\text{PM}_ G\\) is \\(p=n^{-1/m(G)}\\). A necessary condition for \\(\\text{PM}_ G\\) is the property \\(\\text{COV}_ G\\) that each vertex lies in a copy of \\(G\\). Although for every tree \\(T\\) the thresholds for \\(\\text{PM}_ T\\) and \\(\\text{COV}_ T\\) coincide (see \\textit{T. \u0141uczak} and the author [SIAM J. Discrete Math. 4, 107-120 (1991; Zbl 0766.05078)]), it is not the case for general \\(G\\) and a class of counterexamples will be presented. We also establish a threshold theorem for matching all but \\(o(n)\\) vertices into vertex-disjoint copies of \\(G\\). Most proofs make use of a recent correlation inequality from \\textit{S. Janson}, \\textit{T. \u0141uczak} and the author [Random graphs '87, Proc. 3rd Int. Semin., Poznan/Poland 1987, 73- 87 (1990; Zbl 0733.05073)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199484$8EBF7786-EDBD-42A6-A9BD-F582E7F3CE6A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d6978678d7f7a7f1c64abcdcc131da742ac17558","datavalue":{"value":{"entity-type":"item","numeric-id":226978,"id":"Q226978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$BC61A98A-9FE7-4C25-948C-BB5CCBF4B9E1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199484$16C61913-F404-4F62-9320-EF7BB5D0F2DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199484$1AA03360-41CD-4B70-97E1-4E6DEFCE24E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4789a49650cb21daa850027949ee37dbd991efeb","datavalue":{"value":"94356","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199484$6EDC93FC-E06E-4C23-9682-97C6772F8818","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21d142027bf3153eebb876131ac5297907f4e838","datavalue":{"value":"covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199484$92AB9C97-1352-47C3-AAAA-841AC0B57AE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199484$31F3AD22-7D17-4137-A7C8-B407DAFCA1BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199484$469E3BFA-4726-44BA-A601-48F33A76FD24","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":"Q1199484$CAD59E37-F998-4DA1-827D-45B8228F5E3E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"651a4aa30931dcdb0297c04c91de143fc6eb69e9","datavalue":{"value":{"entity-type":"item","numeric-id":3931444,"id":"Q3931444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$951EAA76-ECFB-4D8D-A5AA-5F13B7D51FD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14984de2c148e2374bb45171db95ee8fe2dc24ac","datavalue":{"value":{"entity-type":"item","numeric-id":1104940,"id":"Q1104940"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$E10497A6-0EF0-4164-BB1F-34F1803B1FEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a634eb18a84b579e5bf40db0e71d8cd092f745c5","datavalue":{"value":{"entity-type":"item","numeric-id":5343356,"id":"Q5343356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$C5AD8088-A4AE-44F6-B840-965A8D3217A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"800c670555a3aa8e0884c256e1569ab5ebd57aec","datavalue":{"value":{"entity-type":"item","numeric-id":5603846,"id":"Q5603846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$94E795C4-EA30-4485-89E9-96124A05FAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e10ce216c10c46aa157e29a5047c60e821e13d90","datavalue":{"value":{"entity-type":"item","numeric-id":3749092,"id":"Q3749092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$51D3BB0E-C56F-4A4E-9575-DE8A2019ACBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6793e177d807b877a3f8d40ddd5473decd8f841","datavalue":{"value":{"entity-type":"item","numeric-id":3360223,"id":"Q3360223"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$4A4F757A-00FC-4FA0-B7D8-1A26180B9334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30f2197a6a09231de2069b98b8861f1751f91919","datavalue":{"value":{"entity-type":"item","numeric-id":3971235,"id":"Q3971235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$4450BB95-82E2-4AA2-A69D-350B865AAFA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b9fdf2c6f44203343ac8a393f9f09f01aa0a03","datavalue":{"value":{"entity-type":"item","numeric-id":3795707,"id":"Q3795707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$971C650E-1ED5-4D0D-BCB3-043176FA2722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4f9d66da2d8b68dc9962826cb46cf9c1973d9d","datavalue":{"value":{"entity-type":"item","numeric-id":1812888,"id":"Q1812888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199484$8E8561E2-DA7A-4D3A-92B3-AF6DC7D30879","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06074747e8d1e52b372ff7d01674149ef29aa080","datavalue":{"value":{"entity-type":"item","numeric-id":4262228,"id":"Q4262228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d5ae6f2011a7f4d99e805462fecc5993d4b2384","datavalue":{"value":{"amount":"+0.8443236947059631","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":"Q1199484$2736E5AC-BF51-4109-9B55-CA89BCF71EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca3bcda53546069e75d31a3366c2c0923b82a7b0","datavalue":{"value":{"entity-type":"item","numeric-id":3956993,"id":"Q3956993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f529166cfb3b3b272ac84eafe1aaabbfb9e6e116","datavalue":{"value":{"amount":"+0.8234696388244629","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":"Q1199484$09DBE400-CA0F-4132-98CD-0A75FF29DE02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4189379d60e184526190b2d8f06037e73935ef89","datavalue":{"value":{"entity-type":"item","numeric-id":3154668,"id":"Q3154668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afbb70eb260f78a84aa7463803db1348bef9657b","datavalue":{"value":{"amount":"+0.8132873773574829","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":"Q1199484$CAB48A04-CC6D-44BE-8CEC-5F226CDAC314","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23937df1656c1db0917cfcc8112d4e4c3d27d2dc","datavalue":{"value":{"entity-type":"item","numeric-id":3720644,"id":"Q3720644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"726f399a7be4e08f937bb516ebed1cd374657703","datavalue":{"value":{"amount":"+0.808463454246521","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":"Q1199484$048C8A66-04C5-4736-9FDD-BCD186A83357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c979c3f06cde716b4955776a1eb3d19970e2f0d4","datavalue":{"value":{"entity-type":"item","numeric-id":4697453,"id":"Q4697453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b7130dd2364977c544e64ecfa506cb86672b18f","datavalue":{"value":{"amount":"+0.8050417900085449","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":"Q1199484$AA74F9EE-CAAC-4910-93DC-E0C2BD53BAD9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Matching and covering the vertices of a random graph by copies of a given graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Matching_and_covering_the_vertices_of_a_random_graph_by_copies_of_a_given_graph"}}}}}