{"entities":{"Q2380453":{"pageid":2391196,"ns":120,"title":"Item:Q2380453","lastrevid":73763031,"modified":"2026-04-14T17:11:05Z","type":"item","id":"Q2380453","labels":{"en":{"language":"en","value":"Dense \\(H\\)-free graphs are almost \\((\\chi (H)-1)\\)-partite"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5687003"}},"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":"Q2380453$A439C0AD-F67A-430C-A1F5-61EC2FCB7174","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ccc5e022d681768a3014228cbdd070a5ecdd59d","datavalue":{"value":{"text":"Dense \\(H\\)-free graphs are almost \\((\\chi (H)-1)\\)-partite","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2380453$68FBBF5C-9C85-410A-BC7F-FF7F7E8D3043","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f41a64c1cf87ce34451d3ea82dc9847edcc0ed52","datavalue":{"value":"1215.05090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380453$C48E5978-AAA1-4B98-BDCD-AF09E545CA8B","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":"Q2380453$F27322FB-B97F-42EB-ABF8-A9A6AA128789","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":"Q2380453$7A927010-079B-49D4-BED6-04C91F155C2F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"143e8774a45e663375c24b3b343519cf2933b18c","datavalue":{"value":{"time":"+2010-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2380453$C3884CF9-8966-42DD-8044-4B4C284A783D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"85b205646f282895116f9b71e242d3127503593c","datavalue":{"value":"https://arxiv.org/abs/0907.3815","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380453$E0CB5495-BB44-449E-836A-B5A8DC2021D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5a52163d2ef74e396147199e2f721aeaaa971d11","datavalue":{"value":"https://eudml.org/doc/229553","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380453$9812A91D-B076-40F6-886F-FEE42050AC0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7fd15368255448806e54d4425e17f89275b4e200","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r21.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q2380453$529E077D-2CD7-4F1B-B2EA-16BD5FD95655","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"665afddddaf16746e95a25d13a3a5a148612eeaf","datavalue":{"value":"Summary: By using the \\textit{E. Szemer\u00e9di} regularity lemma [``Regular partitions of graphs,'' Probl\u00e8mes combinatoires et th\u00e9orie des graphes, Orsay 1976, Colloq. int. CNRS No. 260, 399--401 (1978; Zbl 0413.05055)]; \\textit{N. Alon} and \\textit{B. Sudakov} [Electron. J. Comb. 13, No. 1, Research paper R19, 9 p. (2006; Zbl 1085.05036)] recently extended the classical \\textit{B. Andrasfai}, \\textit{P. Erd\u0151s} and \\textit{V. T. S\u00f3s} theorem [Discrete Math. 8, 205--218 (1974; Zbl 0284.05106)] to cover general graphs. We prove, without using the Regularity Lemma, that tiic following stronger statement is true.   Given any \\((r+1)\\)-partite graph \\(H\\) whose smallest part has \\(t\\) vertices, there exists a constant \\(C\\) such that for any given \\(\\varepsilon> 0\\) and sufficiently large \\(n\\) the following is true. Whenever \\(G\\) is an \\(n\\)-vertex graph with minimum degree  \\[ \\delta(G)\\geq \\Biggl(1-{3\\over 3r-1}+ \\varepsilon\\Biggr)\\,n, \\]  either \\(G\\) contains \\(H\\), or we can delete \\(f(n,H)\\leq Cn^{2-{1\\over t}}\\) edges from \\(G\\) to obtain an \\(r\\)-partite graph. Further, we are able to determine the correct order of magnitude of \\(f(n,H)\\) in terms of the Zarankiewicz extremal function.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2380453$6B20BD1D-820A-472E-BBF5-494133DD3D35","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380453$11A4FEA0-BD91-47C5-9F35-AC42AD8A8AAC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bf75d5661920299c34229678e5bf6ce262ba28e5","datavalue":{"value":"5687003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380453$B609492A-48D4-42C7-8D04-7A005E309B2F","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":"Q2380453$34F11372-276A-4C90-8C18-74AFA1D0CD46","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"8783bd17410b539baef2015618d11fc61121e78f","datavalue":{"value":"bafkreifwqnsn3nlfnojtdaohq6tf6cx4po3bzors5wp2oyebrk35qwgpwu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2380453$07B36EFA-86EC-41E3-8C13-3CC833452424","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0eef9c13974daaba27a8d7599c7dd7dbccf382ea","datavalue":{"value":{"entity-type":"item","numeric-id":819178,"id":"Q819178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b890a0b9249a9c4a7a54274e2581a4bdfc3c309d","datavalue":{"value":{"amount":"+0.8636463284492493","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":"Q2380453$173EF7D4-550C-4332-AC05-D4133D93A012","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16be3e62b62a3eb6c12f7780a1d100f97315b9f6","datavalue":{"value":{"entity-type":"item","numeric-id":4987252,"id":"Q4987252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cdef9a1de09991c50ad7bcc3252cba8c930607d","datavalue":{"value":{"amount":"+0.8108789920806885","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":"Q2380453$E1DAC716-56FC-4508-A3F1-211F0D82E82D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce007c1463ca0920ef39d0316c2000a9899b7846","datavalue":{"value":{"entity-type":"item","numeric-id":858147,"id":"Q858147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86e984ba31629977dbdf01bee579ee1d7a7ab1d0","datavalue":{"value":{"amount":"+0.8076779842376709","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":"Q2380453$66A3C264-CF14-400B-A16F-02B8B22CE1ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0d370abc690d8df2fd572079de8e36af47129c","datavalue":{"value":{"entity-type":"item","numeric-id":5954318,"id":"Q5954318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dd044eb82846d65b64c68520ca95c0008dc653fb","datavalue":{"value":{"amount":"+0.8052976131439209","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":"Q2380453$DF24D72A-2A9D-434B-8ECA-449E386ACF1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a104e209a09e0b3099cdbb86f6ed6f6e8a37fb7","datavalue":{"value":{"entity-type":"item","numeric-id":2583671,"id":"Q2583671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"58af4895efacfa1d116041790b0396fcf2c05141","datavalue":{"value":{"amount":"+0.8049971461296082","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":"Q2380453$8FF6FD75-0D01-4127-994C-1FC3D1356EB7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Dense \\(H\\)-free graphs are almost \\((\\chi (H)-1)\\)-partite","badges":[]}}}}}