{"entities":{"Q2235276":{"pageid":2246019,"ns":120,"title":"Item:Q2235276","lastrevid":73611507,"modified":"2026-04-14T16:39:05Z","type":"item","id":"Q2235276","labels":{"en":{"language":"en","value":"Maximum induced forests in random graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7412186"}},"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":"Q2235276$E67379CF-CF7F-4940-AF04-F0AF63B414B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ab592711b9569bf44b37c4340050cfd12a27b18","datavalue":{"value":{"text":"Maximum induced forests in random graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2235276$2E52B298-6A19-465F-B800-EA8E4D36AEC0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f19fd39aadafbde48b21223264b907b06ae9a6c1","datavalue":{"value":"1477.05172","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$5225D493-905E-4D8A-AD27-DCD697CCF781","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$7E004BBD-4FDC-43B5-A6F5-787A9B51480A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$865C4952-3653-455A-B45C-C32DA42A9C65","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63ea68637f5cfe48b0d0d77e5f0fa82323c89d78","datavalue":{"value":{"time":"+2021-10-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":"Q2235276$A2EFFFCF-8435-44C9-A8A5-D140481D4543","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"585f7c8468714f7f53066fd842041b680381c675","datavalue":{"value":"https://arxiv.org/abs/2101.08190","type":"string"},"datatype":"url"},"type":"statement","id":"Q2235276$4445F155-1728-43C6-AE37-5D08D05209B6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ee3c319656036afc9c68af6af5d71f2507f883ce","datavalue":{"value":"The authors prove that the maximum size of an induced forest (i.e.\\ a subgraph that is a forest) in an Erd\u0151s-R\u00e9nyi graph \\(G(n,p)\\) is of size either \\(\\lfloor2\\log_{1/(1-p)}(enp)+2+\\varepsilon \\rfloor\\) or \\(\\lfloor2\\log_{1/(1-p)}(enp)+3+\\varepsilon \\rfloor\\) with high probability as \\(n\\to\\infty\\), when \\(p\\) is fixed, for some constant \\(\\varepsilon > 0\\). The argument is a first moment computation for the higher bound, the lower bound being deduced from \\textit{D. Kamaldinov} et al. [Discrete Math. 344, No. 2, Article ID 112205, 14 p. (2021; Zbl 1454.05111)], where the same concentration result is proven for the maximum size of an induced tree in \\(G(n,p)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235276$3DA32068-B915-4903-A0D8-A87B89338EE6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9475d262ec55242fd2469ab2c99e8e63adbb04ff","datavalue":{"value":{"entity-type":"item","numeric-id":1617122,"id":"Q1617122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$5F25EDCC-11A2-4A9A-B4AB-1C0661FEEA33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$9127B0DA-C2A5-4847-9FCA-CD9D78AA2771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$7E2A41BE-DF5E-4814-8DE4-0EB8164490F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$ECFE3BDB-C626-4307-8384-F30C0A143B48","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e1a5478c3bf851281e128cccd40c55c8c7f0b39f","datavalue":{"value":"7412186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$FE5663E4-1530-48C6-B6F4-F038AD00FFDA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0446baf9c31d45b16691b35420e6e46c50f286","datavalue":{"value":"random graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235276$528AEE5A-1714-4333-A4B7-3DB78A70DA82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"245f22e847d54aaf868a97e707981e1b10ddd91b","datavalue":{"value":"concentration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235276$54E258B5-827C-4F01-9D91-B9798269A56C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709ab8e23af022def6eacaa518d2f70f8cec2bdc","datavalue":{"value":"induced forest","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235276$3B762172-77EE-49AB-B26F-A437BEE66DA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63c1434323ab49931c3af95549372679e5687894","datavalue":{"value":"induced tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q2235276$D606BF05-7BA9-4563-90F4-471A1BD203BC","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":"Q2235276$BD38F1C0-3D2F-4B91-8169-446694059062","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9940715f026f1a0be334f3e648eeb3688b648951","datavalue":{"value":"W3204774295","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$604D5D4C-955F-417F-A79E-CDFF2F381D17","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f11d905c5d301eb7550191ae68eb684c9598dcb8","datavalue":{"value":{"entity-type":"item","numeric-id":4111621,"id":"Q4111621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$292734FF-08C3-419C-B9D0-31F84AB20603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b86f05fffc753e9ac084120182b55844176a03d5","datavalue":{"value":{"entity-type":"item","numeric-id":5195116,"id":"Q5195116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$5F7EBFB6-2249-46EC-B758-5AC17F1D9373","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6254e3774534a53de166055c12cccf75cb257bc2","datavalue":{"value":{"entity-type":"item","numeric-id":4050627,"id":"Q4050627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$7DC9C53E-DFFB-4653-9D1B-0FD3BB369E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5487da924a1bcdfe2df9214e8bc20708759201b","datavalue":{"value":{"entity-type":"item","numeric-id":2214056,"id":"Q2214056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$E7456A59-BC2F-48B8-A4F5-2EF2D10E5B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f98cd8e79e44b62b6b3a1e3bc32134c136af16","datavalue":{"value":{"entity-type":"item","numeric-id":2835279,"id":"Q2835279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$AD80C2C1-83EC-453B-B9A9-5F2F598FD972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee2dff358e0f47fee5882e6f1bf6e70cc1f7f452","datavalue":{"value":{"entity-type":"item","numeric-id":1121286,"id":"Q1121286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$8583DBD5-22A6-4863-95A4-ACB3139300A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1f7ec931168e4dd9eaa62f72639c99b4c21ef47","datavalue":{"value":{"entity-type":"item","numeric-id":5616724,"id":"Q5616724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$84DDCA0C-2DD8-4D70-9A40-B7D72F1D42C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8d705524fdbfe2e52f105b23cd7e5e22a8d21d8","datavalue":{"value":{"entity-type":"item","numeric-id":1088688,"id":"Q1088688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$333A81F5-2C34-43BD-A8A2-56F25A9BAADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c124b23e66bda5f6b96b58b4ca724e8f07b76603","datavalue":{"value":{"entity-type":"item","numeric-id":3229522,"id":"Q3229522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$CC09A2A7-3108-4230-8BE1-3DDD9AF7C315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ad64d62d89102920c3c52a8c6730ebd01a66fb4","datavalue":{"value":{"entity-type":"item","numeric-id":4894603,"id":"Q4894603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2235276$7569D1C9-1FD9-470A-BCA7-05A59D5341AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"04e9e47e389d1baa00a8d870e714bcb085ac1db7","datavalue":{"value":"10.1016/J.DAM.2021.08.018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2235276$430FC5B0-BA10-40E2-A5ED-35E32B165EC6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"195f188c600f7148e2c4d5494bc916865bec3a67","datavalue":{"value":{"entity-type":"item","numeric-id":1088688,"id":"Q1088688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00213855086287a8c7a12d0193803c8babbe4e4a","datavalue":{"value":{"amount":"+0.8529433608055115","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":"Q2235276$A3742170-8A80-430F-81FC-4239EBD25483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c00b715f2293aca849853b619cb988d1afa3106f","datavalue":{"value":{"entity-type":"item","numeric-id":790843,"id":"Q790843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1890436a165856e78cf4c35fa43c7038079169e2","datavalue":{"value":{"amount":"+0.8465636968612671","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":"Q2235276$18539128-3487-4D5C-B143-9D5836D25BEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c6776cd1d67123d3b08c5c42b5ece3fbdacc608","datavalue":{"value":{"entity-type":"item","numeric-id":3545905,"id":"Q3545905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"62f78296e8938a944188b539b3d9fb2b094d5d44","datavalue":{"value":{"amount":"+0.8457754850387573","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":"Q2235276$302A3728-D781-4225-8C7E-93B8EF2B92A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5035870b35383c40f180da2d5454e845a8d9a34f","datavalue":{"value":{"entity-type":"item","numeric-id":1879119,"id":"Q1879119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"927f946bd325eeddfae6c5e76f7a338cb2d0fd15","datavalue":{"value":{"amount":"+0.8429021239280701","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":"Q2235276$FF3E44E2-5CB9-4E72-AC00-2F4E0403454A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0eb96f8e67c98beeab820c71c54ce449b56814a","datavalue":{"value":{"entity-type":"item","numeric-id":3816113,"id":"Q3816113"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"509c8eeeef98ed1a29905c6e54fe42ac8433ca89","datavalue":{"value":{"amount":"+0.8417801856994629","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":"Q2235276$4FC386C5-8850-42CD-BF2A-061154991C60","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum induced forests in random graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_induced_forests_in_random_graphs"}}}}}