{"entities":{"Q6955983":{"pageid":21239430,"ns":120,"title":"Item:Q6955983","lastrevid":76055898,"modified":"2026-04-22T16:30:02Z","type":"item","id":"Q6955983","labels":{"en":{"language":"en","value":"A jump of the saturation number in random graphs?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8066816"}},"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":"Q6955983$921B2406-54BD-49F3-B3D9-D0B2C6BCC54B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"23a4d1588050f152e5995440ae1884c39a112357","datavalue":{"value":{"text":"A jump of the saturation number in random graphs?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6955983$AB82B119-B872-455A-A96F-E4597177F07F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50c1725a72987447b523d2e9df910a25b7cedcf5","datavalue":{"value":"1569.05321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6955983$49020324-61C8-484D-82C9-7256303AE22C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bd83dc6a0a6c8d5d71b9510564a3772a965c24b8","datavalue":{"value":"10.1002/RSA.70009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6955983$01C5117F-DE78-4911-BE64-9ABC0E3076FA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"addeac2215d6c24c9a36a7a0f1e247aa1e0f33d1","datavalue":{"value":{"entity-type":"item","numeric-id":2088712,"id":"Q2088712"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6955983$ECFA5961-088B-4152-ADB4-BDF64DE45C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"92b8140f4c37c4afee442cd675725c4ac4d83221","datavalue":{"value":{"entity-type":"item","numeric-id":6177415,"id":"Q6177415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6955983$A473A50F-4EA6-4F48-9957-4A63D6CE51E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"214e732b9ee41b2396f55de0fe64813983a0ad39","datavalue":{"value":{"entity-type":"item","numeric-id":265976,"id":"Q265976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6955983$21B277C3-4955-441F-935E-71BFB74969FE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"607ae7f7d11ced7a8909533172911c64cec6dcc4","datavalue":{"value":{"entity-type":"item","numeric-id":6486797,"id":"Q6486797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6955983$D80484B8-4537-4234-B1CE-D809C9D862E9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1541852f95bfa9523e1e2b6deca7116081cce9f2","datavalue":{"value":{"time":"+2025-07-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6955983$E8C62BE9-7B7A-4C69-B9E4-3F4FECCCB778","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ba11596ebd80fd7b1d93a9a7a60b238da010f0b","datavalue":{"value":"For any graphs \\(G\\) and \\(F\\), a subgraph \\(H\\) of \\(G\\) is said to be \\(F\\)-saturated in \\(G\\) if it is a maximal \\(F\\)-free subgraph of \\(G\\). The least number of edges in an \\(F\\)-saturated subgraph of \\(G\\) is called the saturation number \\(\\operatorname{sat}(G,F)\\). \\textit{D. Kor\u00e1ndi} and \\textit{B. Sudakov} [ibid. 51, No. 1, 169--181 (2017; Zbl 1370.05191)] initiated the study of the saturation problem for random graphs, when the host graph \\(G\\) is the binomial random graph \\(G(n,p)\\) for a constant \\(p\\). In this paper, the authors raise the following conjecture: For a constant \\(p\\) in \\((0,1)\\) if \\(F\\) is a graph such that every \\(e\\) in \\(E(F)\\) belongs to a triangle in \\(F\\), then with high probability \\(\\operatorname{sat}(G(n,p),F)=o(n\\ln n)\\). They improve a solution to this conjecture by deriving a universal bound for \\(\\operatorname{sat}(G(n,p)\\). Further, they also obtain a family of graphs for which the bound is linear in \\(n\\). Besides proving certain useful results, they also raise some open problems whose solution may come close to a full settlement of the above conjecture.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6955983$06937C1B-D929-490E-BF47-721469A6DE12","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c754ec9fae75fbeaa94e089f2452dc68e1235b5c","datavalue":{"value":{"entity-type":"item","numeric-id":198726,"id":"Q198726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6955983$1F7C4154-122C-4CAA-B548-F8E8F2CE7D46","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6955983$1FBB829F-A324-41AB-937B-4E8A3FE4E756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"505dab9721154d1029d881b944cbf9d233b6d0c1","datavalue":{"value":"05D40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6955983$86D60033-550A-4E44-80C2-BCAD5B1ACB3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6955983$B72FBF03-5082-48CA-AC16-689EA2CC84CF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68464da5034a18c6fd0d0ca4396271ff0b7970e8","datavalue":{"value":"8066816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6955983$6EA5B1C7-0149-47D7-BDEE-257A27A3E45B","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6955983$435B38E6-931A-45A2-96AF-BCC898DAE495","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bedd6923f3a60674ffee75cafb41330fb2837ff","datavalue":{"value":"probablistic combinatorics","type":"string"},"datatype":"string"},"type":"statement","id":"Q6955983$6DAEC191-6961-4961-81B4-85312C88D442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4f51776dadcb1bfead92cdaa8c678dc729e342b","datavalue":{"value":"random graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6955983$FDC190E7-51CD-43BB-A38B-82032AABDD67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ba3d08eaa1a82a6fcaa6e6a2a62c141a93978c4","datavalue":{"value":"saturation number","type":"string"},"datatype":"string"},"type":"statement","id":"Q6955983$C3E3CD09-AE48-4F70-8053-EC6FF2F90E77","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":"Q6955983$94FDBD28-B4EB-43D4-9708-52B177E64464","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A jump of the saturation number in random graphs?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_jump_of_the_saturation_number_in_random_graphs%3F"}}}}}