Homogeneous substructures in random ordered hyper-matchings

Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło, Andrzej Ruciński · 2025

Read Homogeneous substructures in random ordered hyper-matchings by Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło, Andrzej Ruciński (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-20374.txt.

Introduction

Rows of paired items, set out in a line, can twist around each other in many ways. Andrzej Dudek and co-authors study such pairings in a 2025 paper on random ordered matchings. Each pairing joins small groups that do not share points, and pairs can cross or nest in set patterns.

The team asks how large a block of pairs, all sharing the same small set of patterns, a random pairing is apt to hold. They pin down that size, up to a steady factor, for all small pattern sets and for some larger, well shaped ones. One case covers pairs that split cleanly into two camps. The results add firm ground to the maths of ordered pairings.

Catalog record

CREATORAndrzej Dudek, Jarosław Grytczuk, Jakub Przybyło, Andrzej Ruciński
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-20374

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Homogeneous substructures in random ordered hyper-matchings Thanks: The first author was supported in part by Simons Foundation Grant MPS-TSM-00007551. Thanks: The second author was supported in part by Narodowe Centrum Nauki, grant 2020/37/B/ST1/03298. Thanks: The third author was supported in part by the AGH University of Krakow grant no. 16.16.420.054, funded by the Polish Ministry of Science and Higher Education. Thanks: The last author was supported by Narodowe Centrum Nauki, grant 2024/53/B/ST1/00164. Andrzej Dudek, Jarosław Grytczuk, Jakub Przybyło, Andrzej Ruciński Abstract . An ordered r r -uniform matching of size n n is a collection of n n pairwise disjoint r r -subsets of a linearly ordered set of r ​ n rn vertices. For n = 2 n=2 , such a matching is called an r r -pattern , as it represents one of 1 2 ​ ( 2 ​ r r ) \tfrac{1}{2}\binom{2r}{r} ways two disjoint edges may intertwine. Given a set 𝒫 \mathcal{P} of r r -patterns, a 𝒫 \mathcal{P} -clique is a matching with all pairs of edges order-isomorphic to a member of 𝒫 \mathcal{P} . In this paper we are interested in the size of a largest 𝒫 \mathcal{P} -clique in a random ordered r r -uniform matching selected uniformly from all such matchings on a fixed vertex set [ r ​ n ] [rn] . We determine this size (up to multiplicative constants) for several sets 𝒫 \mathcal{P} , including all sets of size | 𝒫 | ≤ 2 |\mathcal{P}|\leq 2 , the set ℛ ( r ) \mathcal{R}^{(r)} of all r r -partite patterns, as well as sets 𝒫 \mathcal{P} enjoying a Boolean-like, symmetric structure. 1. Introduction In this paper we are interested in the maximum size of sub-matchings of random ordered uniform matchings with all pairs of edges forming prescribed patterns. Before stating our results we present necessary definitions and background. 1.1. Matchings and words A hypergraph on a linearly ordered vertex set is called ordered , and it is r -uniform , r\geq 1 , if all its edges have the same size r . Two ordered hypergraphs are order-isomorphic if there is an isomorphism between them preserving their linear orders. An ordered r -matching of size n is an ordered r -uniform hypergraph consisting of n pairwise disjoint edges (and no isolated vertices). For fixed r and n , there are precisely \frac{(rn)!}{(r!)^{n}\,n!} distinct ordered r -matchings of size n . The family of all of them will be denoted by \mathcal{M}^{(r)}_{n} . For instance, the family \mathcal{M}^{(2)}_{2} consists of three distinct matchings depicted in Figure 1.1 . 1 2 3 4 1 2 3 4 1 2 3 4 Figure 1.1. Three distinct 2 -matchings of size two. A natural and convenient way to represent ordered r -matchings is in terms of words . One simply fixes an alphabet of size n and assigns different letters to different edges (so the obtained word contains each letter exactly r times). For instance, if r=3 and M=\{\{1,2,4\},\{3,10,12\},\{5,7,11\},\{6,8,9\}\} , then two examples of words representing M are AABACDCDDBCB and CCECDFDFFEDE . Obviously, there are many such words which differ only in the letters selected to the alphabet and their assignment to the edges. All such words are equivalent and throughout the paper we identify ordered matchings with the equivalence classes of their word representations. Just for convenience, to represent a given matching we typically choose a word in which the first occurrences of letters appear alphabetically. An important subclass of matchings can be defined via the notion of interval chromatic number introduced in [ 15 ] . An interval coloring of an ordered hypergraph G is a partition of its linearly ordered vertex set into intervals (colors) such that each edge of G has at most one vertex in each of these intervals. The least number of colors in any interval coloring of G is the interval chromatic number of G , denoted by \chi_{<}(G) . Clearly, if G an ordered r -uniform hypergraph, then \chi_{<}(G)\geq r . An ordered r -matching M with \chi_{<}(M)=r will be called r -partite . In such a matching, every edge contains exactly one vertex from each of the r consecutive blocks of size n . Equivalently, any word representing an r -partite r -matching must consist of r consecutive blocks each containing all letters. Note also that, trivially, every sub-matching of an r -partite r -matching is r -partite itself. For instance, the following 3 -matching is visibly 3 -partite: {\color[rgb]{1,0,0}{ABCDEFG}}\>\!{\color[rgb]{0,1,1}{\underline{ACGEFBD}}}\>\!{\color[rgb]{0,0,1}{\underline{\underline{GFEDCBA}}}}. Note that here every edge is of the form \color[rgb]{1,0,0}{X}\>\!\color[rgb]{0,1,1}{\underline{X}}\>\!\color[rgb]{0,0,1}{\underline{\underline{X}}} . Also, the sub-matching consisting only of the edges represented by letters A and B , ABABBA , is 3-partite too. We will often use the power notation W^{k} to write concisely the word \underbrace{W\;W\;\cdots W}_{k} consisting of k repetitions of the same word W . For instance, ABABAB=(AB)^{3} and ABBBABAAAA=AB^{3}ABA^{4} . 1.2. Patterns and cliques Ordered r -matchings of size n=2 are called r -patterns . For each r\geqslant 2 there are exactly \tfrac{1}{2}\binom{2r}{r} of them. The set of all r -patterns will be denoted by \mathcal{P}^{(r)} (instead of \mathcal{M}_{2}^{(r)} ). For instance, in letter notation, \mathcal{P}^{(2)}=\{AABB,\;ABBA,\;ABAB\} , (cf. Figure 1.1 ). For a fixed pattern P , a P -clique is an ordered matching in which every pair of edges forms pattern P . In Figure 1.2 one can see three P -cliques of size four corresponding to the three 2 -patterns in \mathcal{P}^{(2)} . A A B B C C D D A B C D D C B A A B C D A B C D Figure 1.2. Cliques of size 4 corresponding to the three patterns in \mathcal{P}^{(2)} . In [ 4 ] we proved that every ordered 2 -matching of size n contains, for some P\in\mathcal{P}^{(2)} , a P -clique of size \lceil n^{1/3}\rceil (and this is optimal), while a random such matching contains (with high probability) a P -clique of size \Theta(n^{1/2}) for every P\in\mathcal{P}^{(2)} . These results were generalized in [ 5 ] to arbitrary r\geqslant 3 , with a necessary restriction to collectable patterns P , that is, to those patterns that allow building arbitrarily large P -cliques. The following characterization of collectable patterns was established in [ 5 , Proposition 2.1] : an r -pattern P is collectable if and only if it is splittable into consecutive blocks , P=S_{1}\cdots S_{s} , of the form S_{i}=A^{t}B^{t} or S_{i}=B^{t}A^{t} . Obviously, such a splitting is unique. For instance, (1.1) P=AB|BBAA|BA|AAABBB|BBAA|BA|AB|AB is a collectable 12 -pattern with the suitable splitting into eight blocks S_{i} . From this characterization one can easily deduce that for every r\geqslant 3 there are exactly 3^{r-1} collectable patterns in \mathcal{P}^{(r)} . It was also proved in [ 5 , Proposition 2.1] that non-collectable patterns P cannot even create P -cliques of size three. Every collectable r -pattern P uniquely determines a composition \lambda_{P}=(\lambda_{1},\dots,\lambda_{s}) of the integer r , that is, an ordered partition r=\lambda_{1}+\cdots+\lambda_{s} , where \lambda_{i}=|S_{i}|/2 , for i=1,\dots,s . For the 12-pattern P defined in ( 1.1 ) \lambda_{P}=(1,2,1,3,2,1,1,1) . Note that for a collectable pattern P with s blocks in the splitting there are exactly 2^{s-1} patterns Q with \lambda_{Q}=\lambda_{P} (including P ). Let us call such

Read the complete text