{"entities":{"Q6197319":{"pageid":13332207,"ns":120,"title":"Item:Q6197319","lastrevid":58763211,"modified":"2026-04-06T15:28:22Z","type":"item","id":"Q6197319","labels":{"en":{"language":"en","value":"On R\u00f6dl's theorem for cographs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7806240"}},"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":"Q6197319$FCCFB2DF-E3E5-4F38-83B0-94DE6F0E440E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"67ee0234779cedc7bc9c682bbdcb60c27dbb711e","datavalue":{"value":{"text":"On R\u00f6dl's theorem for cographs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6197319$5E6E9558-C7A7-41D3-BD42-B8878498859F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dfc23e487bcb47ce4af70b0689de113452591985","datavalue":{"value":"10.37236/12189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6197319$7F8CE631-3957-4D4A-B197-D1AE95E1E31B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"af500a65311a4c34eb25256ce5e9f19fbfb1648a","datavalue":{"value":{"entity-type":"item","numeric-id":480809,"id":"Q480809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6197319$7DE9A4DF-31F2-437B-9ABB-0D17F064B83F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"63374f39c7f9618158f0fe867382b7bf912eea01","datavalue":{"value":{"entity-type":"item","numeric-id":313428,"id":"Q313428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6197319$90FD8B50-7F44-4A02-97E5-337F1313C8B9","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":"Q6197319$49B357E1-A92B-4E19-B89D-42884C8F93D5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7adfab34f3c3d8e61a418701d66917b32bf911dc","datavalue":{"value":{"time":"+2024-02-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":"Q6197319$DEE05373-4BB4-46BC-A3C2-E9ECE4692B59","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c0520e71ce63d399b4511a9b30bb46938d831e30","datavalue":{"value":"https://arxiv.org/abs/2308.00593","type":"string"},"datatype":"url"},"type":"statement","id":"Q6197319$688ECECF-981D-490D-8367-FB90F3CE1E2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"16b911c5b421f83ea6d7d8c59f24bf933b0535f9","datavalue":{"value":"Summary: A theorem of R\u00f6dl states that for every fixed \\(F\\) and \\(\\varepsilon>0\\) there is \\(\\delta=\\delta_F(\\varepsilon)\\) so that every induced \\(F\\)-free graph contains a vertex set of size \\(\\delta n\\) whose edge density is either at most \\(\\varepsilon\\) or at least \\(1-\\varepsilon\\). R\u00f6dl's proof relied on the regularity lemma, hence it supplied only a tower-type bound for \\(\\delta \\). \\textit{J. Fox} and \\textit{B. Sudakov} [Adv. Math. 219, No. 6, 1771--1800 (2008; Zbl 1152.05054)] conjectured that \\(\\delta\\) can be made polynomial in \\(\\varepsilon\\), and a recent result of \\textit{J. Fox} et al. [``Induced subgraph density. II. Sparse and dense sets in cographs'', Preprint, \\url{arXiv:2307.00801}] shows that this conjecture holds when \\(F=P_4\\). In fact, they show that the same conclusion holds even if \\(G\\) contains few copies of \\(P_4\\). In this note we give a short proof of a more general statement.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6197319$6AD349E0-0D12-460B-A5C0-108AC0DCA752","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6197319$22D0EE44-CC44-4E5C-B6E8-48880CD8C3FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6197319$6E331224-9BBC-4319-8002-AF61BF41789E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6197319$052626B9-AB48-4716-979C-9D805B72E18D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7fa7e76e921eb6798b8638e3b974bedd7252f2a1","datavalue":{"value":"7806240","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6197319$DA67B6E7-586F-46D0-973C-EAF16B4CC50E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8af94ff6f545d2be756a5e8fb07bf13bd7a35fe","datavalue":{"value":"Erd\u0151s-Hajnal property","type":"string"},"datatype":"string"},"type":"statement","id":"Q6197319$52B71C0C-AC5D-430B-B49B-5C9087A60CCD","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":"Q6197319$0B780927-758B-48ED-AE49-082645C05D74","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"15192b9abca3302b0865f7461bb71a1e2920a3b9","datavalue":{"value":"W4387772189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6197319$B30A7611-2EBC-4321-B23C-8BA1DEEB561D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3457de1e7afbdf3b1ab8a57a41eccb3470874f0e","datavalue":{"value":{"entity-type":"item","numeric-id":5364250,"id":"Q5364250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6197319$5E25C753-0B24-4BC3-A904-7CBE23FF44B4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26248ee6788d94c10fae81643a26d7dca549421e","datavalue":{"value":{"entity-type":"item","numeric-id":6655697,"id":"Q6655697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47ba52e26f898955f089f878451ec5d0b9f19638","datavalue":{"value":{"amount":"+0.8876709342002869","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":"Q6197319$FB1D7233-BDC1-44A0-807E-C617A0E35E17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d48101231cac363f3c18fd35458901fe0278a0f","datavalue":{"value":{"entity-type":"item","numeric-id":6051054,"id":"Q6051054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d79178e3181d837246c4833ca87d67b163ccca8d","datavalue":{"value":{"amount":"+0.8234544396400452","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":"Q6197319$27E4F052-7FA3-4513-89C1-7509AA830E89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f12bb875e6b16215023cd3146ab89d4a8cfb994e","datavalue":{"value":{"entity-type":"item","numeric-id":6133166,"id":"Q6133166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffff55b934e0f71427d401e70192b60ead19190c","datavalue":{"value":{"amount":"+0.8055381178855896","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":"Q6197319$19D0DBDF-EFC3-402F-84FC-20DFADD6C0D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3d2f651c816b3cdfdfe8fa375bd13cd0f480acae","datavalue":{"value":{"entity-type":"item","numeric-id":6624423,"id":"Q6624423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14301f4035aa0e63675791489aa353ddab393afe","datavalue":{"value":{"amount":"+0.7641919851303101","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":"Q6197319$908AE8D1-66BA-489F-B66F-78B1A7A5871B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e12340f9249803648a8f808cb11598f82064bb9d","datavalue":{"value":{"entity-type":"item","numeric-id":2380453,"id":"Q2380453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"546d4006ff8ef0865ccb6900b5dd371182f14ec4","datavalue":{"value":{"amount":"+0.7482362389564514","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":"Q6197319$3D179F9C-4CF0-4259-921D-4C90F936FD70","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":"Q6197319$653DCF76-62F4-44A2-9980-CF6FB1BF2168","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6197319","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6197319"}}}}}