Colorful Matchings

DOI10.1137/21M139997XMaRDI QIDQ6098465zbMATH OpenOpenAlexFDO

Authors Andrii Arman, Vojtěch Rödl, Marcelo Tadeu Sales

Publication date 14 June 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.09633

zbMATH Keywords

matchingsrainbow matchings

Mathematics Subject Classification ID

Triple systems (05B07) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: Suppose a committee consisting of three members has to match $n$ candidates to $n$ different positions. Each member of the committee proposes a matching, however the proposed matchings totally disagree, i.e., every candidate is matched to three different positions according to three committee members. All three committee members are very competitive and want to push through as many of their suggestions as possible. Can a committee always find a compromise -- a matching of candidates to positions such that for every committee member a third of all candidates are assigned according to that committee member suggestion? We will consider an asymptotic version of this question and several other variants of similar problem. As an application we will consider an embedding problem -- in particular which configurations large Steiner systems always need to contain.

Recommendations

• Matchings with few colors in colored complete graphs and hypergraphs
• Multicolored matchings in hypergraphs
• Nearly perfect matchings in regular simple hypergraphs
• Rainbow matchings in r-partite r-graphs
• On a conjecture of Stein

Cites work

• Embedding hypertrees into Steiner triple systems
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 1380611 (Why is no real title available?)
• Nearly perfect matchings in regular simple hypergraphs
• New bounds for Ryser’s conjecture and related problems
• Splitting necklaces

Cited in

(2)

• Perfect matchings in shadow colorings
• A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

This page was built for publication: Colorful Matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6098465)