{"entities":{"Q405108":{"pageid":406875,"ns":120,"title":"Item:Q405108","lastrevid":61599528,"modified":"2026-04-11T00:23:17Z","type":"item","id":"Q405108","labels":{"en":{"language":"en","value":"How many colors guarantee a rainbow matching?"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340125"}},"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":"Q405108$BD505E97-902E-4F9F-BE04-69F35F970116","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a1ea3e685729734cb15ef293bb90b214874e2faf","datavalue":{"value":{"text":"How many colors guarantee a rainbow matching?","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405108$AD38F971-41C5-4128-A836-885D1089DC4F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ad83cec06f90816092d99d758bd42aedd03a7932","datavalue":{"value":"1300.05097","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$5DF0A0BF-E4E1-4AAA-862B-DA10C6690C2C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cda60493022f5f14ac1fe4e356b6f974bac02e6d","datavalue":{"value":{"entity-type":"item","numeric-id":272325,"id":"Q272325"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$E7B7D3FA-6A8A-4003-8DC1-58C648530969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7e2180975cc0441c74630baede04a356d62197c","datavalue":{"value":{"entity-type":"item","numeric-id":290808,"id":"Q290808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$7E615922-18FE-487C-AE0B-EF40EC34B62F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"502bbb6d3842faa7531646862d34737b11134d06","datavalue":{"value":{"entity-type":"item","numeric-id":1584432,"id":"Q1584432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$75542AB8-7852-476D-AD4B-83402FAEF344","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":"Q405108$5401D14B-D362-43E2-AA36-FBB173916617","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405108$28E58A74-A418-46E1-87DA-9C6B5C07F699","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"eb2d5e81f4456f4742e52dfaa5b4ebda538061e0","datavalue":{"value":"https://arxiv.org/abs/1211.0793","type":"string"},"datatype":"url"},"type":"statement","id":"Q405108$D845E15D-0184-49AD-9F09-483F78DED58D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"c5550018017350ac391558b64550cd2d3cebe04d","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p27","type":"string"},"datatype":"url"},"type":"statement","id":"Q405108$A68FF52F-662E-4D89-92F9-C045A511778D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"62391d93ffdbc5d8d0e379adea2ec9245860aaf0","datavalue":{"value":"Summary: Given a coloring of the edges of a multi-hypergraph, a rainbow \\(t\\)-matching is a collection of \\(t\\) disjoint edges, each having a different color. In this note we study the problem of finding a rainbow \\(t\\)-matching in an \\(r\\)-partite \\(r\\)-uniform multi-hypergraph whose edges are colored with \\(f\\) colors such that every color class is a matching of size \\(t\\). This problem was posed by \\textit{R. Aharoni} and \\textit{E. Berger} [ibid. 16, No. 1, Research Paper R119, 9 p. (2009; Zbl 1186.05118)], who asked to determine the minimum number of colors which guarantees a rainbow matching. We improve on the known upper bounds for this problem for all values of the parameters. In particular for every fixed \\(r\\), we give an upper bound which is polynomial in \\(t\\), improving the superexponential estimate of \\textit{N. Alon} [Mosc. J. Comb. Number Theory 1, No. 1, 3--10 (2011; Zbl 1255.05144)]. Our proof also works in the setting not requiring the hypergraph to be \\(r\\)-partite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q405108$6B1D1E7E-4214-4BEF-AF4B-E80C79075055","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$F16174A0-89DB-4702-A697-CFDFFAB06FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$BF608548-A2EE-4C7F-9640-8786B75E70D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1ad1bf428b79a0176d62afa9a160b2a17f8d9ea9","datavalue":{"value":"05D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$F6001076-1D90-49D8-8BF9-AADA4EF9A624","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a09872c507729d29e1c1613e820db567c4517089","datavalue":{"value":"05C65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$FF6AC9E7-93C7-4A9D-8279-82CBBFB7BA30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$401BC9C1-DF13-425C-99B3-D883609D31DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ca36051312caf4dd932329e90ef1bc26f54d378a","datavalue":{"value":"6340125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$9D0C9B0D-BE40-413D-8E85-FA65A57DEACB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d38dfce1450c2e6e12520ff96f70bf75c89bdfd8","datavalue":{"value":"rainbow matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q405108$3AEC636B-E19D-407E-AFCE-53260A74AD08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"191403835f9d573ead779b7e37a9e1db540852cc","datavalue":{"value":"extremal problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q405108$AABAB05B-7ACD-44FC-A901-0E86BEDB9000","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":"Q405108$669C2DC2-4D87-4EE2-8992-F20AF9FA2D4B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd90d5739eb00fa5a5ab0736d73a1e03fd1a98c1","datavalue":{"value":{"entity-type":"item","numeric-id":873644,"id":"Q873644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$56F690C3-12FE-4D23-9A46-5D265116605F","rank":"normal"},{"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":"Q405108$AB733C8A-73B6-4A83-8E04-48ADBC5F8CB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66c67eac33726e7b246e7ae98ea4d3681689d12a","datavalue":{"value":{"entity-type":"item","numeric-id":4518333,"id":"Q4518333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$01BCA5E5-73E0-4C66-B94B-D545B7D4A264","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5e990535b942d4527f78b96bd47a943cc8479a7","datavalue":{"value":{"entity-type":"item","numeric-id":446272,"id":"Q446272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$B9846DB4-E06D-4012-AFE1-F80EF7454D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a07b35799ea93b75596d36219fdde17cf718f3bd","datavalue":{"value":{"entity-type":"item","numeric-id":4446871,"id":"Q4446871"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$561C42B5-E3FD-4876-BE8F-86887563A7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b92e3821f0a20b290fb28e3657ff3e1c5b57a201","datavalue":{"value":{"entity-type":"item","numeric-id":5902976,"id":"Q5902976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$57ACE5C1-CF50-440E-AAC5-A09B7E308C60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8d81578a7757260e56b3768250d14abdb68eed8","datavalue":{"value":{"entity-type":"item","numeric-id":5797044,"id":"Q5797044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$9D5A814F-00DC-4EBA-8E2B-B10A11B8D63B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb6062db7162ee35b3d6ea77b2177bbe535e6567","datavalue":{"value":{"entity-type":"item","numeric-id":3770569,"id":"Q3770569"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$D7888CF0-64D6-4E16-882E-463DB0BFA6DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a3cc33932bce49dcfa94504ac6d3b858fb14229","datavalue":{"value":{"entity-type":"item","numeric-id":1900519,"id":"Q1900519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$E68B9774-7223-4E6E-88BA-739DF70BB08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"215405df6d402442f2b14f4d16068c6f68b9585a","datavalue":{"value":{"entity-type":"item","numeric-id":2888870,"id":"Q2888870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$DB0177DA-2CFB-4B39-8D0C-7165764480C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23db62a342a63360f423ce3fcc98a401945516fa","datavalue":{"value":{"entity-type":"item","numeric-id":3429743,"id":"Q3429743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$B8930831-7BB8-4A77-8D10-68B00A8E7B07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4650fc02d5aa03b9c13d2d0bd06afbbb8b6a763b","datavalue":{"value":{"entity-type":"item","numeric-id":2883866,"id":"Q2883866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$9C869E99-3CBF-44BA-AC45-E24A7FCAF4FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3ca5d9f188310875833f2cc0e443a120246693f","datavalue":{"value":{"entity-type":"item","numeric-id":4222172,"id":"Q4222172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405108$9048E310-CC30-4A97-9404-5133FCCA1920","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"229ec1639c69fc159a5b36cafd03d2d7db19c15d","datavalue":{"value":"bafkreidko7r4e2gyacq6oen73vvpx6vvexy2fu6kwymlxctzgtpri2egeq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405108$3EB055F1-9712-44FD-BF5B-698DBC1782C9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a176099b75a284cee97e38bf7ad7eef02019f7a5","datavalue":{"value":{"entity-type":"item","numeric-id":446272,"id":"Q446272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4749dd2acbd6f1111ab14e19aa79a37f3ea5a40","datavalue":{"value":{"amount":"+0.9182931780815125","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":"Q405108$20B695D0-3DB2-4362-9792-A04FA3F72C6A","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":"74fdb08d242794c05441f727d4ba53ed06ee4d14","datavalue":{"value":{"amount":"+0.8625133633613586","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":"Q405108$7D4E9BA0-5177-45AF-A828-715C72EEE234","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":"6c0096db32e9713a204c942018cefed9486d005a","datavalue":{"value":{"amount":"+0.8560450673103333","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":"Q405108$5133A775-7EB3-451F-916B-BEFDFBD1CB95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ee5b5d06cd4031ebb6507def939672d0601eef3","datavalue":{"value":{"entity-type":"item","numeric-id":510578,"id":"Q510578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"15eed7a5c7321087033429dd412802bcd61b1c87","datavalue":{"value":{"amount":"+0.8535026907920837","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":"Q405108$5D2FDF6D-9884-4FC7-A3EF-390127496C26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"053b119acc07e1d82e4e156184aa47b8af51aed7","datavalue":{"value":{"entity-type":"item","numeric-id":668047,"id":"Q668047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"df13095ff14da30af6acf61829c3bbb11caa7bd6","datavalue":{"value":{"amount":"+0.8516138792037964","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":"Q405108$D02DE5AA-AB17-4370-BE94-A1C0A2B4BF05","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"How many colors guarantee a rainbow matching?","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/How_many_colors_guarantee_a_rainbow_matching%3F"}}}}}