TY - JOUR

T1 - Multicolored matchings in hypergraphs

AU - Alon, Noga

N1 - Funding Information:
Acknowledgements. Research supported in part by an ERC Advanced grant, by a USA—Israeli BSF grant, by the Oswald Veblen Fund and by the Bell Companies Fellowship.
Funding Information:
Research supported in part by an ERC Advanced grant, by a USA—Israeli BSF grant, by the Oswald Veblen Fund and by the Bell Companies Fellowship. This paper was initiated during a visit at the Department of Combinatorics and Optimization of the University of Waterloo. The stimulating research atmosphere at the department and, in particular, fruitful discussions with Penny Haxell and Nick Wormald are gratefully appreciated.
Publisher Copyright:
© 2011, Mathematical Sciences Publishers. All rights reserved.

PY - 2011

Y1 - 2011

N2 - For a collection of (not necessarily distinct) matchings M = (M1, M2,:::, Mq) in a hypergraph, where each matching is of size t, a matching M of size t contained in the union [qi=1Mi is called a rainbow matching if there is an injective mapping from M to M assigning to each edge e of M a matching Mi 2 M containing e. Let f(r, t) denote the maximal k for which there exists a collection of k matchings, each of size t, in some r-partite r-uniform hypergraph, such that there is no rainbow matching of size t. Aharoni and Berger showed that f(r, t) 2r–1 (t – 1), proved that the equality holds for r = 2 as well as for t = 2 and conjectured that the equality holds for all r, t. We show that in fact f(r, t) is much bigger for most values of r and t, establish an upper bound and point out a relation between the problem of estimating f(r, t) and several results in additive number theory, which provides new insights into some of those results.

AB - For a collection of (not necessarily distinct) matchings M = (M1, M2,:::, Mq) in a hypergraph, where each matching is of size t, a matching M of size t contained in the union [qi=1Mi is called a rainbow matching if there is an injective mapping from M to M assigning to each edge e of M a matching Mi 2 M containing e. Let f(r, t) denote the maximal k for which there exists a collection of k matchings, each of size t, in some r-partite r-uniform hypergraph, such that there is no rainbow matching of size t. Aharoni and Berger showed that f(r, t) 2r–1 (t – 1), proved that the equality holds for r = 2 as well as for t = 2 and conjectured that the equality holds for all r, t. We show that in fact f(r, t) is much bigger for most values of r and t, establish an upper bound and point out a relation between the problem of estimating f(r, t) and several results in additive number theory, which provides new insights into some of those results.

KW - Additive Latin transversals

KW - Rainbow matchings

UR - http://www.scopus.com/inward/record.url?scp=84893541128&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893541128&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84893541128

SN - 2220-5438

VL - 1

SP - 3

EP - 10

JO - Moscow Journal of Combinatorics and Number Theory

JF - Moscow Journal of Combinatorics and Number Theory

IS - 1

ER -