$n$ people form $k$ clubs. Each club has at least 3 people. every two club has exactly 1 member in common. Maximum number of $k$?

Question

$n$ people form $k$ clubs. Each club has at least 3 people. every two club has $1$ and exactly $1$ member in common. What's the maximum number of $k$?

My thoughts: Similar to oddtown problem, I can think of this as a linear algebra problem. Let $A$ be a matrix of $n$ by $k$ where $A_{ij} = 1$ when member $i$ is in club $j$ and $A_{ij} = 0$ otherwise. $A^TA $ has diagonal greater or equal to 3 and non diagonal entries equal to $1$. What's the biggest dimension of $k$? At the very least $A^TA$ needs to be positive semidefinite. But I can't go any further...

Answer 1

Each person $p$ is a member of at most $\lfloor {n-1\over2}\rfloor$ clubs, because removing $p$ from those clubs leaves several disjoint sets of size at least $2$. Therefore, the number of pairs $(p,C)$ such that $p$ is a person, $C$ is a club, and $p$ is a member of $C$, is at most $n\cdot \lfloor \frac{n-1}2\rfloor$. On the other hand, the number of such membership pairs is at least $3k$, since each $C$ contains at least $3$ members. Therefore, we get that $$ n\cdot \left\lfloor \frac{n-1}2\right\rfloor\ge 3k\implies k\le \left\lfloor\frac{n}3 \left\lfloor\frac{n-1}2 \right\rfloor\right\rfloor $$ When when $n\equiv 1$ or $3\pmod6$, the floors disappear, and this becomes $n(n-1)/6$. For these $n$, the bound is exactly attainable using a Steiner triple system of order $n$. See [Skolem] for the details of how to construct Steiner triple systems for these $n$.

Edit 2: Okay, I found this problem in the CRC Handbook of Combinatorial Designs. It is known as a packing design. It turns out that the upper bound $\left\lfloor\frac{n}3 \left\lfloor\frac{n-1}2 \right\rfloor\right\rfloor$ is attainable, except for when $n\equiv 5\pmod 6$, in which cases you can only get that upper bound minus one. The construction for $n\equiv 0,2\pmod 6$ is easy, just take a Steiner triple system of order $n+1$ and delete one person, and all clubs containing them. For $n\equiv 4,5$, you will have to consult the handbook for the construction, in the Packings chapter (chapter 40 page 550 in the second edition).

Charles J. Colbourn and Jeffrey H. Dinitz. 2006. Handbook of Combinatorial Designs, Second Edition (Discrete Mathematics and Its Applications). Chapman & Hall/CRC.

Skolem, T. (1958). Some Remarks on the Triple Systems of Steiner. MATHEMATICA SCANDINAVICA, 6, 273-280. https://doi.org/10.7146/math.scand.a-10551

Answer 2

One solution is to have one person be a member of all the clubs and everybody else only a member of one club. This gives you $k=\lfloor \frac {n-1}2 \rfloor$

This paragraph assumes that each club must have exactly three people because I misread the problem. Otherwise, pick one club and call its members $A,B,C$. At least two of them, say $A,B$ are members of other clubs. Call the clubs that include $A$ a-clubs and the ones that include $B$ b-clubs. No one except $A$ can be a member of more than one a-club and no one other than $B$ can be a member of more than one b-club. Given that there is an a-club besides $A,B,C$ there cannot be more than three b-clubs (or c-clubs). Let the second a-club be $A,D,E$. It has to have one member in common with every b-club. $A$ is shared with $A,B,C$, $D$ can be shared by one and $E$ shared by another. By symmetry, there cannot be more than three a-clubs. We can have $$A,B,C\\ A,D,E\quad A,F,G\\B,D,F\quad B,E,G\\ C,D,G\quad C,E,F$$
for seven clubs at a maximum this way.