2025/07/27 by Dudek, Andrzej, Grytczuk, Jarosław, Przybyło, Jakub +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2507.20374
An ordered r-uniform matching of size n is a collection of n pairwise disjoint r-subsets of a linearly ordered set of rn vertices. For n=2, such a matching is called an r-pattern, as it represents one of \tfrac12\binom2rr ways two disjoint edges may intertwine. Given a set P of r-patterns, a P-clique is a matching with all pairs of edges order-isomorphic to a member of P. In this paper we are interested in the size of a largest P-clique in a random ordered r-uniform matching selected uniformly from all such matchings on a fixed vertex set [rn]. We determine this size (up to multiplicative constants) for several sets P, including all sets of size |P|≤2, the set R(r) of all r-partite patterns, as well as sets P enjoying a Boolean-like, symmetric structure.