1
$\begingroup$

What is the number of families of $4t+1$ subsets of order $2t$ of the set $\{1,2, \ldots ,p\}$, where $p$ is a prime number which is equal to $4t+1$ and the order of intersection of each pair of the subsets is $t$ or $t-1$ and each subset has $t$-intersection with $2t$ subsets and $t-1$-intersection with the other $2t$ subsets?

$\endgroup$
1
  • $\begingroup$ you mean: what is the number of families of $4t+1$ subsets. please correct to make it more clear. $\endgroup$
    – Wolfgang
    Feb 23, 2013 at 14:23

2 Answers 2

2
$\begingroup$

Yes, equivalently, the problem can be stated as follows: We are looking for the number of $p\times p$ 0-1-matrices $A$ with all row sums $2t$ such that $AA^T=tJ+tI-B$, where $B$ a 0-1-matrix with also all row sums equal to $2t$. (Here, $J$ denotes the all-1-matrix).

It is not hard to find circulant matrices that fulfill the conditions for each $p=4t+1$ (why only for primes?), and each of them gives rise to $(p-1)!/2$ set families. But different matrices can yield the same families, e.g. for $t=1$, we can have
$A=circ(11000)$ with $AA^T=circ(21001)$ and
$A=circ(10100)$ with $AA^T=circ(20110)$, each yielding the same 12 structures.

For $t=2$:
$A=circ(111010000)$ with $AA^T=circ(4\ 2211\ 1122)$,
$A=circ(110010100)$ with $AA^T=circ(4\ 1122\ 2211)$,
$A=circ(110110000)$ with $AA^T=circ(4\ 2121\ 1212)$,
$A=circ(110101000)$ with $AA^T=circ(4\ 1212\ 2121)$,
$A=circ(111001000)$ with $AA^T=circ(4\ 2112\ 2112)$,
$A=circ(110100010)$ with $AA^T=circ(4\ 1221\ 1221)$.

$t=3$:
$A=circ(1110110100000)$ with $AA^T=circ(6\ 333222\ 222333)$,
$A=circ(1110101100000)$ with $AA^T=circ(6\ 332223\ 322233)$,
$A=circ(1110110010000)$ with $AA^T=circ(6\ 323322\ 223323)$,
$A=circ(1110011010000)$ with $AA^T=circ(6\ 322233\ 332223)$,
$A=circ(1110100101000)$ with $AA^T=circ(6\ 232233\ 332232)$,
and probably many others (looking at the patterns of $AA^T$).

In fact, looking at the $t=2$ patterns that seem "complete", I'd conjecture that there are $\binom{2t}{t}$ essentially different such circulant matrices.
(There may be also non-circulant solutions, so this would not yet solve the problem, but be a nice start.)

$\endgroup$
1
  • 1
    $\begingroup$ A computer search for $t=3$ and $t=4$ shows that not all $\binom{2t}t$ patterns occur. E.g. for $t=3$, only 14 of the 20 occur, and on the other hand, some correspond to several non isomorphic matrices. E.g., both $A=circ(1111001000100)$ and $A=circ(1110110010000)$ yield $AA^T=circ(6\ 323322\ 223323)$. $\endgroup$
    – Wolfgang
    Feb 24, 2013 at 16:45
1
$\begingroup$

I do not know the answer. However, here is part of an analysis for t=1; perhaps some of it can extend for larger t. I usually mean set of size 2t when I say set.

Consider two sets with intersection C of size t. The complement of their union has size t+1, which specifies only one set which has intersection of size t-1 with the two sets. This means any other set that intersects the two sets misses C. Thus (as t=1) one can specify a structure by listing the locations of successive C's. In this case, it means enumerating 5 cycles and dividing out by cyclic and reversal symmetry, giving 12 such structures. (I view it as 0-1 matrices where each column is proved to have 2 1's.)

It may be that taking a matrix view will help with larger t.

Gerhard "Ask Me About Binary Matrices" Paseman, 2013.02.23

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.