On a Combinatorial Problem from the Model Theory of Wreath Products, I

✍ Scribed by Dan Saracino

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 181 KB
• Volume: 86
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1998.2941

✦ Synopsis

We prove some conjectures concerning a combinatorial problem that arises in the model-theoretic investigation of wreath products.

1999 Academic Press

We denote the least such d by $(r, n). The above problem arises in connection with the study of what is called the arity of a finite permutation group G. The arity is the smallest k such that for all m k the G-orbits of m-tuples are determined by the G-orbits of k-tuples of their elements. It is shown in [2] that, for the relatively simple case of wreath products of symmetric groups acting naturally, determining the arities is equivalent to determining the values of $(r, n).

It is easy to see [2] that $(r, 2)=2 r&2 when r is even, while $(r, 2) is undefined when r is odd. Some other values of $ for small r and n are indicated in [1, 2], for example, $(3, 3)=3. In general, upper bounds on $(r, n) may be obtained by giving appropriate examples of multisets of equivalence relations. Using a series of such examples, upper bounds on $(r, n) are established in [2] for all cases when n 3, and it is conjectured that these bounds are actually the exact values.