## Abstract

For a collection of (not necessarily distinct) matchings M = (M_{1}, M_{2},:::, M_{q}) in a hypergraph, where each matching is of size t, a matching M of size t contained in the union [^{q}i=1^{M}i is called a rainbow matching if there is an injective mapping from M to M assigning to each edge e of M a matching M_{i} 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) 2^{r–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.

Original language | English (US) |
---|---|

Pages (from-to) | 3-10 |

Number of pages | 8 |

Journal | Moscow Journal of Combinatorics and Number Theory |

Volume | 1 |

Issue number | 1 |

State | Published - 2011 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Algebra and Number Theory
- Discrete Mathematics and Combinatorics

## Keywords

- Additive Latin transversals
- Rainbow matchings