{"entities":{"Q510322":{"pageid":512089,"ns":120,"title":"Item:Q510322","lastrevid":57047586,"modified":"2026-03-26T10:28:40Z","type":"item","id":"Q510322","labels":{"en":{"language":"en","value":"Rainbow matchings and rainbow connectedness"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6686266"}},"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":"Q510322$9FC23DE6-F073-4A10-A932-2DE40F596FCD","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"64db30e9f56662e2ae38aaca15800e24cc15a325","datavalue":{"value":{"text":"Rainbow matchings and rainbow connectedness","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q510322$9115C184-4E14-4605-951D-E37FAF470617","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"05caad339571c895c446b92fa39aa414457a54b5","datavalue":{"value":"1355.05203","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$9769817A-0A8B-4C7F-BCD3-1AC1515861E0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bf458a392ae0db17eb0f85a88967799de18440d2","datavalue":{"value":{"entity-type":"item","numeric-id":322268,"id":"Q322268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$05DB2725-6AC7-43BC-9351-10471ECA1512","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":"Q510322$7093AD5F-D239-408F-BBB1-544F05FBF19F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a051f678ce9f4f7380cf2de9c6018ea50fabc5c","datavalue":{"value":{"time":"+2017-02-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":"Q510322$139DA3B4-1573-4B55-BBD5-7D05F451CB6E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"248b9f67dad676286c76500c7d22be9d8e26dae0","datavalue":{"value":"https://arxiv.org/abs/1504.05373","type":"string"},"datatype":"url"},"type":"statement","id":"Q510322$35E6E9C4-C2D4-4309-884C-22E2C2B7ABED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"515a65b7d9b9b0866222da87d1c1ea0c0ffda09e","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i1p13","type":"string"},"datatype":"url"},"type":"statement","id":"Q510322$D942626D-89DF-429D-9356-746C5F3EA463","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ceeb7623a288000980d51b4ac9a4f6a77604a74c","datavalue":{"value":"Summary: \\textit{R. Aharoni} and \\textit{E. Berger} [Electron. J. Comb. 16, No. 1, Research Paper R119, 9 p. (2009; Zbl 1186.05118)] conjectured that every collection of \\(n\\) matchings of size \\(n+1\\) in a bipartite graph contains a rainbow matching of size \\(n\\). This conjecture is related to several old conjectures of \\textit{R. A. Brualdi} and \\textit{H. J. Ryser} [Combinatorial matrix theory. Cambridge etc.: Cambridge University Press. (1991; Zbl 0746.05002)], and \\textit{S. K. Stein} [Pac. J. Math. 59, No. 2, 567--575 (1975; Zbl 0302.05015)] about transversals in Latin squares. There have been many recent partial results about the Aharoni-Berger Conjecture. The conjecture is known to hold when the matchings are much larger than \\(n+1\\). The best bound is currently due to \\textit{R. Aharoni} et al. [``Representation of large matchings in bipartite graphs'', Preprint, \\url{arXiv:1601.00943}] who proved the conjecture when the matchings are of size at least \\(3n/2+1\\). When the matchings are all edge-disjoint and perfect, the best result follows from a theorem of \\textit{R. H\u00e4ggkvist} and \\textit{A. Johansson} [Comb. Probab. Comput. 17, No. 4, 519--536 (2008; Zbl 1152.05019)] which implies the conjecture when the matchings have size at least \\(n+o(n)\\).  In this paper we show that the conjecture is true when the matchings have size \\(n+o(n)\\) and are all edge-disjoint (but not necessarily perfect). We also give an alternative argument to prove the conjecture when the matchings have size at least \\(\\phi n+o(n)\\) where \\(\\phi\\approx 1.618\\) is the Golden Ratio.   Our proofs involve studying connectedness in coloured, directed graphs. The notion of connectedness that we introduce is new, and perhaps of independent interest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q510322$C43826C8-67C0-4766-B92C-06EE7B7C129B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$776C9D11-4EE6-416D-8E52-6B3DEC2CC606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$F1AE4903-99D0-4167-98FF-98650D91D524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0fb5c2b5135b23a64eead86c75bb584d8442d720","datavalue":{"value":"05B15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$A38B4F29-1759-469C-AB4B-29262580C4EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$6C867EB1-D8F1-4B80-B268-B68F3E456A85","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c63778ba5a0bc2c16018269c09aef6508441a89e","datavalue":{"value":"6686266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$681BA6E5-C9A3-4FB0-9DAB-1692FD3ED4AB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f688ae621af73201a019c8f1194e5d3f579b7573","datavalue":{"value":"matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q510322$54D7BFE6-2047-4AC1-BEE5-19B115B7F92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d634b808394b6ce56aeffe284d3cf7ad53dc409f","datavalue":{"value":"connectedness","type":"string"},"datatype":"string"},"type":"statement","id":"Q510322$8A2438C2-454A-47AA-9825-6E8EB47BAC39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48b8ab83a8451eded9102ad7e855308601619ff7","datavalue":{"value":"Latin squares","type":"string"},"datatype":"string"},"type":"statement","id":"Q510322$9345CEE7-07A6-4A11-AE46-F596BEB1C570","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"68f0187c80f319f514f027e2a22d4128fa6f3b57","datavalue":{"value":"transversals","type":"string"},"datatype":"string"},"type":"statement","id":"Q510322$625424A5-3AAB-4593-BD7F-96F943010075","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":"Q510322$268079E3-1F2E-4D5C-BFDF-7482E62F2C9D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1238251f082925ef2f742be0ff65e4b5ddba22c3","datavalue":{"value":{"entity-type":"item","numeric-id":2380283,"id":"Q2380283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$13832EF6-7C72-4D2B-A56A-29A324DABFEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a67221d5cdd26078ffbdfdb6a6432cd5f2138956","datavalue":{"value":{"entity-type":"item","numeric-id":2940993,"id":"Q2940993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$3B894F5B-A179-47D4-A7E1-8CE74FB41F5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5971ab807e617857889f6df4062ad50bfa8066fc","datavalue":{"value":{"entity-type":"item","numeric-id":5348494,"id":"Q5348494"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$BCDB3653-DF1D-4772-94FF-D68826010773","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09d12695d4a3731e56edebe1f68edf8feccbdbd8","datavalue":{"value":{"entity-type":"item","numeric-id":4398864,"id":"Q4398864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$6CC46658-D53F-416A-AF54-1A47FB1C5A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c45d173b4596d4c411d5333a8d80b4ed5e85919","datavalue":{"value":{"entity-type":"item","numeric-id":4177580,"id":"Q4177580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$A49D9CC2-8943-4BCF-A462-DE6D9E787734","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b073b70429536ef3ba0b0852f8badb2c326703a","datavalue":{"value":{"entity-type":"item","numeric-id":3998725,"id":"Q3998725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$185B11A3-6B8A-4262-B0F9-C1EBAB6A00EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40374ae32937deea967d7cb26c57ed28ec1e66fc","datavalue":{"value":{"entity-type":"item","numeric-id":281599,"id":"Q281599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$C4F72E01-0795-4E47-B775-DDB532D8B462","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b137257bde3f60623e44ee73a08107fa72c852e5","datavalue":{"value":{"entity-type":"item","numeric-id":3527541,"id":"Q3527541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$9807219F-7C4B-42F1-8674-DA90085FEE0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f14684d18fa9f7f6265ca06914c03019844f3076","datavalue":{"value":{"entity-type":"item","numeric-id":5900501,"id":"Q5900501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$9ADAC3DA-C718-40E6-823E-E43A0D9B5188","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3b69212c350e70142b5789d1cf269a9f9b83f61","datavalue":{"value":{"entity-type":"item","numeric-id":2637240,"id":"Q2637240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$8BB9F322-1779-4049-91A6-965E70686717","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c49a6e06b896e4f1664315238aae63fd1a1250e","datavalue":{"value":{"entity-type":"item","numeric-id":1215505,"id":"Q1215505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$F944E175-0E7B-4E62-AB10-315C156F4222","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfe3ae059093bea746d306d1d7ea071ab1714775","datavalue":{"value":{"entity-type":"item","numeric-id":3089374,"id":"Q3089374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$A5D2EA7A-B817-461E-B997-8AC20441D5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f42cba67594ff27063911205c759fa0b87ea45","datavalue":{"value":{"entity-type":"item","numeric-id":1242922,"id":"Q1242922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q510322$04FCB3C5-4FDA-490B-AC05-A1B0EA69E62C","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"259b995eeabfce73c8f1cc4891d85e2e61ffd26b","datavalue":{"value":"bafkreiagp354nb3eksmi3hgybbyrmrl35gxhfcuoqe2x6h7tbdrvcwcqvu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q510322$091EAA0C-8CFB-490B-BC8B-F48297214DAC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dabee03ba67b15c60eb4221d994f569dee78987e","datavalue":{"value":{"entity-type":"item","numeric-id":322269,"id":"Q322269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2d36240ddf42435b61aab8c4fd97d525797d3ea","datavalue":{"value":{"amount":"+0.961066722869873","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":"Q510322$4AD28B62-5141-4D9E-9254-DA110C0E1391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e115ddac854d61c6eff14e68706d4bd13383e24","datavalue":{"value":{"entity-type":"item","numeric-id":1649359,"id":"Q1649359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c376f44d8f87ff7e45e157ee337e19514d923285","datavalue":{"value":{"amount":"+0.893076479434967","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":"Q510322$BBB96168-574F-44ED-AA2F-D1743D7EECCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cfb5f39c3474b27c3dd05fc74c00fe405d1fbef","datavalue":{"value":{"entity-type":"item","numeric-id":3174698,"id":"Q3174698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6013477352a442c63f9c94314303bfe8809e41aa","datavalue":{"value":{"amount":"+0.8845757246017456","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":"Q510322$CCBCD02C-159E-4A0C-B16A-41C409D9E8D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"110836bc44ee2fa18a44211661ede64e6ae4b439","datavalue":{"value":{"entity-type":"item","numeric-id":281599,"id":"Q281599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8aa2d73d85ef443d77bd541a6db25fb8efb87399","datavalue":{"value":{"amount":"+0.8756940364837646","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":"Q510322$738005A2-6B65-4383-81CB-B45B2294CBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c790802666fee49d4490273b186306557ee4b82","datavalue":{"value":{"entity-type":"item","numeric-id":2073301,"id":"Q2073301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8786dd9abad7d6b75aefd4681bea936b7bfc73e7","datavalue":{"value":{"amount":"+0.8756826519966125","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":"Q510322$CB290420-E560-4657-AB35-A6D8DF1A703C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:510322","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:510322"}}}}}