{"entities":{"Q5958808":{"pageid":8135610,"ns":120,"title":"Item:Q5958808","lastrevid":47756011,"modified":"2026-01-02T14:57:07Z","type":"item","id":"Q5958808","labels":{"en":{"language":"en","value":"Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715853"}},"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":"Q5958808$F511E600-8C7F-4539-B3E8-1BD8EA3ECCF8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42c71b69992d8dbe335a37aac4d18e432bdd9343","datavalue":{"value":{"text":"Statistical mechanics perspective on the phase transition in vertex covering of finite-connectivity random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5958808$1727680F-B151-4E75-BC14-26A902666834","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e266285b6c0b23860848c3c978c63aecffdfbfb4","datavalue":{"value":"1026.82014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$DBFF073F-7515-490B-9044-F305257D2F92","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1181d1c8a16302530d16438e9351571c9046e000","datavalue":{"value":"10.1016/S0304-3975(01)00163-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$E9814CA7-CD17-4A9B-A9FA-5C8863D360F6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90591ec197753ce8793e07e9afdc15aa9a7dd23d","datavalue":{"value":{"entity-type":"item","numeric-id":486733,"id":"Q486733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$DBDA677C-45D6-4CE6-9C19-789DD4E1EFEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4b5d843858bc82b7efc080fbf040888d83db561c","datavalue":{"value":{"entity-type":"item","numeric-id":709758,"id":"Q709758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$935704FD-7501-4F9F-9A6B-E752B156E2FC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$F65361AD-7F66-4F79-942E-4E9BD8E18659","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5958808$5D0F543B-80CF-41CC-8580-939A9C095D89","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6324872526a3f05465366fc63a9ca8b4ef2c149d","datavalue":{"value":"The vertex-cover problem is studied for random graphs \\(G_{N,cN}\\) having \\(N\\) vertices and \\(cN\\) edges. Exact numerical results are obtained by a branch-and-bound algorithm. It is found that a transition in the coverability at a \\(c\\)-dependent threshold \\(x=x_{c}(c)\\) appears, where \\(xN\\) is the cardinality of the vertex cover. This transition coincides with a sharp peak of the typical numerical effort, which is needed to decide whether there exists a cover with \\(xN\\) vertices or not. For small edge concentrations \\(c\\ll 0.5\\), a cluster expansion is performed, giving very accurate results in this regime. These results are extended using methods developed in statistical physics. The so-called annealed approximation reproduces a rigorous bound on \\(x_{c}(c)\\) which was known previously. The main part of the paper contains an application of the replica method. Within the replica symmetric ansatz the threshold \\(x_{c}(c)\\) and various statistical properties of minimal vertex covers can be calculated. For \\(c<e/2\\) the results show an excellent agreement with the numerical findings. At average vertex degree \\(2c=e,\\) an instability of the simple replica symmetric solution occurs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958808$E5AE2708-7AE6-44D3-A00A-07266617A2F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1605bc5dea0dca4de0a503b8718abc9a678a6472","datavalue":{"value":"82B41","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$C0F7AC71-BFD1-4E29-A6D7-57BE361F0238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$4D57B49B-C4A0-48CD-93FD-87C24906F506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4de4c832c60705655c31fdc221b680cd6d52ed72","datavalue":{"value":"82-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$AD2CEF6F-353A-48D8-90C1-3285FC49207C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"955a6ac68db8c67c1772255c707ed5eb1d2bad2b","datavalue":{"value":"90C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$EFB43CD3-09F9-4474-9A7B-358B93EAEA44","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2c47b43891102acb0f0c5f7fe3026713bd728a58","datavalue":{"value":"1715853","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$5A61D4E5-81D2-4E56-8CC2-22D0ADE55FA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a55697f11ed6943355f61f33b5c3a878590a2f90","datavalue":{"value":"vertex-cover problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958808$FB8842B3-9EC3-4DAA-B379-F960009D2D89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958808$FFE62327-AB34-45C9-9C96-9B99137578C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf54e2d199641bd16db964256732a9040fd52c2f","datavalue":{"value":"branch-and-bound algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958808$AF4B0F80-667B-4ABA-8452-0EF9CE7AAF43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3630d9097e172f7863a39f839195e76dd8e14ed5","datavalue":{"value":"annealed approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958808$EF04B905-B6FA-48D4-8B98-CCC42207C162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5639b06e00d9ee118b27248e06525ec1b6ed7b46","datavalue":{"value":"replica method","type":"string"},"datatype":"string"},"type":"statement","id":"Q5958808$269B932D-FFCA-4BCB-9A7C-6D8B171FEA1A","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c0cba7e0ab2c7aef38abd153b2270fa5d0f43436","datavalue":{"value":"Q58001608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5958808$2F85596E-A52F-4F03-95CE-152F0617EE8C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8970d53f5fc5de8a7599b5d4b50f76cbd183814b","datavalue":{"value":{"entity-type":"item","numeric-id":13265,"id":"Q13265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$F438077F-5D62-43A0-88E3-469B103B0265","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":"Q5958808$7CD66D4E-DF77-4798-896A-7314CF69F1E8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f11d905c5d301eb7550191ae68eb684c9598dcb8","datavalue":{"value":{"entity-type":"item","numeric-id":4111621,"id":"Q4111621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$FF10D09D-9A7C-4208-AC05-D38ACE61CB27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edd227013a96dd65d0289b90d93ff4bba0dd80ab","datavalue":{"value":{"entity-type":"item","numeric-id":3286850,"id":"Q3286850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$C4C44991-5696-4F96-92A0-D194FFA279B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95d31d569f0092e34aba63ab212c6f82ed91ba93","datavalue":{"value":{"entity-type":"item","numeric-id":923109,"id":"Q923109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$D31A4784-B98D-410E-97AC-05E25BEBB44C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$F13D5426-64E6-4672-896C-9EE0A7C997FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d87723c489ed79e2c95619504697d8f67469d5db","datavalue":{"value":{"entity-type":"item","numeric-id":3701457,"id":"Q3701457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$F442B40D-9C7D-406B-86EB-45C729BA5046","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dfe2940b4e597e5086b3157aa4af62a7067d29dc","datavalue":{"value":{"entity-type":"item","numeric-id":1584341,"id":"Q1584341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$349A74EF-928A-46B5-AB3D-9844D0FF83EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27650fb33280eb15aa99fe7b839da09c174ca0e3","datavalue":{"value":{"entity-type":"item","numeric-id":5519733,"id":"Q5519733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$B022B93D-FF9B-46EA-B506-982779661C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de431ae5e1e6d0bce50265c8838d96541539c883","datavalue":{"value":{"entity-type":"item","numeric-id":4702188,"id":"Q4702188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$E12C54F9-AEAC-47F4-ACB0-578B29A0489A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0a7f8f3f6afc956c0f373f0c214ba40715ce59","datavalue":{"value":{"entity-type":"item","numeric-id":4492521,"id":"Q4492521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$5BADFC83-2E48-40B9-8A22-693788EC6B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2499f070fd0dfae5aaadf25b62eee8f8ef1d7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4237477,"id":"Q4237477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$F02DD5CA-0F63-4AF8-A633-85160DB683F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51c82b79d7c145be88232c9ca5c1f2cb2632530c","datavalue":{"value":{"entity-type":"item","numeric-id":4486390,"id":"Q4486390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$2255C7B0-D144-47C6-93C7-78D407D58789","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1075903201a7b5a96eb9e60933d437eac5400eb1","datavalue":{"value":{"entity-type":"item","numeric-id":5354392,"id":"Q5354392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$1E0ED283-1CED-46C7-9E39-04192968E880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1eafdbadab6556c3d155308f91ffabae30954f8","datavalue":{"value":{"entity-type":"item","numeric-id":2674173,"id":"Q2674173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$EA1017F3-CFE8-4245-B8ED-EA86F9407E2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1dc8a1faedec1647ff5e9aefae185cf306f2bc5","datavalue":{"value":{"entity-type":"item","numeric-id":4133117,"id":"Q4133117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5958808$5A50913A-CE89-450B-B41E-C4A143D789FD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98f6499340030b4d36d8bce48ea097cac5266cfb","datavalue":{"value":{"entity-type":"item","numeric-id":5696397,"id":"Q5696397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1e2285c6a088f53f2ebe8ff577c60e7f5c80b8e","datavalue":{"value":{"amount":"+0.8728858232498169","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":"Q5958808$D69EF98D-EC88-4DD9-9D94-5B0F33C23785","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e4dda7977f236b733b56b6ae2874409544a3c45","datavalue":{"value":{"entity-type":"item","numeric-id":5456532,"id":"Q5456532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ebe06e7824abd3257bc64a7dedd07d52e026e5d9","datavalue":{"value":{"amount":"+0.8186461329460144","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":"Q5958808$C407C3F2-C849-4A8D-8AA1-44CCDD7BD94D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7ef9cdf612bb21a895deba123755e977b71faef","datavalue":{"value":{"entity-type":"item","numeric-id":3624680,"id":"Q3624680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"419fcfadac78b21458c5516c8fda35f604118098","datavalue":{"value":{"amount":"+0.8036274909973145","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":"Q5958808$646A956A-1D87-48FF-A8CC-5F068147EC0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92ce35b07f52f3638d0b146bf5254f27095dc2cc","datavalue":{"value":{"entity-type":"item","numeric-id":709759,"id":"Q709759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4adf962bad6c958645c22633d0822302d0f7d724","datavalue":{"value":{"amount":"+0.7896268367767334","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":"Q5958808$31F90182-C802-4478-AA5A-B5D831AFE759","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d61f770f2f48a81a0fb96d65cc09298aec540a1f","datavalue":{"value":{"entity-type":"item","numeric-id":658477,"id":"Q658477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"569954c2446218246c922300c87b39a9cee92af5","datavalue":{"value":{"amount":"+0.7399376034736633","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":"Q5958808$CB7DB2EE-53DA-4D3F-A8E6-C466BE266CE3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5958808","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5958808"}}}}}