{"entities":{"Q2409840":{"pageid":2420583,"ns":120,"title":"Item:Q2409840","lastrevid":57898443,"modified":"2026-04-03T00:20:07Z","type":"item","id":"Q2409840","labels":{"en":{"language":"en","value":"Local resilience for squares of almost spanning cycles in sparse random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6791423"}},"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":"Q2409840$71D38FEE-476C-4C9C-B1BA-82D05C9A8F26","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2cd1355a430ab0dfcc7e85ae27e644f1738138b8","datavalue":{"value":{"text":"Local resilience for squares of almost spanning cycles in sparse random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2409840$3F0C8E8B-39DF-4458-8948-4A7C66982C3D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cef4e50d62ecea672c6c35a0fb41159b5274e661","datavalue":{"value":"1441.05204","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409840$35D994CE-F5CE-4981-9042-39969587C7C5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d48de915aa01a02038a0ae1831e2489aecfb3653","datavalue":{"value":{"entity-type":"item","numeric-id":1742760,"id":"Q1742760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$3D746691-197F-48E7-A9C4-2EA53FE9F626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a7b1b74b045e21f161107ae2d1ec32cd3fa125c","datavalue":{"value":{"entity-type":"item","numeric-id":173496,"id":"Q173496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$AC530C76-9485-4B2B-99A6-A2E221EB0D1B","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":"Q2409840$AFEEF654-2766-4142-9F3B-56F68FDC6AED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6c5297401e02788bd3f4d1f30d634c2fb25880e4","datavalue":{"value":{"time":"+2017-10-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":"Q2409840$3866B83F-DA09-4B1E-8AC9-840D275DC1BB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"26fd595c7a1907c6e462f2d6e04d372e4732689b","datavalue":{"value":"https://arxiv.org/abs/1606.02958","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409840$F0F66423-77F1-4AD6-9467-925C8AF03A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"87e67b16dcc849fcaf54254fade45a2bd636a675","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i4p8","type":"string"},"datatype":"url"},"type":"statement","id":"Q2409840$6E032B03-C10E-4316-868C-0E8A3976C6B7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b47d412cd5fbd2a670b46238a6dddcd4fe0ed6ba","datavalue":{"value":"Summary: In 1962, L. P\u00f3sa conjectured that a graph \\(G=(V, E)\\) contains a square of a Hamiltonian cycle if \\(\\delta(G)\\geq 2n/3\\). Only more than thirty years later \\textit{J. Koml\u00f3s} et al. [Combinatorica 17, No. 1, 109--123 (1997; Zbl 0880.05049); Random Struct. Algorithms 9, No. 1--2, 193--211 (1996; Zbl 0864.05063)] proved this conjecture using the so-called blow-up lemma. Here we extend their result to a random graph setting. We show that for every \\(\\epsilon > 0\\) and \\(p=n^{-1/2+\\epsilon}\\) a.a.s. every subgraph of \\(G_{n,p}\\) with minimum degree at least \\((2/3+\\epsilon)np\\) contains the square of a cycle on \\((1-o(1))n\\) vertices. This is almost best possible in three ways: (1) for \\(p\\ll n^{-1/2}\\) the random graph will not contain any square of a long cycle (2) one cannot hope for a resilience version for the square of a spanning cycle (as deleting all edges in the neighborhood of single vertex destroys this property) and (3) for \\(c<2/3\\) a.a.s. \\(G_{n,p}\\) contains a subgraph with minimum degree at least \\(cnp\\) which does not contain the square of a path on \\((1/3+c)n\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409840$6C1E22DF-AD97-4844-984C-96BDB6FD4C18","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409840$5BC2D2D2-9753-4E00-A271-F879E6A0A7B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409840$A7997946-CDB1-4721-A2CC-A2E0EBF2ACC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409840$4E681309-FDD1-4FC2-9068-6529FDDF5501","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b10077c6d29b9b336303062a125835d2590986d","datavalue":{"value":"6791423","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409840$7159B366-DA74-4392-8F14-6E7DBB59323F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409840$45AE9D12-AB9C-4B43-A4D5-0DF5CCC5B21E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef1625684ee1906c78ea5e52376065e793cb680f","datavalue":{"value":"resilience","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409840$01F5ECF6-4424-4A8B-8825-CC9CDEB3E7EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01ed07f120c764ac3822047990c919cd761b8514","datavalue":{"value":"almost spanning subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2409840$76BDB0F2-8E22-44D4-BFCC-82266D3AFB2B","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":"Q2409840$23AE9A32-E739-4635-A9AA-D4E8710ADFB7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3430e2caa72a36cf195c133fb5fb279c61dc55","datavalue":{"value":{"entity-type":"item","numeric-id":5126757,"id":"Q5126757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$4DDC38FD-A68F-427D-AEE5-A1DE1600BD6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a55c3a24960786fcf08168b321bfcd461ac080a","datavalue":{"value":{"entity-type":"item","numeric-id":1050368,"id":"Q1050368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$3DE9B532-D82D-42FE-8875-CCC11B621B49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$B5221C2B-06D4-4B00-9DDC-F244DFECCDC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f222388e5cd01b7b997c5b621ee6890ce1bee4f","datavalue":{"value":{"entity-type":"item","numeric-id":476516,"id":"Q476516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$C8F9A99C-7200-443B-80E8-29D45D923545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3159cfa27d8998a0889650e457a61616bca97f34","datavalue":{"value":{"entity-type":"item","numeric-id":5812733,"id":"Q5812733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$36D113F1-7AF9-4EAB-B8C2-2450E448D1D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d75e0e999a0a0c1a5bc04b8131c00a7fb4003c82","datavalue":{"value":{"entity-type":"item","numeric-id":858679,"id":"Q858679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$D65B19CA-B5AE-46C4-AC75-EC60EFAB916B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a42947a8aab8113178dbbd91216a47bc1e6b3a5b","datavalue":{"value":{"entity-type":"item","numeric-id":3416250,"id":"Q3416250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$3281D648-F65F-44C2-8699-5120E0A29FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0aef3ff5cffd3b07288de9ab2d7ff5ebd39d4c","datavalue":{"value":{"entity-type":"item","numeric-id":4336102,"id":"Q4336102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$4F7C491F-AFBF-4E57-B1FD-C5C6BBF54D21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31ffcb65b5d111490042d472d548c61b4cfc45f0","datavalue":{"value":{"entity-type":"item","numeric-id":1375060,"id":"Q1375060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$647EE8E7-E425-47F9-9FCD-79AF854387DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e11bf65cb6459492b00543657811c7c16e1dde47","datavalue":{"value":{"entity-type":"item","numeric-id":1055441,"id":"Q1055441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$79D56A62-5CBA-45BD-9536-405D499AD5B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd6dc032d205f3969ec04e561df0192635c1d5b5","datavalue":{"value":{"entity-type":"item","numeric-id":4894609,"id":"Q4894609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$D9EEF7D9-1870-4AD6-981D-06C4D961654D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0a795a1b9d741ade8d6f6b7e878df8900cc60ea","datavalue":{"value":{"entity-type":"item","numeric-id":4899069,"id":"Q4899069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$83B0EE00-39F4-4CB8-B6B2-C1B9EE284879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"245e31b18abcea78e04410fdcf74e14d38a3ee88","datavalue":{"value":{"entity-type":"item","numeric-id":3168496,"id":"Q3168496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$21ED36FB-D473-4749-ABE9-0DF7BBECBC92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ba6cbad3609d0bffe6edec1b118412b5d2c81af","datavalue":{"value":{"entity-type":"item","numeric-id":2998854,"id":"Q2998854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$C88839E9-C6EA-42F7-BAAB-D02B68B3B7F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7645417c6b9a9d3537fd0be9fc0136de2571c25","datavalue":{"value":{"entity-type":"item","numeric-id":2640616,"id":"Q2640616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$C80AAB1F-B4FE-465C-8D9D-1C4AF52A0735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2409840$D94C8ED2-9DB8-4B62-8417-DCC08BEB3EFC","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c1506fa480d2b6df35cbd57743acf6df5f6368e2","datavalue":{"value":"bafkreihtvlxulkb7agvc6gnqbwi6tfsq3phxgbuuleknzisyroxou4jlia","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2409840$64E37CCB-F951-47BC-9854-243C03936E7C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2627eb6b7bfe6012130bad96951f21058db24171","datavalue":{"value":{"entity-type":"item","numeric-id":4625026,"id":"Q4625026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86e72240f2a1d4e642cd8ab72953d04d30766a03","datavalue":{"value":{"amount":"+0.8814200758934021","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":"Q2409840$BC297328-21D4-4E39-899E-332994877CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92c9fb34978b62a7a2f34f805ea91ab0e2c0864a","datavalue":{"value":{"entity-type":"item","numeric-id":4899069,"id":"Q4899069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd1517d0083ad5b8a6ce21f0e2cb12f5520fe1e2","datavalue":{"value":{"amount":"+0.8703030347824097","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":"Q2409840$730DE130-1C9F-408A-AD4C-2600735ED42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92ad89f7cd0bc75e8adb5e3c7073bebea955e914","datavalue":{"value":{"entity-type":"item","numeric-id":2664554,"id":"Q2664554"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3d5905277b5408deaef3785e44455a1e2f81399","datavalue":{"value":{"amount":"+0.8648609519004822","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":"Q2409840$CBF9D9F8-1AD5-4828-8EB0-BBC682B873F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2ea856f96b1b24fc4e707485422ddcfe9c559f3","datavalue":{"value":{"entity-type":"item","numeric-id":4894609,"id":"Q4894609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a56bb6cdea7e88886bc483bfbc90dfe78110c95","datavalue":{"value":{"amount":"+0.81605064868927","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":"Q2409840$1699C21B-31CD-4117-8FB0-479A68753F13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d702966ff51699f1ea5d3cdecfc6a20dad827fe3","datavalue":{"value":{"entity-type":"item","numeric-id":322234,"id":"Q322234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a56bb6cdea7e88886bc483bfbc90dfe78110c95","datavalue":{"value":{"amount":"+0.81605064868927","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":"Q2409840$385E00F5-B532-4816-9953-71437D407B66","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2409840","badges":[]}}}}}