{"entities":{"Q870053":{"pageid":871901,"ns":120,"title":"Item:Q870053","lastrevid":50048614,"modified":"2026-01-12T19:26:39Z","type":"item","id":"Q870053","labels":{"en":{"language":"en","value":"A characterization for sparse \\(\\varepsilon\\)-regular pairs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5132838"}},"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":"Q870053$02785888-1923-4BD2-A5C6-0A3C7737DF58","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2fffbaff87fd19567e83a51a43f28d99f6d3084e","datavalue":{"value":{"text":"A characterization for sparse \\(\\varepsilon\\)-regular pairs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q870053$9FE3C240-29AE-4A98-A40D-E643676E4B09","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"77d650213445b74daf4463605753fec83621976e","datavalue":{"value":"1112.05089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870053$685A22A8-6908-4420-9029-7C88E4EDB0D9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34a5646eb9fce14667f2fce60d983d8ccfb2f1e7","datavalue":{"value":{"entity-type":"item","numeric-id":501983,"id":"Q501983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870053$EF533187-C934-483E-B896-370457E9E6FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a7b1b74b045e21f161107ae2d1ec32cd3fa125c","datavalue":{"value":{"entity-type":"item","numeric-id":173496,"id":"Q173496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q870053$3CC62F8D-FC57-4BFF-B2D7-F54EB5B634CE","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":"Q870053$B34FD028-33AA-4D1B-912A-3AF920FF1AA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"39eed756ef4774638f5dc70a5b404d4f34900328","datavalue":{"value":{"time":"+2007-03-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q870053$19CDF4F4-C53B-4B60-93EC-3C44E9532B5E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2305dade27463f055625771483477b0851ff12f3","datavalue":{"value":"https://eudml.org/doc/127342","type":"string"},"datatype":"url"},"type":"statement","id":"Q870053$0C325A32-3D1D-47E7-9248-203C6FB54B63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"6578b0a9ae1602c301911e456c49321cc92946c8","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r4.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q870053$AA8C6424-E2DD-4E23-A621-2470D180DF39","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"283854379f9174fecf3eecb52454e91d528e1eac","datavalue":{"value":"Summary: We are interested in (\\(\\varepsilon\\))-regular bipartite graphs which are the central objects in the regularity lemma of Szem\u00e9redi for sparse graphs. A bipartite graph \\(G=(A\\uplus B,E)\\) with density \\(p=|E|/(|A||B|)\\) is (\\(\\varepsilon\\))-regular if for all sets \\(A'\\subseteq A\\) and \\(B'\\subseteq B\\) of size \\(|A'|\\geq \\varepsilon|A|\\) and \\(|B'|\\geq \\varepsilon |B|\\), it holds that \\(|e_G(A',B')/(|A'||B'|)- p| \\leq \\varepsilon p\\). In this paper we prove a characterization for (\\(\\varepsilon\\))-regularity. That is, we give a set of properties that hold for each (\\(\\varepsilon\\))-regular graph, and conversely if the properties of this set hold for a bipartite graph, then the graph is \\(f(\\varepsilon\\))-regular for some appropriate function \\(f\\) with \\(f(\\varepsilon)\\to 0\\) as \\(\\varepsilon\\rightarrow 0\\). The properties of this set concern degrees of vertices and common degrees of vertices with sets of size \\(\\Theta(1/p)\\) where \\(p\\) is the density of the graph in question.","type":"string"},"datatype":"string"},"type":"statement","id":"Q870053$28EC7893-2F90-4A4B-AB9A-D03D2FC23732","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870053$6B461284-D9FD-410A-8207-3F11262F1983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870053$F4DFA5AD-1716-4890-BAD2-4DD24152A2CD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aac07f6a1e1c644dc34bc5ebe7811144c208f9f1","datavalue":{"value":"5132838","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870053$9EE68DE9-CFFD-49AD-8663-86554E89272D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1a55ba5e5ae71e39cd2c561a862d90de0615e61","datavalue":{"value":"regularity lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q870053$35C04D95-54B8-42EB-B6F7-2F51656E5C19","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":"Q870053$8EFD1396-4718-4BBA-87B1-CC8AB04DE3CD","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"d2c2d69add60486d696c8a4a9c267208c99cefb8","datavalue":{"value":"bafkreiazgp3xmvthxazg2yokkone6e75eppr3wrpmwru5fom5hkzoetgdy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q870053$E9E86D6C-0CBD-4FCA-B7A4-84ED0AE537B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ec648fe870879b15fe24f7f85fa099f0f2593d2b","datavalue":{"value":{"entity-type":"item","numeric-id":4419289,"id":"Q4419289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f9585faba8277f2e2c72cb0838c6fa6277f6d295","datavalue":{"value":{"amount":"+0.8680711388587952","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":"Q870053$A4A15A92-A636-4856-9852-3BFA8014F6D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a433d2f0e079fda94cc09909425c9aec5ccb34c8","datavalue":{"value":{"entity-type":"item","numeric-id":1422124,"id":"Q1422124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94962ae8cd504ddd38cf42bebed9202de0d1e3a2","datavalue":{"value":{"amount":"+0.8677552938461304","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":"Q870053$EC699725-3390-4FB9-A382-FC4D92BB4FED","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":"f2ad80b7c4b50b2be6cdb93b33e78aadf8a12632","datavalue":{"value":{"amount":"+0.8505285382270813","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":"Q870053$3DE66439-6AC7-4BB4-A511-F7B6F9B10B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f8ebeea2074d65af2bbcfe003ba1fd99b698c82","datavalue":{"value":{"entity-type":"item","numeric-id":4407452,"id":"Q4407452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9eb0ece049382603af6ba3ac36892503f78eb92f","datavalue":{"value":{"amount":"+0.8503577709197998","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":"Q870053$F03D4A86-FDFE-43D5-959B-0C5A4ED479FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a3b96879479be07076b7638365b5f72544db209","datavalue":{"value":{"entity-type":"item","numeric-id":858679,"id":"Q858679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9707b76225eaa99c489dd047c270d906b227146b","datavalue":{"value":{"amount":"+0.8315105438232422","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":"Q870053$5C88A202-B52A-4A91-949D-0DF62CA7EFAF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:870053","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:870053"}}}}}