Question

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?

Answer 1

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.)

Answer 2

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