{"entities":{"Q1422124":{"pageid":1432864,"ns":120,"title":"Item:Q1422124","lastrevid":70369362,"modified":"2026-04-13T14:18:41Z","type":"item","id":"Q1422124","labels":{"en":{"language":"en","value":"Matrix-free proof of a regularity characterization"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2038337"}},"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":"Q1422124$15676FEE-A652-4FA7-9621-2DD14B156508","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dba42c0de0f123f628370e3517341ec96e986c6d","datavalue":{"value":{"text":"Matrix-free proof of a regularity characterization","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1422124$24BC44A0-4DED-4986-8D90-35BB1EB961B5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bd78eb039aae1fff1f089edb8e751d6bcaf10ac6","datavalue":{"value":"1031.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422124$CF6FC49A-8966-44E8-AC13-8B6557FA234B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0388e62f4d88081ce76803cf2a865e606b73f162","datavalue":{"value":{"entity-type":"item","numeric-id":404437,"id":"Q404437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422124$71078F5D-F40E-492C-A777-62235061333B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"32c25fa8e627a607462b66f5901b2fab775a3c7c","datavalue":{"value":{"entity-type":"item","numeric-id":190558,"id":"Q190558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1422124$8A886EB5-0517-4AE0-8D41-9F1F92366D3C","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":"Q1422124$68BF3A1E-CB8D-4A3B-9803-4D4203C435D1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a4b42c06db7e24b19fc79361c42f9be31630ff05","datavalue":{"value":{"time":"+2004-02-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1422124$CC4DC68C-CC65-431D-B5D9-15D28629C7F0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a75e8b79ccd889654a1fbb67f6869b6eee1720c4","datavalue":{"value":"https://eudml.org/doc/123236","type":"string"},"datatype":"url"},"type":"statement","id":"Q1422124$D46ABFA6-21F1-4E96-901B-C5FEFC10A5B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"222590d4f5d40a5fe66d0eb93bc23f7a42a606bb","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_10/Abstracts/v10i1r39.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1422124$C837FEC3-7845-4A8D-BDFD-1B8F4903DE4B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"679891d57851be05689daf5611076675dfa7bbe1","datavalue":{"value":"Summary: The central concept in Szemer\u00e9di's powerful regularity lemma is the so-called \\(\\varepsilon\\)-regular pair. A useful statement of \\textit{N. Alon} et al. [J. Algorithms 16, 80-109 (1994; Zbl 0794.05119)] essentially equates the notion of an \\(\\varepsilon\\)-regular pair with degree uniformity of vertices and pairs of vertices. The known proof of this characterization uses a clever matrix argument.     This paper gives a simple proof of the characterization without appealing to the matrix argument of Alon et al. We show the \\(\\varepsilon\\)-regular characterization follows from an application of Szemer\u00e9di's regularity lemma itself.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422124$0D127836-80BE-460B-B0C7-2164FAD16EE1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422124$2106A248-13F8-4A65-9EA0-3F41AFD18D0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422124$D2E38599-3669-455F-994F-5DFBECF15B13","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"17c2c88c989fb1987e28e801e4b639c4ce84b42b","datavalue":{"value":"2038337","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422124$CFF70C3C-6905-426A-B4CD-D46BF4387117","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a55ba5e5ae71e39cd2c561a862d90de0615e61","datavalue":{"value":"regularity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1422124$3522F1CE-734F-4DD4-BDA2-D0DCAEAC6735","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":"Q1422124$A5C7D63E-D169-4A8D-8C7D-5B4BC0684A32","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"724252bbf932883f02f2a9c6c77c67d8a5415107","datavalue":{"value":"bafkreidko2hy2v7l5q3psmx2464mqjiipn5eogtpeyhqp7rk5qiy3risxu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1422124$C07952D7-5776-4F4B-9003-938AB65FE5F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e9c1bf468a148f311d71ce2c134ff4af97f23e2","datavalue":{"value":{"entity-type":"item","numeric-id":870053,"id":"Q870053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55974d5017557a96fe98e9a460c334a67fbdbd99","datavalue":{"value":{"amount":"+0.813279926776886","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":"Q1422124$122A0ABC-8A7D-46CE-B68E-75E49CDFC3D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"17eaa5c39d4a6d6820338bdd0e0ed1445ae94c8e","datavalue":{"value":{"entity-type":"item","numeric-id":2998854,"id":"Q2998854"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69eceb6182f86319a8f0c193e4812964d7a7d470","datavalue":{"value":{"amount":"+0.7912523746490479","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":"Q1422124$3EF057C8-1697-404E-9CC6-DAB420DF1543","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8ce85735fd5a33244ac2a1f7d4a4ad614b7954d","datavalue":{"value":{"entity-type":"item","numeric-id":3978309,"id":"Q3978309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d099ad05ce1adbe8de557a484e4185f2dece0296","datavalue":{"value":{"amount":"+0.7749081254005432","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":"Q1422124$4276013E-30B5-454D-AF83-B380F7E48566","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e488376537dc0371ffa0ebaac791aa3d1134636f","datavalue":{"value":{"entity-type":"item","numeric-id":4736881,"id":"Q4736881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11d8669022c77b9b884ed0b0cd882ab22e453cc0","datavalue":{"value":{"amount":"+0.7741274833679199","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":"Q1422124$172BAE31-275B-427B-A13C-300C0A27ED70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0db37eb8386581be72e4f87a879cc9b037b398","datavalue":{"value":{"entity-type":"item","numeric-id":682130,"id":"Q682130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b59bd2bd0691d052dbf26bdef5205b266cfbe35","datavalue":{"value":{"amount":"+0.772472083568573","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":"Q1422124$533BD71A-DCDE-4B77-9D78-5B7F1393787A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Matrix-free proof of a regularity characterization","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Matrix-free_proof_of_a_regularity_characterization"}}}}}