{"entities":{"Q405113":{"pageid":406880,"ns":120,"title":"Item:Q405113","lastrevid":56902287,"modified":"2026-03-24T13:00:47Z","type":"item","id":"Q405113","labels":{"en":{"language":"en","value":"Long paths and cycles in random subgraphs of \\(\\mathcal{H}\\)-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340128"}},"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":"Q405113$44A5F107-6A5B-48C0-94C4-5AB497B811F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"641e652144fec24dc9a138285921d9e68623a52f","datavalue":{"value":{"text":"Long paths and cycles in random subgraphs of \\(\\mathcal{H}\\)-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405113$AB67B654-DC02-4EF7-A568-ECDC37541490","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4d57c541fb9f75c48df6a1ba2ff1a1ba8604a91b","datavalue":{"value":"1300.05284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$FB525A7B-81CF-458C-AA81-72FB055D9273","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1cf400bc99a406c4d5dfcfdd4d04f10c4dc1f7f","datavalue":{"value":{"entity-type":"item","numeric-id":178700,"id":"Q178700"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$7E8F1AFA-FDBA-43AC-BF18-21A205ED9461","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a8013bc00783240c57786649bc43e422121684be","datavalue":{"value":{"entity-type":"item","numeric-id":285062,"id":"Q285062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$4FBD2CCD-8D53-4413-84A6-CE4DCB3C98E8","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":"Q405113$8BCAB3E7-44E4-45B5-971B-AA4CF7A6F080","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405113$0E409A3C-31A1-4C90-8A29-FBDEE3C16876","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0618a597a386cc65abf45e8de6ae213985250512","datavalue":{"value":"https://arxiv.org/abs/1303.1066","type":"string"},"datatype":"url"},"type":"statement","id":"Q405113$EF3BDD61-97BA-4F42-A06F-33DFAB1CB29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d4ef6130b9ed75f9f41bd9ac13173073fdbfe585","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p30","type":"string"},"datatype":"url"},"type":"statement","id":"Q405113$A0450093-DA06-41C1-872B-AC8AC5E23107","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9095b31e551440a796f40e5caddf3915d05c056","datavalue":{"value":"Summary: Let \\(\\mathcal{H}\\) be a given finite (possibly empty) family of connected graphs, each containing a cycle, and let \\(G\\) be an arbitrary finite \\(\\mathcal{H}\\)-free graph with minimum degree at least \\(k\\). For \\(p \\in [0,1]\\), we form a \\(p\\)-random subgraph \\(G_p\\) of \\(G\\) by independently keeping each edge of \\(G\\) with probability \\(p\\). Extending a classical result of \\textit{M. Ajtai} et al. [Combinatorica 1, 1--12 (1981; Zbl 0489.05052)], we prove that for every positive \\(\\epsilon\\), there exists a positive \\(\\delta\\) (depending only on \\(\\epsilon\\)) such that the following holds: If \\(p \\geq \\frac{1+\\epsilon}{k}\\), then with probability tending to \\(1\\) as \\(k \\to \\infty\\), the random graph \\(G_p\\) contains a cycle of length at least \\(n_{\\mathcal{H}}(\\delta k)\\), where \\(n_\\mathcal{H}(k)>k\\) is the minimum number of vertices in an \\(\\mathcal{H}\\)-free graph of average degree at least \\(k\\). Thus in particular \\(G_p\\) as above typically contains a cycle of length at least linear in \\(k\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q405113$3C1DD3A1-89A5-41A4-BB80-45B52B62CA93","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$9754019B-7C5E-44A2-ADB7-EE2B28144E0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$E0A83444-2FCB-42C7-9D82-D79710D43B68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$527F6573-E7EA-4252-8043-A4C1F1F4F700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$E5325993-9BB3-4DA3-A0CB-56AA0E491C6B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5dc2fba2c407e83c4aa7c2fdafb7375eb9ab289","datavalue":{"value":"6340128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$FB2FAEA2-02EC-41CD-A785-FBB466C9A298","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q405113$06987485-83C5-4191-A20B-8954F3C35B59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453a43e7e93d9a367957c940a4dbc5498dddc3ee","datavalue":{"value":"forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q405113$B6C7C42A-AFAF-4684-936A-BA3227B61F65","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":"Q405113$C47CA44B-1D49-4702-93D4-849162F1917E","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":"Q405113$2D9CB871-FCEE-49A7-8EBC-702EF9334AA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2758f48b1a93e71d851a0e4b14bce521c35fc05","datavalue":{"value":{"entity-type":"item","numeric-id":3503433,"id":"Q3503433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$EDCB07F8-812A-4E14-8267-593AE2C5295F","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":"Q405113$7CB56F37-FB38-4CF0-B583-9B123337F0E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d81d022f27d459c65117397e298a3e45690fb65b","datavalue":{"value":{"entity-type":"item","numeric-id":1844243,"id":"Q1844243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$153F704A-49FD-4BF0-8E2A-9E5CDDE2050B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e622e5707cb1957d253d5b9e482066961a80f854","datavalue":{"value":{"entity-type":"item","numeric-id":4500709,"id":"Q4500709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$B3C885A9-ECA1-45C5-AA19-794577C880D9","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":"Q405113$24A5ADA8-3381-41AC-9B55-40474D8EA7E5","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":"Q405113$A4478C77-313F-4FAC-AC06-525CD34C10B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f55f1e038afd85377e01e81bd97f16855356739","datavalue":{"value":{"entity-type":"item","numeric-id":5397728,"id":"Q5397728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$857ECF0B-235C-486C-85B6-17AA6A01D79D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46d9ad90196724f52c8b5dd6156076cdc3bcbc64","datavalue":{"value":{"entity-type":"item","numeric-id":4446876,"id":"Q4446876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$83662A99-E1A5-4E51-852F-4016AE735D5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"984b0790103c755d1e373d861a44bec66558001d","datavalue":{"value":{"entity-type":"item","numeric-id":5555420,"id":"Q5555420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$91970C04-606A-4339-9F49-7925757EB5FE","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":"Q405113$8160C4A5-E59F-4B7C-B7F8-173B65513AEF","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":"Q405113$99C2124A-3AAF-445F-BCB9-4A43E265855A","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":"Q405113$3BF47ECB-4DE4-473B-A702-630E5FD3A0E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14b5b68e795fecee578ee6f531023fb47d4d0bfa","datavalue":{"value":{"entity-type":"item","numeric-id":4226453,"id":"Q4226453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$A6CE80AF-FF0A-45DD-AB57-EDACEC8F0EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeb7a57c78a894e3d0403e82c2e78e47c63f7774","datavalue":{"value":{"entity-type":"item","numeric-id":5560919,"id":"Q5560919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$724A95CF-1501-4D3A-AF63-6D56930566A7","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":"Q405113$4F2451D7-697E-4236-84E6-AA1EE74E1866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad266fb3b1c6c5e3a807915143f36a85b0afeba1","datavalue":{"value":{"entity-type":"item","numeric-id":949802,"id":"Q949802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405113$F1ABBBF4-C91F-4B09-8A07-7FFB770AA217","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3e2a6c16d48f0145cf36458e138a0a4cf6327d1b","datavalue":{"value":"bafkreicvhd3ua63v4jeybbaqppqygcwqyqsorr7yqoklgdn3oqmektucby","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405113$EF5A44AF-33FF-486E-B3B6-FD2352AA9CFD","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":"c413acbe930d2a5a46ecb5adb7aceb114bec6ffc","datavalue":{"value":{"amount":"+0.9017862677574158","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":"Q405113$117ECDD5-8078-4DA4-9E63-1D402EEF6CFB","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":"d9b569dc3da6cd0e2d44a5399fabd169a173cbee","datavalue":{"value":{"amount":"+0.8841885924339294","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":"Q405113$5F9BE7C4-0372-49C0-9A3A-6D758AFD074F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"674a9b926c5b6d6503f7223c4bc196acda2f78f0","datavalue":{"value":{"entity-type":"item","numeric-id":1174180,"id":"Q1174180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d924578ccbe216bc5995955e950cfe05435a3921","datavalue":{"value":{"amount":"+0.8813316226005554","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":"Q405113$9216C563-EE38-4F96-B2C6-64409546F36A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"983f090ade3bf35d092bdc0422660785d6f4916b","datavalue":{"value":{"entity-type":"item","numeric-id":1753122,"id":"Q1753122"},"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":"Q405113$E6835C7E-0140-4C29-AC10-499A857EA0B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf61e6f21cdea33e405806814c4a243c8c6009e","datavalue":{"value":{"entity-type":"item","numeric-id":5366938,"id":"Q5366938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"912d72fa754b6ea9a32db7d62fdb7209e8d7f873","datavalue":{"value":{"amount":"+0.8478940725326538","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":"Q405113$2E675909-285B-41AB-801E-DB5D195149CC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:405113","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:405113"}}}}}