{"entities":{"Q1613547":{"pageid":1624287,"ns":120,"title":"Item:Q1613547","lastrevid":72345381,"modified":"2026-04-14T04:16:49Z","type":"item","id":"Q1613547","labels":{"en":{"language":"en","value":"Tripartite version of the Corr\u00e1di-Hajnal theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792465"}},"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":"Q1613547$3330F991-8FCB-4AF3-8BCE-6CE1CA963474","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a61e41fdf99e6b40d572168da2f6a5c02903d6dc","datavalue":{"value":{"text":"Tripartite version of the Corr\u00e1di-Hajnal theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613547$EA953647-6EFD-4F5C-8223-9FF584549411","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"01b8bb595b65ae95a6d1c5a7cc58e5e544103aaf","datavalue":{"value":"0995.05069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613547$20FFEB82-D7D6-4D61-86EB-C8B57E379668","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1e93c2c5d7b660cb385980d69d3ab438981bdf55","datavalue":{"value":"10.1016/S0012-365X(01)00373-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613547$AAA3E059-3C29-47BE-AC26-59EE0689D95B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b6cfc2ec3578dd9520412d6985440a9e7332351","datavalue":{"value":{"entity-type":"item","numeric-id":1613546,"id":"Q1613546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613547$1BC78E16-417F-46A1-BC76-4FEDC422BE17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"15796c0873d9a05767b939c2bba042c56c00920f","datavalue":{"value":{"entity-type":"item","numeric-id":313785,"id":"Q313785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613547$32D8F270-7816-4A17-A327-56F4FE3BDD3B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613547$34C52C31-5F7C-4725-85AE-22D347EAFFFD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613547$A6FE812F-F3B6-4F9D-A133-651C559BB74A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5c3970b9a572f530211cc96c8bfed5639bf5601e","datavalue":{"value":"https://arxiv.org/abs/1605.06647","type":"string"},"datatype":"url"},"type":"statement","id":"Q1613547$2250B24B-0043-4E7C-A2EC-9413EFD1A2B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"009f4d050240e2bc092c6a414822e11f2d8ee9ca","datavalue":{"value":"The authors give a version for tripartite graphs of a classical theorem in extremal graph theory (for the Corr\u00e1di-Hajnal theorem see \\textit{K. Corr\u00e1di} and \\textit{A. Hajnal} [Acta Math. Acad. Sci. Hung. 14, 423-439 (1963; Zbl 0118.19001)]). Namely, given a tripartite graph \\(G\\) such that each vertex is adjacent to at least \\((2/3)N\\) vertices in each of the other classes, then either \\(G\\) contains a subgraph that consists of \\(N\\) disjoint triangles or \\(G\\) is a specific graph characterized by the authors with the property that each vertex is adjacent to exactly \\((2/3)N\\) vertices in each of the other classes. The proof is based in two main tools: the regularity lemma [\\textit{E. Szemer\u00e9di}, Colloq. Internat. CNRS, 399-401 (1978; Zbl 0413.05055)], and the blow-up lemma [\\textit{J. Koml\u00f3s, G. N. S\u00e1rk\u00f6zy} and \\textit{E. Szemer\u00e9di}, Combinatorica 17, 109-123 (1997; Zbl 0880.05049)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613547$0463937B-BA67-4FF9-8A43-52321244CF29","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613547$023291F2-6E98-4B9F-A611-18B5E845F84A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ae809c97ecaaf51d47d412a4b313f3ae25ba4682","datavalue":{"value":"1792465","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613547$7D7569F7-2524-41DB-BBE0-CDDA4CD29577","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a55ba5e5ae71e39cd2c561a862d90de0615e61","datavalue":{"value":"regularity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613547$18EB0703-6B6F-4BE5-90FB-3B317B80AD79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ef20359f878079a933a991ee5825605067b583","datavalue":{"value":"blow-up lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613547$279B39F0-A938-460F-95F1-9BC3510F6C6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4a5281e99be804d5374fe1dd42caa1019f564c6b","datavalue":{"value":{"entity-type":"item","numeric-id":298636,"id":"Q298636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613547$B98B6D19-C9EA-4B5B-B1DC-7425530F9059","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":"Q1613547$DE2EF5FE-627D-4B64-834F-B66B915A580D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65f4fb228c160cd1339693a54cfaa6077c20d70b","datavalue":{"value":{"entity-type":"item","numeric-id":2883851,"id":"Q2883851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6ed89379fcc8cc3cf6933808079f5278a1ebcc6a","datavalue":{"value":{"amount":"+0.8144437074661255","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":"Q1613547$22679B79-6EC7-4D70-A0BE-8312D9FFA65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0dc2d479f6089e0acebbce5a5f9e1e66ab8aa807","datavalue":{"value":{"entity-type":"item","numeric-id":1969796,"id":"Q1969796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22165dc8fa4f2e41c63fbeaece219b29dd25d402","datavalue":{"value":{"amount":"+0.8138400912284851","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":"Q1613547$0182B0A6-D96F-4D8C-B12F-9D90E7D9D4A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d709070cf44c0a1f96b7a66a96c06afd1e4294a7","datavalue":{"value":{"entity-type":"item","numeric-id":4962591,"id":"Q4962591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86242b5acd977d41d645ff7fae9c306ed9e2fd11","datavalue":{"value":{"amount":"+0.8130941987037659","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":"Q1613547$D776BF6E-CB7F-448F-B5B8-45ECC1A76B9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0958f79f69417b5262ac30e4c41543f8fdf6eca","datavalue":{"value":{"entity-type":"item","numeric-id":5264273,"id":"Q5264273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4073481da73f5ff3f156c7e29b39d1dc1c1d202","datavalue":{"value":{"amount":"+0.8074907660484314","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":"Q1613547$5F39CFB7-3725-49AB-BC4B-5B1C7112E78C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"06bebcb453422f3e84e72357db4ed8c9782eba01","datavalue":{"value":{"entity-type":"item","numeric-id":2857315,"id":"Q2857315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61ac447c5a49f3c9d3efcc0780668de170af5b1c","datavalue":{"value":{"amount":"+0.8035337924957275","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":"Q1613547$F0746D11-83F7-4975-BA31-4D43FE7FF8E7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tripartite version of the Corr\u00e1di-Hajnal theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tripartite_version_of_the_Corr%C3%A1di-Hajnal_theorem"}}}}}