{"entities":{"Q1964595":{"pageid":1975337,"ns":120,"title":"Item:Q1964595","lastrevid":43448756,"modified":"2025-07-25T23:05:08Z","type":"item","id":"Q1964595","labels":{"en":{"language":"en","value":"Perfect matchings in \\(\\varepsilon\\)-regular graphs and the blow-up lemma"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1404393"}},"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":"Q1964595$B2CFB183-CDEA-4ABE-8A5D-60156794FB0E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"31c6fe1b157c6fbac734e08eadddbbbbeb75534d","datavalue":{"value":{"text":"Perfect matchings in \\(\\varepsilon\\)-regular graphs and the blow-up lemma","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1964595$0C920FB4-2095-470A-970B-C7920CED4CD7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0240a9e1032073b64aea589d5e31b1297669363e","datavalue":{"value":"0932.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964595$7255D249-E1A1-4230-8C46-C85663EA4E69","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":"Q1964595$9298D603-E80D-4C19-9C01-986CE7B02327","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b17fbfec200bcf11c37dd1a72a5e177de6557760","datavalue":{"value":{"time":"+2000-02-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1964595$00C8FA8A-CCF3-4630-A220-CC3D24803AFD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f4ce22b385491d560ece834a159cbf57a857a08c","datavalue":{"value":"Let \\(G\\) be a graph with two disjoint subsets \\(A\\), \\(B\\) of its vertices, with cardinalities \\(a\\) and \\(b\\), respectively. The number of edges between \\(A\\) and \\(B\\) divided by \\(ab\\) is the density of the pair \\(A\\), \\(B\\). A bipartite graph with bipartition \\(U\\), \\(V\\), \\(|U|=|V|=n\\) is \\(\\varepsilon\\)-regular if for any pair of sets \\(A\\subset U\\) and \\(B \\subset V, |A|, |B|> \\varepsilon n\\), the densities of the pairs \\(A\\), \\(B\\) and \\(U\\), \\(V\\) differ by at most \\(\\varepsilon\\). If all the vertices of such an \\(\\varepsilon\\)-regular graph \\(G\\) with density \\(d>2\\varepsilon\\) have degrees not too far from \\(d\\) then \\(G\\) is known to have about as many perfect matchings as the corresponding random bipartite graph, that is, about \\(d^n n!\\). In the paper this result is utilized to prove that with probability quickly approaching one, a perfect matching drawn randomly from \\(G\\) is spread evenly, in the sense that for any large subsets of vertices \\(A\\subset U\\) and \\(B \\subset V\\), the number of edges of the matching spanned between \\(A\\) and \\(B\\) is close to \\(|A||B|/n\\). As an application an alternative proof of the blow-up lemma of \\textit{J. Koml\u00f3s, G. N. S\u00e1rk\u00f6zy} and \\textit{E. Szemer\u00e9di} [Combinatorica 17, No. 1, 109-123 (1997; Zbl 0880.05049)] is given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964595$DC5AD04D-EDA8-4CD8-9DA6-217C2C898443","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964595$DF6ED9D5-75CF-4F57-891F-429B579C16D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964595$ED484D70-1F85-42AC-B557-8BEBA490549F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"32fee5c9843c40862dafad022165bf6548eec8f9","datavalue":{"value":"1404393","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964595$28306C61-223A-4EE4-91FF-AA96FD0C52A4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17947e1c61570c11c96440abffe6455cc560f6f1","datavalue":{"value":"\\(\\varepsilon\\)-regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964595$59E419C2-6F93-4B3F-965A-359CDC58E289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0ef20359f878079a933a991ee5825605067b583","datavalue":{"value":"blow-up lemma","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964595$1D77CF5A-AD03-4213-8B3A-F21285168252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1964595$5E09BEA7-2469-40C0-88CC-45005FC93718","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"260c786eb881e5a0588a9cb9c21f3fc1a631bf21","datavalue":{"value":"Q105584593","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964595$A77B3718-E3B6-4043-A288-F5DE9A9FFC3F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c36b77bffff6f43e669d0380d3493f37a56849f","datavalue":{"value":{"entity-type":"item","numeric-id":168591,"id":"Q168591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964595$25875764-3781-4673-AD66-57ECDC40E3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dc0952d447fed38177fb32bd92c2d18011c79ac","datavalue":{"value":{"entity-type":"item","numeric-id":226978,"id":"Q226978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1964595$B3842293-591B-4A65-A0BA-E1C8E47C4A84","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":"Q1964595$FE8F27A3-D80E-4CFD-B11F-B8E02E921BBF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3298f7c5ff9c288ca31b48acf1dbed50d6384ec5","datavalue":{"value":"https://doi.org/10.1007/s004930050063","type":"string"},"datatype":"url"},"type":"statement","id":"Q1964595$0608AA8A-46B2-45FF-A8C8-9844C8DACE72","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a85272cd1183f1a9ac9792e54a842687666a03cf","datavalue":{"value":"W2010512224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964595$8CC45C32-5CF0-4785-8564-6B4352C3536C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd0768ac8ee86df811722fbf9896c19e50d73946","datavalue":{"value":"10.1007/S004930050063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1964595$4521974F-4117-4997-A9D7-7BC906AE8EBA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43161900791d6926b3a5bd9a0a54ec93c606281a","datavalue":{"value":{"entity-type":"item","numeric-id":2784462,"id":"Q2784462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a701a1a6223167acad2a4f0d4ce26e14f61ebe79","datavalue":{"value":{"amount":"+0.89118946","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$190C8B66-E112-4AB1-86B2-FDDB9B3E9B1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e80e2c2fc54c49453cfe69dfcf1499e7494ccc2c","datavalue":{"value":{"entity-type":"item","numeric-id":4240605,"id":"Q4240605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f37f86e7af72de25fe697d6cfb018b090092009","datavalue":{"value":{"amount":"+0.7781349","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$1E98EA6E-8226-42F3-AA23-2F3A33604B73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6d2b25d9a11480421877b73fc384389fe50328b","datavalue":{"value":{"entity-type":"item","numeric-id":4247195,"id":"Q4247195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0b422403e595542285308adf970dd197bb01271","datavalue":{"value":{"amount":"+0.7726488","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$260E0FDC-52F8-4BF1-A82B-8DDF4FEB213A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41429a84489474de8958b4966b5e91d86b0ffb0c","datavalue":{"value":{"entity-type":"item","numeric-id":4459590,"id":"Q4459590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e2bddea2259a4b2e11e05c25589a46ec490717da","datavalue":{"value":{"amount":"+0.7704939","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$4C24704D-019E-4F6B-94BE-129110E360E7","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":"fa094b656226d215eb731ec6b9cc2e5d0b4a937f","datavalue":{"value":{"amount":"+0.7553092","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$7977B6A5-FE8C-4D5B-A47F-373EE1ACCC74","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"563b6970c0866109b3e5a51b48f2820b175a03c7","datavalue":{"value":{"entity-type":"item","numeric-id":5443799,"id":"Q5443799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e896f474222f9a38ba8dcd9d9b2ce0e187843af","datavalue":{"value":{"amount":"+0.7534219","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$CE355EB9-02C8-4796-8254-A10D4BD46556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d505e3fed8db527daa58a8e031c0bb2f5602f0de","datavalue":{"value":{"entity-type":"item","numeric-id":1953449,"id":"Q1953449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe3a278cf6023cb87a0a6cfce713937690c8b1e1","datavalue":{"value":{"amount":"+0.74455583","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$3BE06E32-BB81-4AA5-B906-1E9B1E452524","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":"9bbe1617c265b9b7c1e28827037de299b7f74274","datavalue":{"value":{"amount":"+0.73714674","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$78020099-8D4C-44A7-8F2B-52CED6708FF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9890cba9f51f3e04fcc383fe7853405a25672f6","datavalue":{"value":{"entity-type":"item","numeric-id":4508359,"id":"Q4508359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"215876fc29e288d753e5bee7d3c9e0c8ca8ea545","datavalue":{"value":{"amount":"+0.7366067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1964595$D05859EE-D826-4697-BC80-60D14218BB92","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1964595","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1964595"}}}}}