{"entities":{"Q879618":{"pageid":881466,"ns":120,"title":"Item:Q879618","lastrevid":55970749,"modified":"2026-02-21T15:27:17Z","type":"item","id":"Q879618","labels":{"en":{"language":"en","value":"Szemer\u00e9di's lemma for the analyst"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5152562"}},"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":"Q879618$624DAEC9-9918-4A7B-ABEB-6939C2121EEA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"81f67ed68bec0beac1a0f04030dc77f8fcf9b0f5","datavalue":{"value":{"text":"Szemer\u00e9di's lemma for the analyst","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q879618$07EE2274-D121-40D5-9FC0-E8B2C3015DCB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1ca40d27c025de81fcf6ab06446f35c00c06b88c","datavalue":{"value":"1123.46020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$EC5B08EB-CB35-4EAA-BF50-C0DC5E67DEA1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0a856556e52924da659ef4b62c37629292b38379","datavalue":{"value":{"entity-type":"item","numeric-id":233550,"id":"Q233550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879618$AD857194-9681-448A-8C23-00CE11E0C703","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"201364cbbc61e0d0a85431778d2e1c2e76306b69","datavalue":{"value":{"entity-type":"item","numeric-id":6480584,"id":"Q6480584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879618$F6A5756D-AC4A-477F-BF3C-BAB48A00379D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9f7ed99dde37a1ed2b712f0eb37bcc96b8743b93","datavalue":{"value":{"entity-type":"item","numeric-id":172246,"id":"Q172246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879618$0E3D3986-F421-4A8E-9C6B-6CE6F473425A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1a2af428023bb1f64e3e9e7c392bd08e7b812892","datavalue":{"value":{"time":"+2007-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q879618$891884B3-61C0-4402-B770-8C1FA1157C40","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"57035309c77e5639ee657097f29a42842f4b46d7","datavalue":{"value":"Szemer\u00e9di's regularity lemma was first used in his proof of the Erd\u0151s--Tur\u00e1n conjecture on arithmetic progressions; cf.\\ [\\textit{E.\\,Szemer\u00e9di}, Acta Arith.\\ 27, 199--245 (1975; Zbl 0303.10056)]. Roughly speaking, it asserts that every sufficiently large graph can be decomposed into smaller pieces so that the subgraph between them behaves random-like. Here, the authors present various reformulations of the lemma or its variants in the language of analysis.   The set-up is the Hilbert space \\(L^2[0,1]\\) and the (symmetric) kernel operators  \\[  (Wf)(x) = \\int_0^1 w(x,y)f(y)\\,dy,  \\]  normed by  \\[  \\| W\\| _{\\square} = \\sup_{S,T\\subset [0,1]} \\biggl| \\int_{S\\times T} w(x,y)\\,dx\\,dy \\biggr|. \\]  For matrices, this last norm is known as the cut-norm.   One way to restate the Szemer\u00e9di lemma in analytic terms is as follows. For every \\(\\varepsilon>0\\), there is an integer \\(k(\\varepsilon)>0\\) such that, for every symmetric measurable function \\(w: [0,1]^2 \\to [0,1]\\), there is a partition \\([0,1]=S_1\\cup\\dots\\cup S_k\\) into \\(k\\leq k(\\varepsilon)\\) sets of equal measure such that, for every \\(R\\subset [0,1]^2\\) that is a union of at most \\(k^2\\) measurable rectangles, one has  \\[  \\biggl| \\int_R (w-w_{\\mathcal P}) \\,dx\\,dy \\biggr| \\leq \\varepsilon,  \\]  where \\(w_{\\mathcal P}\\) is the conditional expectation of \\(w\\) for the partition \\([0,1]^2 = \\bigcup_{i,j=1}^k S_i\\times S_j\\) of \\([0,1]^2\\).  Other reformulations of Szemer\u00e9di's lemma involve a general result on approximation in Hilbert spaces or the compactness of a certain metric space defined by means of the cut-norm or coverings of \\([0,1]\\) with balls of small diameter for a certain metric.   The last section contains two applications, for example, a lower bound on the number of classes in the weak version of the Szemer\u00e9di lemma.  Reviewer's remark: A related paper is [\\textit{T.\\,Tao}, Contrib.\\ Discrete Math.\\ 1, No.\\,1, 8--28 (2006; Zbl 1093.05030)] that discusses Szemer\u00e9di's lemma from the perspective of probability theory.","type":"string"},"datatype":"string"},"type":"statement","id":"Q879618$DD029BA8-141D-4281-89E6-5B3F93AC6F64","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"098587d627d11b69ddd36652699d57f211999689","datavalue":{"value":{"entity-type":"item","numeric-id":203344,"id":"Q203344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q879618$85D0F409-344C-4CD5-BF8B-AA4EA4F0F834","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"52e0168162117eb8e8335cbb8d5acc37f04a4a3e","datavalue":{"value":"46C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$5B4AAB97-017D-4757-8872-EDE2F685ACE8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$44FFA600-C560-4198-A92B-0C0768B9FF2E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3bdede527e7c93b05c78b1a12910c9dbd0ee7efd","datavalue":{"value":"5152562","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$0632CB8F-925E-4B53-A1E0-9D48E2F1AEEE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1d9702cfceef978a63417db03c4a5f3c4c2afb1c","datavalue":{"value":"Szemer\u00e9di's regularity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q879618$B6DC1F53-7B6E-4AD6-9E24-0B51B563AC35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c2bb017ac4ad0d3b30fd08bfc4a3cb95102fc3","datavalue":{"value":"kernel operators on Hilbert spaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q879618$9764158E-DF0C-4531-AEB8-7CF0D34E9056","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7abf6b0afbeceb151095e68e3d98baee383a9ec3","datavalue":{"value":"cut-norm","type":"string"},"datatype":"string"},"type":"statement","id":"Q879618$E6F26CD1-FE00-451B-B33E-E93B8E4A206F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3d9aaf408fcecf2d8bcf4f143878a2715740dbd1","datavalue":{"value":"Q105583448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$5EA67084-201D-4298-BF16-42EE86E88809","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":"Q879618$B0B49529-EAB9-453F-8A96-A97B99CA613E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee02a10424969d0fbeafa0687af6caaeb4d1e2aa","datavalue":{"value":"https://doi.org/10.1007/s00039-007-0599-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q879618$C4879999-7CFE-4788-B34A-38E36962D61D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"25dc269847408ccd9a7de3337bd4260b105cd1ae","datavalue":{"value":"W2068571612","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$80E0467A-50E8-439C-896B-3038647184C0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9dcc35f93e6f3e1b8c3c8ab297c9138bd80e7f55","datavalue":{"value":"10.1007/S00039-007-0599-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q879618$ABB08A35-499B-4C59-8FE2-2B28277C0EFB","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2da4c163a31e83887f9f2e3c655ff9d92b9bff3","datavalue":{"value":{"entity-type":"item","numeric-id":5480762,"id":"Q5480762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a56e899911c6940933a319f56bb186de4bc0fc7","datavalue":{"value":{"amount":"+0.8180705308914185","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":"Q879618$029A6CD0-38A8-441B-8AB7-F788BBDF8A3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"507bd99b9f71c53d3e41a356f06a520e549eb5a7","datavalue":{"value":{"entity-type":"item","numeric-id":3601922,"id":"Q3601922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65d2639947ff01070db89580dcfadfaf2f3d01ab","datavalue":{"value":{"amount":"+0.7973484992980957","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":"Q879618$3BE517DB-FBEE-4782-8B7D-EF2EB04143C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40c2ab75b715bac454353c6543b612baf7e6d97f","datavalue":{"value":{"entity-type":"item","numeric-id":311501,"id":"Q311501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c68fd4c34a80dee0fa1f6ad8e9ef219370305f6c","datavalue":{"value":{"amount":"+0.7959038019180298","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":"Q879618$009BCB4B-F7CE-4AC2-9074-E6201F25F404","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:879618","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:879618"}}}}}