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

✍ Scribed by Dan Saracino

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

✦ Synopsis

We continue the investigation of a combinatorial problem concerning multisets of equivalence relations on a finite set.

1999 Academic Press

We denote the least such d by $(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, $(5, 4)=7. In [2], values are conjectured for $(r, n) in all cases where n 3.

The conjectured values of $(r, 3) were established in [3]. In the present paper we focus on the value of $(r, 4) for odd r 7, which is conjectured in [2] to be 2 r&2 &1. Our result will subsequently be used in determining $(r, n) for larger n.

An example given in [2] shows that $(r, 4) 2 r&2 &1 for odd r 7, so our task here will be to establish the reverse inequality. In doing so we can count the relations in each multiset according to their multiplicities, but we shall in fact establish somewhat more than is required by proving