{"entities":{"Q2335698":{"pageid":2346441,"ns":120,"title":"Item:Q2335698","lastrevid":71876463,"modified":"2026-04-14T01:07:29Z","type":"item","id":"Q2335698","labels":{"en":{"language":"en","value":"Uniform generation of spanning regular subgraphs of a dense graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7130514"}},"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":"Q2335698$86CC725E-9722-4271-BB86-B0E473FF2815","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5f9f4e5e0e41c7d6f8551663dde150bdd8612976","datavalue":{"value":{"text":"Uniform generation of spanning regular subgraphs of a dense graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2335698$48076756-CD33-47D7-A438-6255E9684D8E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a7c4983dad4a9ecdf8239dfd4ec99927297842d","datavalue":{"value":"1427.05218","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$E50785B4-0BF8-47D1-8F15-099F775B2E61","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"85c7cdc38c1121cd0c2fdca7a462bc31f19a589d","datavalue":{"value":{"entity-type":"item","numeric-id":427799,"id":"Q427799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$CED4DAD4-640C-446C-BADA-BC270D890FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4e5fed75436711fae9c159f3931462760a8b85f","datavalue":{"value":{"entity-type":"item","numeric-id":311512,"id":"Q311512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$62FBF8F6-A7DA-4CD1-81C5-4D8674B18507","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":"Q2335698$737262B8-E808-457F-AA33-63E5B0E91353","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c607cca1c7fb39fdf5e1f1040f681790eb7d8faa","datavalue":{"value":{"time":"+2019-11-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2335698$C6CC17AF-441E-48CD-BD81-3BDBB49B6C07","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"dcf0fa3176c210e9cb4dd4d9a0f6e7d5b8c16078","datavalue":{"value":"https://arxiv.org/abs/1807.00964","type":"string"},"datatype":"url"},"type":"statement","id":"Q2335698$35C80418-CB85-4EAE-8055-84CDBDDCCD55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"66f03a9a0bc21d4919fa44a1b3da94c45194b47d","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p28","type":"string"},"datatype":"url"},"type":"statement","id":"Q2335698$7D992490-6D0F-4D46-85D9-9B7E8FFE7801","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0ccc4752e4cec1bcf59428d9fe2e5735fcb3ac9a","datavalue":{"value":"Summary: Let \\(H_n\\) be a graph on \\(n\\) vertices and let \\(\\overline{H_n}\\) denote the complement of \\(H_n\\). Suppose that \\(\\Delta = \\Delta(n)\\) is the maximum degree of \\(\\overline{H_n}\\). We analyse three algorithms for sampling \\(d\\)-regular subgraphs \\((d\\)-factors) of \\(H_n\\). This is equivalent to uniformly sampling \\(d\\)-regular graphs which avoid a set \\(E(\\overline{H_n})\\) of forbidden edges. Here \\(d=d(n)\\) is a positive integer which may depend on \\(n\\).  Two of these algorithms produce a uniformly random \\(d\\)-factor of \\(H_n\\) in expected runtime which is linear in \\(n\\) and low-degree polynomial in \\(d\\) and \\(\\Delta\\). The first algorithm applies when \\((d+\\Delta)d\\Delta = o(n)\\). This improves on an earlier algorithm by the first author [Graphs Comb. 30, No. 3, 581--589 (2014; Zbl 1294.05108)], which required constant \\(d\\) and at most a linear number of edges in \\(\\overline{H_n}\\). The second algorithm applies when \\(H_n\\) is regular and \\(d^2+\\Delta^2 = o(n)\\), adapting an approach developed by the first author together with Wormald. The third algorithm is a simplification of the second, and produces an approximately uniform \\(d\\)-factor of \\(H_n\\) in time \\(O(dn)\\). Here the output distribution differs from uniform by \\(o(1)\\) in total variation distance, provided that \\(d^2+\\Delta^2 = o(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2335698$7AF3C672-707C-46E3-96B6-6BE63F5BE853","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$ECFC4061-CAEA-45B1-A8FC-0E38D027DEC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cf979f4acdc6dac710cfd0a80dde6754b28a9043","datavalue":{"value":"05C42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$B53AA214-9B68-46D4-A3AE-481EA17CFC76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$B730C4D6-9774-4D4A-8E20-59A0317E26EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e01671c873d801b913451010c0981a684c101d40","datavalue":{"value":"68W20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$D4CF9435-315C-4A70-A5F5-30994112D6D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$3CEB1B4D-043C-4828-81E3-FBA7483B20E3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"bdc69792db358819c1a2d570f4733cd4318fd00f","datavalue":{"value":"7130514","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$CAEC9F1C-4C58-40DA-84B0-93AAB65151D6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dbccb68ff244ccbcfc8d09e9961d418e11becebd","datavalue":{"value":"uniform generation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2335698$31F7BD74-C6E9-4683-8001-574B9AFA3292","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2335698$6DCCBF06-C7BD-4F53-A49A-D2B79537DC9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5411be567ca5e94362fe7878e378973b4d660f8","datavalue":{"value":"\\(d\\)-factors","type":"string"},"datatype":"string"},"type":"statement","id":"Q2335698$09350905-FFFA-4AFF-83A8-9B64A99ED9F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ff543de71b6e59014b527c90d98e89059dce1e3","datavalue":{"value":"switching method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2335698$C6963755-3970-4E73-A240-975312650725","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":"Q2335698$0B0F8BB3-9DF1-4ADE-BAA2-59A3D2B46EAD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d26f83c489c86a675050a5a073c8f83bfab5abf0","datavalue":{"value":{"entity-type":"item","numeric-id":603928,"id":"Q603928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$BE1F7008-8492-49A1-BB2F-2411B443EC1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec7fb451cd334a87eafe9826c9961a47e98d4405","datavalue":{"value":{"entity-type":"item","numeric-id":1255501,"id":"Q1255501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$51FBDB79-92C9-4343-9C68-874A6D93C930","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f34fb167d6b58149e4c07bc6f477f173f3d07b81","datavalue":{"value":{"entity-type":"item","numeric-id":1150630,"id":"Q1150630"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$6316E04B-C5CD-4BA1-B4E8-DE66F7A17D19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5220d12b9a8abdc7511ca32dadd9f2c210e1916d","datavalue":{"value":{"entity-type":"item","numeric-id":5437233,"id":"Q5437233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$DC4AEAC1-DB95-4887-92A8-5C1405518389","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53a3045d49602d0b9c4f8f52dbe6f290cec953fb","datavalue":{"value":{"entity-type":"item","numeric-id":2921768,"id":"Q2921768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$ADEF86B8-84AE-48E2-92BC-CB00CD2EC4A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"126a6e8af0f2336e71649e4f8fc35c0bc7fb0645","datavalue":{"value":{"entity-type":"item","numeric-id":2014710,"id":"Q2014710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$E59A6E60-35CF-412B-8A5A-82D41FE79B6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a15c597cc9bfc6e74109093e827c5f188a649d5e","datavalue":{"value":{"entity-type":"item","numeric-id":4978195,"id":"Q4978195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$D67758D1-3113-49F5-81F5-28455880FEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c7a50b95c60b0d6625a9b620b1fd679ecaaa8d1","datavalue":{"value":{"entity-type":"item","numeric-id":4608003,"id":"Q4608003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$79F81D72-3FC5-43A3-AB4C-35E8170E01C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a998f318405fc477f47b3c0adacc0d1a8f1414c","datavalue":{"value":{"entity-type":"item","numeric-id":3211352,"id":"Q3211352"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$729DBEBC-0513-4A92-AECC-72760113E417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0a3256ff91621e0cb641812b7eda8cab556768e","datavalue":{"value":{"entity-type":"item","numeric-id":909471,"id":"Q909471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$11081ECB-8E87-40CD-B256-30EA29964545","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68a22275073303073c8a630de601f1a0d0d11df5","datavalue":{"value":{"entity-type":"item","numeric-id":5899329,"id":"Q5899329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$97976CD4-07D1-47AD-A31D-EAB28D8E7D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc0d278ce82f2a6dd33b6471a85cdf70dfa6a3c","datavalue":{"value":{"entity-type":"item","numeric-id":5871279,"id":"Q5871279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$5C7EA641-2647-4D0B-AC2E-3A525638F671","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0d6b421a28a525c93cd184bd972fa3349442987","datavalue":{"value":{"entity-type":"item","numeric-id":3684147,"id":"Q3684147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$69869260-06D4-4A49-A166-763D9A9FF72F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f938ceec49731a9f82b43508a2784120eedc850e","datavalue":{"value":{"entity-type":"item","numeric-id":2998852,"id":"Q2998852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$40C04D46-329D-4AA5-B3F4-17D870194FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e185e1bb6c6648825ff1ed14711bdd428a51676a","datavalue":{"value":{"entity-type":"item","numeric-id":3495665,"id":"Q3495665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$6C8B3626-FF24-4C44-925D-CA59B81CC05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e2a7fce6583589d536487d0ce4f153d9b94db02","datavalue":{"value":{"entity-type":"item","numeric-id":1181014,"id":"Q1181014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$6D596433-8E81-4F5B-AD42-7930DE7434BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52a11691d27dfd44b14e5a0e14462216cb2fd7a0","datavalue":{"value":{"entity-type":"item","numeric-id":1814088,"id":"Q1814088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$62272755-9BB1-4B40-AACE-3B66216B13F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74ae4e3d2c73ce855c6bf1b01b845cd11ef65a8f","datavalue":{"value":{"entity-type":"item","numeric-id":4719436,"id":"Q4719436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$222C8B2C-E735-42A0-8794-EFC86074E359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27749641f834745f92d9197fbf29bdb8aee7f0f2","datavalue":{"value":{"entity-type":"item","numeric-id":3853680,"id":"Q3853680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2335698$9CA3D8C8-8011-4E17-913F-F97A25EBCFDA","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"02d7a8a2dec997adb910fa7e76a1cf040757dd15","datavalue":{"value":"bafkreigzbp4tyhgtmyt6jfxty2mj4xfd7iol2glxjc4tspsjnvzwmaohsy","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2335698$DE3465AB-DF9C-4BB4-B128-086F448CE427","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5729b6eb11f21b3755cfc22fb3dd134eb0a199a","datavalue":{"value":{"entity-type":"item","numeric-id":4978195,"id":"Q4978195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a3c861d317951447e83d3134cc715f7e130ec3f","datavalue":{"value":{"amount":"+0.84383624792099","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":"Q2335698$18BE6C4B-02E4-4BFD-B620-3D99035ED166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9dfe33518bb802277719a972d4caf0048784de55","datavalue":{"value":{"entity-type":"item","numeric-id":909471,"id":"Q909471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e031a956b5b41a139115d907a2dcd243166f6ee7","datavalue":{"value":{"amount":"+0.842609167098999","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":"Q2335698$FF6B14D5-6033-4312-ABB0-C995D58F285B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfcd1f15a2d30f4c4c981beea7850fc1ac5e943c","datavalue":{"value":{"entity-type":"item","numeric-id":2014710,"id":"Q2014710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a8d12c99362d7a9bdcdb7ee24b3716f0492004a2","datavalue":{"value":{"amount":"+0.8422242999076843","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":"Q2335698$934F1C94-F09B-4ABF-B670-05CBEFC1AD60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f18ab396ef3cb52d8cae7855c25051a9195727a","datavalue":{"value":{"entity-type":"item","numeric-id":4719436,"id":"Q4719436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22cd12c2752f33ecd216059c09bc3c94c127dc4e","datavalue":{"value":{"amount":"+0.8166908621788025","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":"Q2335698$3FC197D1-6D92-4689-BF1C-11C488EB3EB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"364d5695723e22d779f1bfde93e859cbf11ee1ea","datavalue":{"value":{"entity-type":"item","numeric-id":3495665,"id":"Q3495665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46d29dfe8f51d2850aadc9c8554199d4a0fad6f5","datavalue":{"value":{"amount":"+0.815340518951416","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":"Q2335698$2E27651C-76B6-419E-BC2F-816FA74F7DC3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Uniform generation of spanning regular subgraphs of a dense graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Uniform_generation_of_spanning_regular_subgraphs_of_a_dense_graph"}}}}}