Extremal, enumerative and probabilistic results on ordered hypergraph matchings

Abstract

An ordered r-matching is an r-uniform hypergraph matching equipped with an ordering on its vertices. These objects can be viewed as natural generalisations of r-dimensional orders. The theory of ordered 2-matchings is well developed and has connections and applications to extremal and enumerative combinatorics, probability and geometry. On the other hand, in the case $r \ge 3$ much less is known, largely due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński made some first steps towards a general theory of ordered r-matchings, and in this paper we substantially improve several of their results and introduce some new directions of study. Many intriguing open questions remain.

Keywords

• 05C65
• 05C30
• 05C35
• 05C80