{"entities":{"Q682130":{"pageid":683979,"ns":120,"title":"Item:Q682130","lastrevid":63554967,"modified":"2026-04-11T13:57:13Z","type":"item","id":"Q682130","labels":{"en":{"language":"en","value":"A short proof of Gowers' lower bound for the regularity lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6837910"}},"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":"Q682130$F82FC0CA-2AFC-4465-BAE4-C8CCF191E972","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3aa01e42865a97aa540cf94993bf97e4a830cd49","datavalue":{"value":{"text":"A short proof of Gowers' lower bound for the regularity lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q682130$791D3D3D-DA40-4845-8D33-71067F98B3CD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"288cb1aab25ed311655b7cb4feae53c73354c250","datavalue":{"value":"1399.05128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$47847C8F-447B-4050-93BA-A263A8FF3C9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"44e9e4fb1ffea89d93d9a942b67bf5a451785b67","datavalue":{"value":{"entity-type":"item","numeric-id":682129,"id":"Q682129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682130$1F64BE03-9BD4-4FA9-8A43-D6107D86196D","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":"Q682130$233C46D5-44DD-4EC4-92B1-90B4FC88A046","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":"Q682130$D38F77AE-99F4-4A84-88FD-28F2500384C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ee53210b31b3a9f4fe71da2550e4c06c4d383198","datavalue":{"value":{"time":"+2018-02-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q682130$A163FB84-8F99-402D-8CAE-1F39A0A780FE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"223a331df3c1d829cc5fc82a5732fc9f970ddbfe","datavalue":{"value":"https://arxiv.org/abs/1308.5352","type":"string"},"datatype":"url"},"type":"statement","id":"Q682130$AA695670-9630-435F-A460-329A8E10BC62","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"91b7e30979cad9bddb5a927ba61f9941736b57cf","datavalue":{"value":"Let \\(A\\) and \\(B\\) be two vertex sets in a graph \\(G\\) and let \\(e(A,B)\\) be the number of edges \\(uv\\) such that \\(u \\in A\\) and \\(v \\in B\\). Define \\(d_G(A,B)=e(A,B)/| A| | B| \\). The pair \\((A,B)\\) is said to be \\(\\varepsilon\\)-regular if \\(| d_G(A,B)-d_G(A',B')| \\leq \\varepsilon\\) for all \\(A' \\subseteq A\\) and \\(B' \\subseteq B\\) satisfying \\(| A'| \\geq \\varepsilon | A| \\) and \\(| B'| \\geq \\varepsilon | B| \\). A partition \\(\\mathbb{Z} = \\{\\mathbb{Z}_1, \\ldots,\\mathbb{Z}_k\\}\\) of the vertex set of a graph is called an equipartition of order \\(k\\) if all the sizes of the sets \\(\\mathbb{Z}_i\\) differ by at most 1. Szemer\u00e9di's regularity lemma asserts that, for every \\(\\varepsilon > 0\\), there is \\(M=M(\\varepsilon)\\) such that every graph has an \\(\\varepsilon\\)-regular equipartition of order at most \\(M\\). The original proof only showed that \\(M(\\varepsilon) \\leq \\mathrm{twr}(O(1/\\varepsilon^5))\\), where twr\\((x)\\) is a tower of exponents of height \\(x\\). In [\\textit{T. Gowers}, Geom. Funct. Anal. 7, No. 2, 322--337 (1997; Zbl 0876.05053)], two lower bounds were given. The first bound \\(M(\\varepsilon) \\geq \\mathrm{twr}(\\frac{1}{4}\\log (1/\\varepsilon))\\) was obtained by an inductive construction. The second bound \\(M(\\varepsilon)\\geq \\mathrm{twr}(1/\\varepsilon^c)\\), where \\(c=1/16\\), was established with more complicated construction and significantly involved proof of correctness. The main contribution of this paper is a new proof of the second bound, with \\(c= 1/6\\), using an inductive approach very similar to the proof of the first bound of Gowers. The proofs differ in several subtle aspects so that the inductive argument can be executed \\(1/\\varepsilon^c\\) times instead of \\(\\log (1/\\varepsilon)\\) times.","type":"string"},"datatype":"string"},"type":"statement","id":"Q682130$D5FD847F-9054-4B33-A0C6-EBF6E7466D1A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$604FDD5F-862F-4514-884E-2D25B54B1277","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b02a47bb3e6ffda6ae8940845178eca3854c8d36","datavalue":{"value":"05D99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$B56E5775-C36D-4339-BCBF-91899C5D416B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c593020416696d38602925a6c49f61fabc447704","datavalue":{"value":"6837910","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$757778E6-40BF-4725-A37F-27CAF623DA8F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a55ba5e5ae71e39cd2c561a862d90de0615e61","datavalue":{"value":"regularity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q682130$B23E92D0-41E2-4914-9E23-9EE666201580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a2f70062d99b0e42c0e79b77a5a32351affd9cf","datavalue":{"value":"equipartition","type":"string"},"datatype":"string"},"type":"statement","id":"Q682130$7B7911C9-47F3-4A4D-9187-00DF4863B33C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9e9841f0cb63c1bdf82f03ad3bb8cb0b9eadf7a","datavalue":{"value":"tower of exponents","type":"string"},"datatype":"string"},"type":"statement","id":"Q682130$6083CC1F-D396-4731-B988-544B8BA39FE4","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":"Q682130$6D334F2F-A253-464C-A488-DF3DC7C9AD60","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"56ef1494ec6a91208de5500ce120ad231a82ed0f","datavalue":{"value":"W2160594140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$6484A3BB-81E1-440D-B2AA-0CC68B90116C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e7eef8a759a0fdbc4cd005b6fab0ee7b9a4c2111","datavalue":{"value":"Q124990088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$EA318EE1-4759-4A89-A8CF-ECC7696BD4A7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d22890ff53d4de721bfc54ce199de1c59be420d","datavalue":{"value":{"entity-type":"item","numeric-id":1930904,"id":"Q1930904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682130$51066498-84BE-4C24-8B9D-40C097FC6315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe8baecfc04675db06c9a7aa8134ee8db9a22a91","datavalue":{"value":{"entity-type":"item","numeric-id":1355452,"id":"Q1355452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682130$E53FCBCB-C932-4D60-87B3-E26F9889A119","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q682130$1998FEEC-2EB9-4BA9-A0C8-B9671856B97C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a525db764a7258a0fe9cae031846b35a9fa5e078","datavalue":{"value":"10.1007/S00493-014-3166-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q682130$D8928037-9ABD-444A-AC86-315F9BF5E20B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f50a8df2486a1abf1f44a869000816e5a768698c","datavalue":{"value":{"entity-type":"item","numeric-id":1355452,"id":"Q1355452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dc62b0cdce7f0e82918b4ba3f5c732d822746e7","datavalue":{"value":{"amount":"+0.8537166714668274","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":"Q682130$1797F394-0B99-4E88-8C3E-759357D8F2DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcc8fc1eba22de8edf206666e5296622f7435ea4","datavalue":{"value":{"entity-type":"item","numeric-id":1930904,"id":"Q1930904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68e176e16c12a7ed2e40d621fccf3dc6bfb5d946","datavalue":{"value":{"amount":"+0.8501504063606262","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":"Q682130$0751D905-DEFC-49CE-8083-3DF5A1652C44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0142951ada09087aa33ac7e65a08d08bf95010","datavalue":{"value":{"entity-type":"item","numeric-id":1714948,"id":"Q1714948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"042f04d5769b29b0099fc12bc2e56c60f673e058","datavalue":{"value":{"amount":"+0.832303524017334","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":"Q682130$80ECA4C0-93A3-4C21-9270-F35F0C828760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c01beacf98d5fd30c20b79acc66edcbc97fb049","datavalue":{"value":{"entity-type":"item","numeric-id":2334614,"id":"Q2334614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"042f02c37094de4e4cb24dfc551900dfbd51210c","datavalue":{"value":{"amount":"+0.8230372667312622","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":"Q682130$0141F12D-3A79-4E1B-A19D-2052C10C12CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67d99e2e72ae1a3fa05fe169271155e8a864248b","datavalue":{"value":{"entity-type":"item","numeric-id":4920227,"id":"Q4920227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"432aadfc67caf7eedc5928c4fabbf73d2f2c29e2","datavalue":{"value":{"amount":"+0.8035650849342346","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":"Q682130$3644520E-30D1-419C-8595-99FE0E87F891","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A short proof of Gowers' lower bound for the regularity lemma","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_short_proof_of_Gowers%27_lower_bound_for_the_regularity_lemma"}}}}}