{"entities":{"Q2696608":{"pageid":2707352,"ns":120,"title":"Item:Q2696608","lastrevid":82744157,"modified":"2026-05-06T21:51:10Z","type":"item","id":"Q2696608","labels":{"en":{"language":"en","value":"A Markov chain on the solution space of edge colorings of bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7675076"}},"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":"Q2696608$E7898FFC-898E-4E28-93FD-BD84B3EBC57F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2915f13640d25ccaf1b64e9f1557b540abba2485","datavalue":{"value":{"text":"A Markov chain on the solution space of edge colorings of bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2696608$A0D0D382-2B60-4005-9426-0F87E8DC719F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"933bfdaad641fca64c5d288ca37a954910dae62c","datavalue":{"value":{"entity-type":"item","numeric-id":2112573,"id":"Q2112573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$2A3F17A9-250F-4174-9988-CF25C4E92B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aceb36402978b7b9f7bbe2418819becc88d7d8f1","datavalue":{"value":{"entity-type":"item","numeric-id":253273,"id":"Q253273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$1DFC0FA1-8A4D-484E-A32B-F264D76CBF92","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$B40E1C2A-97F6-40AC-A59F-176007A09C8D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6b263d5295cc97d9d2de9006ed9ca8239afe0517","datavalue":{"value":{"time":"+2023-04-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2696608$6A4A30B5-197C-499E-817E-72148EEC9CA8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eb09aa8ae47ba7f856d6703e8cfd36c8c87d425d","datavalue":{"value":"https://arxiv.org/abs/2103.11990","type":"string"},"datatype":"url"},"type":"statement","id":"Q2696608$7B9BD0A5-6D2F-463E-92AD-858625518C0B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d9906f78e51a0e13eaa478e5431f5973ed9946f5","datavalue":{"value":"The authors construct a Markov chain whose states are all the \\(k\\)-edge-colourings of any given bipartite graph \\(G\\), and such that the distribution converges to the uniform distribution. The Markov chain is constructed using a Markov Chain Monte Carlo approach, using the well-known Metropolis-Hastings algorithm. In this application, the Markov chain can be briefly described as follows. Starting from any \\(k\\)-edge-colouring, perform a random ``local change'' in this colouring (i.e. modifying a small proportion of the coloured edges). With certain ``acceptance probability'' (depending on the local change) the change is accepted and the colouring is updated; with the complementary probability the colouring is unchanged.  The authors implement this idea using a particular set of ``local changes'', and are able to show that the obtained Markov chain has several desirable properties. This Markov chain has diameter at most \\(2km\\) if \\(G\\) has \\(m\\) edges (i.e. it is possibly to obtain any prescribed \\(k\\)-edge-colouring of G, starting from any other prescribed \\(k\\)-edge-colouring of G, using at most \\(2km\\) local changes). It also has ``acceptance probability'' whose inverse is bounded from above by a polinomial on the number of vertices of \\(G\\). This generalises previous results by Jacobson and Matthew and of Aksen et al., who constructuted similar Markov chains for (edge-colourings of) specific bipartite graphs.  The authors also study in more detail the specific case where \\(k\\)-edge-colourings of \\(k\\)-regular bipartite graphs are considered. In this case, the bounds obtained previous analysis can be improved. An application of this last part is given to the problem of sampling a random completion of certain incomplete Latin squares.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2696608$AD3641E6-8A39-4DBD-AC16-15CCD0EBA3BB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6c786c862ea96c8431b08bcbc1855c9063fc0aba","datavalue":{"value":{"entity-type":"item","numeric-id":271629,"id":"Q271629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$D718C893-D949-46C7-A015-3D12A5250FC9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1cdf15533e26fc0c4c2e22d28e655c364dfe77a6","datavalue":{"value":"60J10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2696608$B8255744-5E57-4EEF-AA86-78E1CCCA20A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2696608$D36A607D-2531-4EB8-B1E2-7AECA278A5D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2696608$F2D5CD0E-8987-4DD9-921D-99017063E470","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f77013f6538ab2993841bcfb0bbb5e4d3984ab57","datavalue":{"value":"7675076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2696608$5405C1D0-4E24-4F16-8465-7357E8E3530C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc047062ce587cbbd4cabea844b30d6137383d1a","datavalue":{"value":"edge colorings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2696608$434CD11C-41BF-4063-8143-CA6997C03944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48b8ab83a8451eded9102ad7e855308601619ff7","datavalue":{"value":"Latin squares","type":"string"},"datatype":"string"},"type":"statement","id":"Q2696608$33B3677B-7EBA-427F-8474-F8ACC079A5F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a374883a0559388423da4bd83c42d75836d02e0","datavalue":{"value":"MCMC","type":"string"},"datatype":"string"},"type":"statement","id":"Q2696608$1BC6731B-1DD3-42C8-BCE5-BA86B63C89C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"936fd184234e16050a493e84f1177169d7cc9480","datavalue":{"value":"Metropolis-Hastings algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2696608$0F997DC6-758E-45A7-82E4-5A2693BA67DD","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"674cd60828bc007cb59f25ed895882f886c650f9","datavalue":{"value":{"entity-type":"item","numeric-id":17180,"id":"Q17180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$2C65267F-1148-4757-9FEC-EC9B2088ED75","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":"Q2696608$EE07C7DF-E5E5-46DF-8757-2486B65B130E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7764dff7bf7499ec3b1d68c3a99699e54a032ea9","datavalue":{"value":"W4319067239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2696608$BE8DAAF6-B1E2-4BD2-94A3-A46E8FB7C479","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b74a060fceb5a5f1e108d2fb602a20d7ce9ecd99","datavalue":{"value":{"entity-type":"item","numeric-id":2399287,"id":"Q2399287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$8A954ACD-5ACE-467A-A526-70DB77917C0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a64f52b248c6e54db6201187ef78fb8c9350cfa","datavalue":{"value":{"entity-type":"item","numeric-id":4256220,"id":"Q4256220"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$EF71375B-CD2A-451C-835C-A21F065CC7C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1b7df54b2c861009e10a9d09fe2abd2c236cfd0","datavalue":{"value":{"entity-type":"item","numeric-id":4435150,"id":"Q4435150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$C8C4CE01-D0FA-4B61-AF38-B402DDBBB05A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0b8e815b413e9143fba5109ad44772fddc2a411","datavalue":{"value":{"entity-type":"item","numeric-id":313398,"id":"Q313398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$56172F79-C2D6-4567-AA6D-4FFAE90212CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4709dc388598886bb432a7ab2082974f482f2136","datavalue":{"value":{"entity-type":"item","numeric-id":3947136,"id":"Q3947136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$1B374B25-FBEF-4D38-9076-75CAF6E782DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5c9ec45a1f9a738f277a86c223dfe4771c1d460","datavalue":{"value":{"entity-type":"item","numeric-id":5941061,"id":"Q5941061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$CFF7AD7D-E6A8-4FAD-8B25-5B7669FB5889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"741e30ceb0a83e043199aa0c9fefa3fb42ab37d6","datavalue":{"value":{"entity-type":"item","numeric-id":5624533,"id":"Q5624533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$270A1DCE-EBF8-451E-B3CB-E38773BCE2D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$6AD9CBA0-64F3-4B0B-B9D8-D04551BFA3B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7506e10100e0c44bcd3b4787e53c14da6b38af4","datavalue":{"value":{"entity-type":"item","numeric-id":4221860,"id":"Q4221860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$EE628C8F-F5C0-4BE0-B354-2FD7BFD1DF8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c3eb320d4b98114e1bab22bcaf8058810629bf3","datavalue":{"value":{"entity-type":"item","numeric-id":4798347,"id":"Q4798347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$AA9363C7-5530-4AEC-8B3E-1C503801459C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7678cadff422dc18fb5c6f9d2c4055e1ab7c4be8","datavalue":{"value":{"entity-type":"item","numeric-id":1079379,"id":"Q1079379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$74CD9BB7-0E29-45A8-9600-783F345215A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a1a37c8cfcc2bf8125a819c3a0cf157b143652b","datavalue":{"value":{"entity-type":"item","numeric-id":4943084,"id":"Q4943084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$FFE4C3FE-73F1-4A83-A239-97BA9C006FAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b3de5d933aac98ce001a35d32a88fd2111d286a","datavalue":{"value":{"entity-type":"item","numeric-id":4747513,"id":"Q4747513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$376BDC64-B373-41E9-AE6A-F52FDCC873B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"672b7c767d322e7abf654e0a6ad5e1961e56023b","datavalue":{"value":{"entity-type":"item","numeric-id":5218675,"id":"Q5218675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$46D5F331-6DD5-4481-BE25-D2A3B8B4518C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c9339814e9803731d758ec9a7eb7d1674f711d7","datavalue":{"value":{"entity-type":"item","numeric-id":4685131,"id":"Q4685131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$A63BBB4D-7BAD-4251-82EA-12AE67AC6FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48cc68e0639769cf7c816bdde9f4b42adcf67534","datavalue":{"value":{"entity-type":"item","numeric-id":4228512,"id":"Q4228512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$809F0621-6EE2-40E2-8056-6404A51F762F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4002661922cfbf3b51612e8c6c4804f79fd6bac7","datavalue":{"value":{"entity-type":"item","numeric-id":1850561,"id":"Q1850561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$CDDEBACE-4A53-462E-B339-139E82911CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30d6dc2a44e10b14dafdfbecd3cc59ce2dcafe3f","datavalue":{"value":{"entity-type":"item","numeric-id":3499247,"id":"Q3499247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$8E85DC1E-11BA-4F2B-BE5D-6AD5CC1CE407","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87c8ff4fc6f711a607a536b6572a8daeb1f68437","datavalue":{"value":{"entity-type":"item","numeric-id":5558480,"id":"Q5558480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$611390FC-5BBA-4527-BE5B-FFF71232A59C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde0ee611007bcb2af0320a5f17f36f0f0ec67dc","datavalue":{"value":{"entity-type":"item","numeric-id":4367253,"id":"Q4367253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2696608$23FCA6DE-E202-4124-8D02-A290A7E66641","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4f38194a44f19a320c36b2e862bd30ab51e6ac72","datavalue":{"value":"10.1016/J.DAM.2023.01.029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2696608$0893114B-0F76-4229-9495-497EE19ABFAC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df3481ca88f43e1b59b83221d2db946ec4164c20","datavalue":{"value":{"entity-type":"item","numeric-id":5387664,"id":"Q5387664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4a5204207d4b06fc29279cd6ff6be6db013cdd8","datavalue":{"value":{"amount":"+0.8275464773178101","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":"Q2696608$93B320AB-124D-4AAC-8B14-0513EE05E86C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10d795ee182ad0c64ab3011888ed05154955a568","datavalue":{"value":{"entity-type":"item","numeric-id":5101430,"id":"Q5101430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d08dbb1b8cbb9742fdbf6cd3e23ca70dc598cbea","datavalue":{"value":{"amount":"+0.804477870464325","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":"Q2696608$3BC2EBD8-173B-426F-9FAF-56B653CBC0A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca580e1274d7f4023df7764e89e1e5ee0006d8bf","datavalue":{"value":{"entity-type":"item","numeric-id":4705336,"id":"Q4705336"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a396939ffd7520c4235443295d4ac16c49a52f2","datavalue":{"value":{"amount":"+0.7979017496109009","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":"Q2696608$ACFD5B89-437F-4B53-8E76-41B955058252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e113fea7297cbcf12be56f2bf3e371a3692850a3","datavalue":{"value":{"entity-type":"item","numeric-id":2461977,"id":"Q2461977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59ac326d019fe13e4f0cb1c9abde0e47ecc96d84","datavalue":{"value":{"amount":"+0.7905846238136292","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":"Q2696608$7743B156-AE99-4680-9FF9-B0E6B41FAC53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6346f5b0e51d1e195cfce93cc24105967290d26","datavalue":{"value":{"entity-type":"item","numeric-id":3447279,"id":"Q3447279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6f661420122006d08c9f0eea2afffdfc7900697","datavalue":{"value":{"amount":"+0.7904066443443298","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":"Q2696608$9642D110-9A04-44B5-906A-FC40EC89E66F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A Markov chain on the solution space of edge colorings of bipartite graphs","badges":[]}}}}}