{"entities":{"Q396895":{"pageid":398662,"ns":120,"title":"Item:Q396895","lastrevid":61622250,"modified":"2026-04-11T00:32:33Z","type":"item","id":"Q396895","labels":{"en":{"language":"en","value":"A note on the acquaintance time of random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6330324"}},"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":"Q396895$574CF49A-959A-41E3-8F71-A35AA2F14310","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"50c950e6be364a9a6b63086564c6186375e54463","datavalue":{"value":{"text":"A note on the acquaintance time of random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q396895$BB7E3EF7-3171-47ED-BEB2-0C5D81DF3DB7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4a017084c903e7e1bae7514246de43b0502d93d9","datavalue":{"value":"1295.05210","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396895$CFF10B59-F48C-41D2-8B53-2602E1A95E22","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea6c9ec589ad1c29e012f601e7f530bd1d9cb839","datavalue":{"value":{"entity-type":"item","numeric-id":265088,"id":"Q265088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$C875BE81-A2CD-40E3-9DE2-497C0EDAA032","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1bd2ccad443c7abc989928f6e000b315d9b1786e","datavalue":{"value":{"entity-type":"item","numeric-id":268259,"id":"Q268259"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$41C3FBE3-4890-4D7B-B735-3E5994EBE052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a6197eba997efc9b4d1afb25ce947d80519065cc","datavalue":{"value":{"entity-type":"item","numeric-id":265089,"id":"Q265089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$34520541-20E3-438A-9CA9-73647A13716C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$B5B7DF00-2177-4AEA-A021-C63871F312D2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"014386d1e7349618004d8e2aa9650d7520cb60bd","datavalue":{"value":{"time":"+2014-08-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q396895$12945BDA-86A0-4B71-8990-FF04533C5275","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a83952858b4647e73ae172d70735efc0d7f98dbe","datavalue":{"value":"https://arxiv.org/abs/1305.1675","type":"string"},"datatype":"url"},"type":"statement","id":"Q396895$098978FA-39BE-456A-9FF5-01D8832A36B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"943b66bfffad70fdfc627ba1203c861071845fe9","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p52","type":"string"},"datatype":"url"},"type":"statement","id":"Q396895$E6E9BA94-4497-42B7-AF8D-E8904E2F3C15","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1affed6a82d09b43084693006ded51eba8a1ba7c","datavalue":{"value":"Summary: We prove the conjecture of \\textit{I. Benjamini}, \\textit{I. Shinkar} and \\textit{G. Tsur} [``Acquaintance time of a graph'', Preprint, \\url{arXiv:1302.2787}] on the acquaintance time \\(\\mathcal{AC}(G)\\) of a random graph \\(G \\in G(n,p)\\). It is shown that asymptotically almost surely \\(\\mathcal{AC}(G) = O(\\log n / p)\\) for \\(G \\in G(n,p)\\), provided that \\(pn > (1+\\epsilon) \\log n\\) for some \\(\\epsilon > 0\\) (slightly above the threshold for connectivity). Moreover, we show a matching lower bound for dense random graphs, which also implies that asymptotically almost surely \\(K_n\\) cannot be covered with \\(o(\\log n / p)\\) copies of a random graph \\(G \\in G(n,p)\\), provided that \\(pn > n^{1/2+\\epsilon}\\) and \\(p < 1-\\epsilon\\) for some \\(\\epsilon>0\\). We conclude the paper with a small improvement on the general upper bound showing that for any \\(n\\)-vertex graph \\(G\\), we have \\(\\mathcal{AC}(G) = O(n^2/\\log n )\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q396895$5AD6197C-D457-46A3-B603-30D97879C3B1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396895$53992797-6E6E-4F4F-8EF9-E6F13E38719D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396895$502DBB95-B0B5-43BE-B303-88CE3EC572C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396895$F7F99BF2-A340-405B-99C1-233E04CAB8B9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fd4df946e3671926898b4e09cfef6ca0addbf633","datavalue":{"value":"6330324","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396895$BA4121E2-422E-4638-80CC-C777A60D53CA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q396895$CC3E8D05-7F33-4C06-AAE5-ED63A80F274A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"78503b0250505c0b313c9873472314e3730955b1","datavalue":{"value":"vertex-pursuit games","type":"string"},"datatype":"string"},"type":"statement","id":"Q396895$EBB5B071-E0D1-4141-8AFE-BE31A4B0F5F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d0dec79901ba37a4949ba1879d8bc9fd49080ea3","datavalue":{"value":"acquaintance time","type":"string"},"datatype":"string"},"type":"statement","id":"Q396895$11F8A424-BFCA-4422-A3A3-43C892B4C195","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":"Q396895$F0685993-13F1-4F86-B7DC-1F433403874B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f901a69545f4486415877bb2f48657a19b1f374","datavalue":{"value":{"entity-type":"item","numeric-id":4307057,"id":"Q4307057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$14825877-9CC5-4065-8B14-42CB1D6D29FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9fe5adab5c3a0767ae8cbd90cfe62573420ca67d","datavalue":{"value":{"entity-type":"item","numeric-id":343701,"id":"Q343701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$76779DBD-FFC9-4C70-A448-967513C2F1D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6144a405b8d880120c415f6dbe41a82863fce54","datavalue":{"value":{"entity-type":"item","numeric-id":3192163,"id":"Q3192163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$F881F666-89A0-45B7-8559-C2526B9244CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b07d6ae8072ec0b52d1a52248f558d67752e38c","datavalue":{"value":{"entity-type":"item","numeric-id":2743189,"id":"Q2743189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$DA1A4AF9-6523-47B6-AA39-F929AE54A8FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3941954afbddd9878ea8ac86457e337318b5c62e","datavalue":{"value":{"entity-type":"item","numeric-id":3583313,"id":"Q3583313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$3FA83AFA-C41C-43B1-A200-226DC6BB48D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc47a36e1ac0c95d90450d3d1c8b7166990bef38","datavalue":{"value":{"entity-type":"item","numeric-id":3795460,"id":"Q3795460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$3A2E75C4-815B-4BB3-A279-6424CA6EDB84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28588578bb09af0b4bf0a3281ab6c8d321eb619b","datavalue":{"value":{"entity-type":"item","numeric-id":4519896,"id":"Q4519896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$767C20CC-9D7B-4509-A169-40F41F1AFED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5f1aa9294846cde8376d837af26608b9f41054","datavalue":{"value":{"entity-type":"item","numeric-id":2941641,"id":"Q2941641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$75DF041C-1BD4-4E6D-B103-CF64F2EED2F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f26694317d564ce75313c9fbcae4701f48aa4b05","datavalue":{"value":{"entity-type":"item","numeric-id":2346592,"id":"Q2346592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$C33A438E-7E62-4757-8DC8-1435D590ADBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4037b5bf6c11265800be675dd5428709bac6312d","datavalue":{"value":{"entity-type":"item","numeric-id":418891,"id":"Q418891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q396895$532BCD33-6173-46CA-B95B-FF225594DAE9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"26c46de83bdfadf75f34148bd28bd08ac17731fb","datavalue":{"value":"bafkreie5y5aumy5s5te5wle4d52gmewihswremb72suir3b4b2v2zqmdwq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q396895$394CC2F9-41D2-4858-92F6-52FEA75ABD37","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ee071041bc4cc6f7d3a5d027a403beca3c61ce4","datavalue":{"value":{"entity-type":"item","numeric-id":2801332,"id":"Q2801332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8ce478b718d7846185f458e18cd01c22359887d","datavalue":{"value":{"amount":"+0.9153615236282348","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":"Q396895$B7E2FF3F-7BFE-4384-A509-3F555035295D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dc046d0c69f2ecc1833f436567ac25c66f3a878","datavalue":{"value":{"entity-type":"item","numeric-id":2346592,"id":"Q2346592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7ef7a016ea74b2928f0eb6d0775117a26fbf4240","datavalue":{"value":{"amount":"+0.848235547542572","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":"Q396895$0E6431E2-D0ED-4B28-A8B2-AB994F4A24EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"925cc60b61035751d1453d15bbedf3f0cc72a5d5","datavalue":{"value":{"entity-type":"item","numeric-id":343701,"id":"Q343701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2004ccd10286c88f125f17d634c3915218c239c2","datavalue":{"value":{"amount":"+0.8436515927314758","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":"Q396895$A39BCA24-29E1-45AB-B9E4-2FC4C3EC4E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6019a215ac326dcb0feec18315382ddb0427f6c1","datavalue":{"value":{"entity-type":"item","numeric-id":3192163,"id":"Q3192163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73d6e15eae3c11af7375de079c139a668d745cce","datavalue":{"value":{"amount":"+0.8114518523216248","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":"Q396895$5E8A059A-C4D2-40FF-A56D-82240CEFAD88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df1a621b72342b59dfa6a8fcd44c992166bee848","datavalue":{"value":{"entity-type":"item","numeric-id":4471288,"id":"Q4471288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"330ce5dd1719057bf9b47fa579d91b2a7258acd4","datavalue":{"value":{"amount":"+0.751690149307251","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":"Q396895$BA95019C-7B9C-4A62-9BE6-19F1A73E98F1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the acquaintance time of random graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_acquaintance_time_of_random_graphs"}}}}}