{"entities":{"Q6081383":{"pageid":13215690,"ns":120,"title":"Item:Q6081383","lastrevid":58658562,"modified":"2026-04-06T05:23:05Z","type":"item","id":"Q6081383","labels":{"en":{"language":"en","value":"Pure pairs. V: Excluding some long subdivision"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7745889"}},"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":"Q6081383$54219890-F44F-46C1-8018-5EA3DB8BF595","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"68397e9881ea11788610dc21094b0a4ff147b4cb","datavalue":{"value":{"text":"Pure pairs. V: Excluding some long subdivision","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6081383$8EE6E849-3848-4B1B-AEF4-BB985D6F79A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8b2beaa85ff67f6ba8323eb17002460f5e5f0aa","datavalue":{"value":{"entity-type":"item","numeric-id":846045,"id":"Q846045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081383$99F5C352-127D-43E2-8AE4-66BD8CDF0141","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081383$C6329F27-C3FB-4FB2-A52A-2B613717D57D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f84c2585906a3dfec8dc78c048cfc8b3b8be2285","datavalue":{"value":{"entity-type":"item","numeric-id":345122,"id":"Q345122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081383$82CC0947-22A5-4C53-8F40-73E627922ABD","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6081383$34B74F02-517C-4553-AF3B-DF51B1BD6E5A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31c936eef8b332040242af2e27eaff5bc37458f1","datavalue":{"value":{"time":"+2023-10-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":"Q6081383$6BAB9527-7A05-4D2E-BD99-4048E2D363C2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7aaf5221f13ae28500a1280e063e90d685296e4","datavalue":{"value":"https://arxiv.org/abs/2105.03956","type":"string"},"datatype":"url"},"type":"statement","id":"Q6081383$38F1259A-970E-4CAE-9CDE-AF5B77511820","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e8a90a86a042b6c17009eed315bcb6913dacb355","datavalue":{"value":"Two disjoint sets \\(A\\) and \\(B\\) of vertices of a graph \\(G\\) form a pure pair in \\(G\\) if the possible edges between \\(A\\) and \\(B\\) are either all present in \\(G\\) or all absent. Which graphs have large pure pairs? \\textit{J. Fox} [Order 23, No. 2--3, 197--209 (2006; Zbl 1108.06002)] proved that for every sufficiently large positive integer \\(n\\) and every \\(n\\)-vertex comparability graph \\(G\\) there is a pure pair \\(A\\), \\(B\\) in \\(G\\) with \\(\\vert A\\vert ,\\vert B\\vert \\ge n^{1-o(1)}\\), and conjectured a similar bound for all perfect graphs. Part V of a series of at least 10 papers on pure pairs proves this conjecture, and strengthenings thereof. Let the branch-length of a forbidden induced subgraph \\(H\\) be the minimum of the length of a shortest cycle in \\(H\\) and the shortest distance between vertices of degree \\(>2\\) in \\(H\\). Let \\(c>0\\) be such that \\(1/c\\) is integral, and let \\(H_1\\) and \\(H_2\\) be graphs of branch-length \\(>4/c+5\\). There is an \\(\\varepsilon>0\\) such that every \\(H_1\\)-free and \\(\\bar{H}_2\\)-free graph on \\(n>1\\) vertices has a pure pair \\(A\\), \\(B\\) with \\(\\vert A\\vert \\ge \\varepsilon n\\) and \\(\\vert B\\vert \\ge \\varepsilon n^{1-c}\\). The connection to the Erd\u0151s-Hajnal conjecture is explained in part II by \\textit{M. Chudnovsky} et al. [Combinatorica 41, No. 3, 379--405 (2021; Zbl 1488.05427)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$141AA444-9180-4EE8-BAF7-DEEC84BD0D36","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$DAA0DE1B-974A-4DD6-B07E-25416AC25E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$59DB9C79-C86A-451C-B712-818FF4BB55CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$CAA02601-A7F6-4776-B237-EBE6B0212B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$49C07D92-2E1A-4F34-AEBE-18AE0C1F61EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b35d56cb5f6b105b6d059e7874c18d347cba7f28","datavalue":{"value":"7745889","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$3598F0BC-08AA-45B0-B9E6-E485DDE4ABC4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f4bc5ef64b80473f2dd853aa845c54c1eb0ce36","datavalue":{"value":"induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$F083A5CF-8F86-4FAA-95A1-61D8BFEA41DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"92c1fa317f2d56dc1218643741ac7adce1e68b9f","datavalue":{"value":"ordered graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$48AD7C80-17E7-49B6-88DC-9F95FBD1ACDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$45A944F7-F5D6-44BA-B778-20677966B9B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2580348112e8be1d6ec9396b57de7c09f99e7ad4","datavalue":{"value":"Erd\u0151s-Hajnal conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$E05CC5E5-D672-4CFB-A5F1-76162225D343","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b23e4315a08f1dab32a125b8cac85d5a144df038","datavalue":{"value":"long subdivision","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$6259CE02-5CBE-4B48-94EF-3E3C445CCCB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2130a6124371cfd5e742efe136e79b4f5bd23c49","datavalue":{"value":"branch-length","type":"string"},"datatype":"string"},"type":"statement","id":"Q6081383$0AF51519-D4F1-4E81-A298-C4DCE425DFDD","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":"Q6081383$68D4F9AA-864E-4CE4-9E0E-73C8C0A97AB9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c10b528685354b74c554f463b4453933ccd8fbeb","datavalue":{"value":"W3160589288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$249B04F8-443F-4D7A-A311-52CB0F0E8EAF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"79de15490f3421dc270623b0063a847b771692cd","datavalue":{"value":"10.1007/S00493-023-00025-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6081383$DC06C0C7-7A2F-4872-B290-8BC9EFFAD277","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3558b3661ccaeca0be559c939a7a1b3ab422471","datavalue":{"value":{"entity-type":"item","numeric-id":2043764,"id":"Q2043764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb60f93df2fcd1df8661b62deb618a169ab2b93b","datavalue":{"value":{"amount":"+0.8590707182884216","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":"Q6081383$198FB10B-B5E6-4FF2-95BF-76AE5E34AAAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f43a64e65bcf4f9f4ef5e6ab1a1019321c2ab4b","datavalue":{"value":{"entity-type":"item","numeric-id":5020840,"id":"Q5020840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cbc5fc5484a4cbc6d7d1366dbc1805b34873d58","datavalue":{"value":{"amount":"+0.8389167189598083","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":"Q6081383$EDFE5B81-5C17-42CA-B36D-8739FB2B3B90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5fd77d6aba5ac2a6ecbe3039d8d5feb4b7e0cad","datavalue":{"value":{"entity-type":"item","numeric-id":2213783,"id":"Q2213783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff8e8af14dd9242c2f28a1f7f6e704cefa69f3dd","datavalue":{"value":{"amount":"+0.8195227384567261","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":"Q6081383$5A467D87-1442-4F14-902B-2EA8FB7C3E04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33956aa0e4895269ed69be13e07d585ab9d2a020","datavalue":{"value":{"entity-type":"item","numeric-id":6188521,"id":"Q6188521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"871889f3e1f1b88f6f5d5fbb3e393f72dfe6a02c","datavalue":{"value":{"amount":"+0.8176888227462769","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":"Q6081383$25220630-8EE8-47D4-B223-89E5AA1C4768","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"de94f8a53a89782c41a2322ba90189ac6d32d9b9","datavalue":{"value":{"entity-type":"item","numeric-id":5066924,"id":"Q5066924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e32d206083c50c4ec9d07ec05daeeec50ee164e1","datavalue":{"value":{"amount":"+0.7929471731185913","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":"Q6081383$75F3E3BD-F0D4-42B2-BC35-4CEF56F4FE95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6081383","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6081383"}}}}}