MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Thank you every one who answer to this question. – Mojtaba Jazaeri Feb 23 '13 at 14:12
you mean: what is the number of families of $4t+1$ subsets. please correct to make it more clear. – Wolfgang Feb 23 '13 at 14:23
up vote 2 down vote accepted

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

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

share|cite|improve this answer
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)$. – Wolfgang Feb 24 '13 at 16:45

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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