2023/01/07 by Dudek, Andrzej, Grytczuk, Jarosław, Ruciński, Andrzej
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2301.02936
For r,n≥2, an ordered r-uniform matching of size n is an r-uniform hypergraph on a linearly ordered vertex set V, with |V|=rn, consisting of n pairwise disjoint edges. There are \tfrac12\binom2rr different ways two edges may intertwine, called here patterns. Among them we identify 3r-1 collectable patterns P, which have the potential of appearing in arbitrarily large quantities called P-cliques. We prove an Erdős-Szekeres type result guaranteeing in every ordered r-uniform matching the presence of a P-clique of a prescribed size, for some collectable pattern P. In particular, in the diagonal case, one of the P-cliques must be of size Ω( n^31-r). In addition, for each collectable pattern P we show that the largest size of a P-clique in a random ordered r-uniform matching of size n is, with high probability, Θ(n1/r).