{"entities":{"Q1753122":{"pageid":1763864,"ns":120,"title":"Item:Q1753122","lastrevid":68882646,"modified":"2026-04-13T02:52:18Z","type":"item","id":"Q1753122","labels":{"en":{"language":"en","value":"Paths and cycles in random subgraphs of graphs with large minimum degree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6873190"}},"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":"Q1753122$3503ADCA-C193-4AA5-B455-B94CBA8F4C3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25f2d00d912e7ae5152bd9a9707bd7ed4435da83","datavalue":{"value":{"text":"Paths and cycles in random subgraphs of graphs with large minimum degree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1753122$DEEBB87B-DAD1-493E-98A2-0484EB5BC36F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0f0f0677fe39860b3373bb3f390e14bdd5c0130","datavalue":{"value":"1391.05143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753122$A72FCC9D-0CEC-40BA-BF2F-5115D497B306","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"609d64fe2f8154aee9cc5dbfd4afdb047f47b66b","datavalue":{"value":{"entity-type":"item","numeric-id":1741517,"id":"Q1741517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$EDD16BE5-4950-44C4-8EFA-48457CE835A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"23ba6a7606cf6ed47193e89184086ddabd0de909","datavalue":{"value":{"entity-type":"item","numeric-id":251504,"id":"Q251504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$A63C6992-F9C7-488A-9529-0CD0935D4B5C","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":"Q1753122$389B3140-F0BE-49AA-B355-BC75AE11954F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"889be0f8e7c5593fd9d724762872dd9608a4e49c","datavalue":{"value":{"time":"+2018-05-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1753122$85B6CD5B-494B-460A-9D1A-F4B781C3F11A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fd9827260db19b493fa9a8a4ec30324e8008cc30","datavalue":{"value":"https://arxiv.org/abs/1510.09166","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753122$226CC1FC-D778-413C-9385-06F0155CC460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d0af1f504d4b2e0e4c6c28e4d72eca070a914dca","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p31","type":"string"},"datatype":"url"},"type":"statement","id":"Q1753122$47BF5E73-D5EF-444C-A454-EED20700C6A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dda5b4930394b41cd9c62a0254f3e87d7edff12b","datavalue":{"value":"Summary: For a graph \\(G\\) and \\(p\\in [0,1]\\), let \\(G_p\\) arise from \\(G\\) by deleting every edge mutually independently with probability \\(1-p\\). The random graph model \\((K_n)_p\\) is certainly the most investigated random graph model and also known as the \\(G(n,p)\\)-model. We show that several results concerning the length of the longest path/cycle naturally translate to \\(G_p\\) if \\(G\\) is an arbitrary graph of minimum degree at least \\(n-1\\).  For a constant \\(c>0\\) and \\(p=\\frac{c}{n}\\), we show that asymptotically almost surely the length of the longest path in \\(G_p\\) is at least \\((1-(1+\\epsilon(c))ce^{-c})n\\) for some function \\(\\epsilon(c)\\rightarrow 0\\) as \\(c\\rightarrow \\infty\\), and the length of the longest cycle is a least \\((1-O(c^{- \\frac{1}{5}}))n\\). The first result is asymptotically best-possible. This extends several known results on the length of the longest path/cycle of a random graph in the \\(G(n,p)\\)-model to the random graph model \\(G_p\\) where \\(G\\) is a graph of minimum degree at least \\(n-1\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753122$9F150938-7753-4D2E-A90A-AC2B5F4D70CA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753122$C4F3690A-86D6-4A4D-9DED-DBB943DD13BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753122$6316889A-AD0C-4A3C-9F6F-91C51ACD15F2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"913996d5bbd93aad156c3ded5c6ddd998306f80d","datavalue":{"value":"6873190","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753122$3CE6041B-CB60-476F-9817-02E9AAE25A5D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753122$99170CF1-690A-4929-AEC1-856CAE0F3B2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753122$BB98553F-E44C-43FD-B3D9-A7C8BAF6798E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2dcf267cbc3e04fdcfc3d3761f7ad8ebdabe8c51","datavalue":{"value":"cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753122$4F2335C0-568B-4EE7-9350-F8B459D9768A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e865dcf04feef79efcf163ac054d2ac37b7305b","datavalue":{"value":"paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753122$43C60DAA-271C-4459-B814-D07F10A19070","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fae8dc69695ed62681f89d7d9eea2d8a16b8684","datavalue":{"value":"minimum degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1753122$AEF1E5B9-6FCC-434D-9F0B-8F36045D5D7E","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":"Q1753122$6F4B1437-2BCA-42B2-9FA8-28322A95389C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"22c9192954ccc96b2ee3267d39b3b42b3eff67b4","datavalue":{"value":{"entity-type":"item","numeric-id":1166543,"id":"Q1166543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$F84708B5-C53B-418B-82AE-B97CA10C9502","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bbaef82e8eb92dc4676d651d32794ea23b80ec1","datavalue":{"value":{"entity-type":"item","numeric-id":2798999,"id":"Q2798999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$2093758D-1BB2-43AC-B521-F256D0B7A0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d035933938e805a75565dd399f688395cd7d72","datavalue":{"value":{"entity-type":"item","numeric-id":594110,"id":"Q594110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$BFD5EBC3-6E92-4D2D-A1D0-5B1B533974BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"785517565cd1a5d13c79229e22ed187cf7dccb05","datavalue":{"value":{"entity-type":"item","numeric-id":3691698,"id":"Q3691698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$CB5C5BD6-0ABF-4C55-BFFB-E371D01B991A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0eeff2192304a70455454c7d5bd957bf9891a8e2","datavalue":{"value":{"entity-type":"item","numeric-id":3887496,"id":"Q3887496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$80149B13-6748-4FBC-9A09-1FDB71256989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5df85ee70a104904416be57c740c463f19ac9791","datavalue":{"value":{"entity-type":"item","numeric-id":1092926,"id":"Q1092926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$25917558-8967-44F3-A130-35401E2BC559","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2024036f4e636b4cd58a74af80e43bc352b923","datavalue":{"value":{"entity-type":"item","numeric-id":5366938,"id":"Q5366938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$670BF29D-C842-4938-AB31-529C8AB56CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d093b7102af7f34569240e4906d3598a4a01f5cc","datavalue":{"value":{"entity-type":"item","numeric-id":4982618,"id":"Q4982618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$8F684BFB-8361-4556-B80E-3C87A9066A92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71d893a7870006d6818541a3379544cb5add46ac","datavalue":{"value":{"entity-type":"item","numeric-id":2852544,"id":"Q2852544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$8C44EAF6-9BFD-400A-8E83-E568698ABB78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7867e6df3c745db66b8afb4a381925c0db0b4635","datavalue":{"value":{"entity-type":"item","numeric-id":5256392,"id":"Q5256392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1753122$794C7A31-9BFB-46EC-B592-D54A71B7D62F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"78948806640c742fb719a6851aa27e2f28fccfaa","datavalue":{"value":"bafkreidwbf2wgaatoggypzkzvykz6toh46khwq5o5yzdbt3rfcwr32g2eu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1753122$82DCBAFA-689B-47D2-9BF6-EBA8AF0D89A1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c30a535bb104b741eb1a03e8c3ec2acc4f6f6f32","datavalue":{"value":{"entity-type":"item","numeric-id":4982618,"id":"Q4982618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6673001b348bd22530517454a922b48e466758b2","datavalue":{"value":{"amount":"+0.9397632479667664","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":"Q1753122$A4D85740-F979-49DF-B122-D97E4475F5A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75ae86def3c5f8f51bde2ab60af748d79c7adb1","datavalue":{"value":{"entity-type":"item","numeric-id":1998764,"id":"Q1998764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e9f5af7a213b6c2b2b0cbde2576139b5ebdeeb3","datavalue":{"value":{"amount":"+0.9266179800033568","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":"Q1753122$52E6CDF9-351E-4F9E-A28E-8D2FF8E4D670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"00999b7aea2f58a40ead2e1bb33b904deea1ef5b","datavalue":{"value":{"entity-type":"item","numeric-id":5256392,"id":"Q5256392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"341aa311520f1f7062e0b0c1c0f10e20550ef876","datavalue":{"value":{"amount":"+0.8837811350822449","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":"Q1753122$7123685E-073B-4DF7-8CFA-17B39B3A8600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3745b46226265b4008b451fa41b4cfdaa2ed628e","datavalue":{"value":{"entity-type":"item","numeric-id":405113,"id":"Q405113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eee7fc7079ffc477431e2309ec9bc5ddfdb91d2e","datavalue":{"value":{"amount":"+0.871969997882843","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":"Q1753122$9F257DD6-EBB1-43CB-8C1F-C5CC2E8E69D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"807bb80e6593585e2478992f5e618abd341e8e9d","datavalue":{"value":{"entity-type":"item","numeric-id":3691698,"id":"Q3691698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7053e838e1fd52a95872484b21a8b48649751838","datavalue":{"value":{"amount":"+0.8234729766845703","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":"Q1753122$ED8FD720-C2F0-44CD-A3A9-65C600DE02D0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Paths and cycles in random subgraphs of graphs with large minimum degree","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Paths_and_cycles_in_random_subgraphs_of_graphs_with_large_minimum_degree"}}}}}