Combinatorial Puzzle: Greatest possible number of gangs

Question

There are 36 gangsters, and several gangs these gangsters belong to. No two gangs have identical roster, and no gangster is an enemy of anyone in their gang. However, each gangster has at least one enemy in every gang they are not in. What is the greatest possible number of gangs?

Answer 1

I show that $3^{12}$ is the optimal value as found by bof and Makholm. Let A,B be enemies. Let $N_A$ be the number of gangs containing A for which there is a gangster C such that A is the only enemy of C in that gang. Similary, let $N_B$ be the number for B. If $N_A \leq N_B$, then replace the enemies of A with the enemies of B, remove the gangs containing A and for each gang $S$ containing B, make a gang $S \setminus \{B\} \cup \{A\}$. This can be seen to be a valid ganging without decreasing the number of gangs.

Repeat this process until every pair of enemies is homogeneous, that is, until we have: X,Y are enemies if and only if for all gangs $S$ containing X, the set $S \setminus \{X\} \cup \{Y\}$ is a gang.

Once this is done, let the enemy cliques be of sizes $n_1,n_2,\ldots,n_k$. In every gang, there must be exactly one gangster from each enemy clique. Thus the number of gangs is the product of $n_i$s with sum equal to 36. This is probably optimized when all $n_i$s are equal. In this case, the optimal value is easily checked to be $3^{12}$.

Answer 2

This question is the case $n=36$ of the general problem: find the maximum number of maximal cliques in a graph on $n$ vertices. The general solution is given by OEIS sequence A000792, namely: $a(3k)=3^k,$ $\ a(3k+1)=4\cdot3^{k-1},$ $\ a(3k+2)=2\cdot3^k,$ except that $a(1)=1.$ The OEIS cites M. Capobianco and J. C. Molluzzo, Examples and Counterexamples in Graph Theory, North-Holland 1978, p. 207 for this result.

Update. This is a 1960 result of R. E. Miller and D. E. Muller:

R. E. Miller and D. E. Muller, A problem of maximum consistent subsets, IBM Research Report RC-240, J. T. Watson Research Center, 1960.

The same result was obtained independently by John W. Moon and Leo Moser in 1965:

J. W. Moon and L. Moser, On cliques in graphs, Israel J. Math. 3 (1965), 23–28.

A new and simple proof was given by David R. Wood in 2007:

David R. Wood, On the number of maximal independent sets in a graph, Graphs Combin. 23 (2007), 337–352.

These references and more can be found in the answers to this cstheory.stackexchange question.