{"entities":{"Q5899329":{"pageid":8003577,"ns":120,"title":"Item:Q5899329","lastrevid":39834455,"modified":"2025-01-27T18:06:26Z","type":"item","id":"Q5899329","labels":{"en":{"language":"en","value":"Generating random regular graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5150179"}},"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":"Q5899329$5A6A93FA-7C95-4705-97A4-B1DA2FC369A9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6158421125efbda69f63902ef1fd743c1081fdaf","datavalue":{"value":{"text":"Generating random regular graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5899329$4C835734-754D-4BE8-ADA8-AFE03F67BF67","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"64429d933af5e2dece7dc796c3442c76a1abe347","datavalue":{"value":"1121.05110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5899329$F1EEF75C-5BA7-420A-ACFE-321992C16EFF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"60f6f958ccf9cd09e9d31c01a086fcdad421f3cb","datavalue":{"value":{"entity-type":"item","numeric-id":178483,"id":"Q178483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5899329$AE373D2C-1917-483A-B5AE-1783C9D0AA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3ac20003147c5e8ffc37ced247b8446bd4defdc1","datavalue":{"value":{"entity-type":"item","numeric-id":178484,"id":"Q178484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5899329$E182A23A-28D0-486F-99C1-6817AC1403F1","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":"Q5899329$FF98F092-837A-473A-94AB-1A2F014470DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0ef68d2ac953bb6a5d4619876ccd47f691709c15","datavalue":{"value":{"time":"+2007-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5899329$F65AF315-6A39-4147-A25B-11950F597499","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"02864fd89bd74445847d9d9bc7b317225a29f099","datavalue":{"value":"Fix a pair of positive integers \\(1\\leq d<n\\) and let \\(S(n,d)\\) be the set of all simple \\(d\\)-regular graphs on a set of \\(n\\) vertices. The uniform random \\(d\\)-regular graph \\(G_{n,d}\\) is obtained by sampling with respect to the uniform distribution from \\(S(n,d)\\). The probability of each simple \\(d\\)-regular graph is thus \\(1/| S(n,d)|\\). Since \\(nd\\) is twice the number of edges in \\(G_{n,d}\\), we always assume that \\(nd\\) is even.  Despite an extensive study, a very fundamental, and perhaps practically the most important, question concerning random regular graphs has not yet been answered in a satisfactory way:   Question: How do we generate a uniform random regular graph?   The paper under review presents a contribution to the answer of this question. The authors analyze an algorithm introduced by \\textit{A. Steger} and \\textit{N. Wormald} [Comb. Probab. Comput. 8, 377--396 (1999; Zbl 0935.05082)] and prove that it produces an asymptotically uniform random \\(d\\)-regular graph in time \\(O(nd^2)\\) for \\(d\\) and \\(n\\) satisfying \\(d=O(n^{1/3-\\epsilon})\\) as \\(n\\to\\infty\\), where \\(\\epsilon\\) is a positive constant. This confirms a conjecture of \\textit{N. Wormald} [Lond. Math. Soc. Lect. Note Ser. 267, 239--298 (1999; Zbl 0935.05080)]. The method of proof is based on a recently developed concentration inequality which can be applied to functions with large Lipschitz coefficients.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5899329$BE2D5134-420E-46F0-A324-C9649F86B8C3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba3efcb7de77d1bd49142f0373b838a01109e4e7","datavalue":{"value":{"entity-type":"item","numeric-id":584284,"id":"Q584284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5899329$586C8AF3-F30C-4590-BDA2-039EFBD01047","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4dd6b8847e09c706889ad9ef05dc0040f1c9f982","datavalue":{"value":"05C80","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5899329$D426840F-CF47-4F6E-B939-E4B264272235","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3448ffdb7fe684dce4e011e5b394cba4ce9edf97","datavalue":{"value":"5150179","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5899329$7A95041F-01D5-44E6-8760-240A0D78C5B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62e547b57ec4579de9e575a2ac77aeddbd664491","datavalue":{"value":"random regular graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5899329$A1E365ED-9793-43C5-83B0-BAAB98A30A62","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":"Q5899329$D6E38135-2A31-4C22-A347-DE1CEE87F7A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"090ceea2d40b4caf2fe8866c4de656412237b6f9","datavalue":{"value":"https://doi.org/10.1007/s00493-006-0037-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q5899329$FEF4C4AF-16F5-4A8F-9FD7-73FE11A79012","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"aea73ed583791249238d026abf269763abe2ce31","datavalue":{"value":"W2610630562","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5899329$EBE93CFF-08D1-4F35-AEAC-DEEB3FCA09BC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3013570bec12d11df1f368ed7985ea2e6b9ba15","datavalue":{"value":"10.1007/S00493-006-0037-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5899329$27EDC316-FA6B-4CD2-9668-F7DC2E9A7089","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e26b64b5e251404df0b52aba0267d8a17a03a9c","datavalue":{"value":{"entity-type":"item","numeric-id":5901097,"id":"Q5901097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9514dae8d7d5ebb1eb7d51b3f074c4f3689f2ca","datavalue":{"value":{"amount":"+0.95603204","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":"Q5899329$569299CA-6554-4B17-BA0B-B73826645E2F","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":"e617445204450afa23622f9ca2847ea958fa5761","datavalue":{"value":{"amount":"+0.89676356","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":"Q5899329$1664FA56-6E75-4916-B4FE-E57D85E628E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7efd82efa9a3c989edb3fc444b9bec4295c0571","datavalue":{"value":{"entity-type":"item","numeric-id":603928,"id":"Q603928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2e13d619c51d5e2e48e5b1b71ff16e549c794b1","datavalue":{"value":{"amount":"+0.8757285","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":"Q5899329$11E3E4E3-B5E0-44A4-80EC-0780CE654ACA","rank":"normal"},{"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":"bc18e841209c086e6ee0ac346b0732b7da876b70","datavalue":{"value":{"amount":"+0.8623052","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":"Q5899329$911E7665-81AA-4A5A-A66E-997E63A7F4CC","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":"bf835108a4ce57843dafde08ef1e7227b03e6e20","datavalue":{"value":{"amount":"+0.8520461","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":"Q5899329$555DF237-AFE3-4D22-B68A-85B312025471","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27501c6ff306d4e210215db6a9f401ea093197d5","datavalue":{"value":{"entity-type":"item","numeric-id":6074660,"id":"Q6074660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39c7ea5a9eeecdbe5d495bb148a6f7f9d29fda2f","datavalue":{"value":{"amount":"+0.83629304","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":"Q5899329$23000083-876D-4C25-B57B-37EA044B079E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa8f01b65783249dd6d11b607aada15ef35c82ed","datavalue":{"value":{"entity-type":"item","numeric-id":3603475,"id":"Q3603475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1508dfbfe4b13bf3b1a2c3f4332f21e94ed20bb","datavalue":{"value":{"amount":"+0.8344227","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":"Q5899329$30EA1EC7-9398-4F41-A51C-6D63E3D692C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbb38989f7e8075de437288483e8776fb58edef7","datavalue":{"value":{"entity-type":"item","numeric-id":3773364,"id":"Q3773364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bbd0384d04af3fda0452b3d24138f9d13362b30","datavalue":{"value":{"amount":"+0.8310659","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":"Q5899329$ABEA8B90-37D2-4805-AE6D-968B7202ED06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a0efdc864641aa5b30cb30f8ba7644757cb874a","datavalue":{"value":{"entity-type":"item","numeric-id":4689375,"id":"Q4689375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"69c33c92221b04e81a5c20bb232dec26b6b398b6","datavalue":{"value":{"amount":"+0.8306967","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":"Q5899329$B1AEC104-0442-4423-A1E3-5333E097728C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a1f37488691ccacae58bd2a60e37beab116d3d6","datavalue":{"value":{"entity-type":"item","numeric-id":5716963,"id":"Q5716963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"77f2bac4f64561f5c75e82298a0ec8daa353854c","datavalue":{"value":{"amount":"+0.8272898","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":"Q5899329$50ABFA2B-7835-4BBC-BE52-5638CF4DDD53","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5899329","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5899329"}}}}}