8
$\begingroup$

Consider the following problem, called the 'Eventown problem':

In a town, residents can form different clubs. The town council establishes the following rules:

1) Every club must have an even number of members.

2) Two clubs must not have exactly the same members.

3) Every two clubs must share an even number of members.

If the town has $n$ inhabitants, then what is the maximum number of clubs that can be formed according to the rules?

In principle, you can "marry" the inhabitants and ensure only couples join clubs (singles are not allowed). Since the $\lfloor \frac{n}{2}\rfloor$ couples have two choices each, we can form $2^{\lfloor \frac{n}{2}\rfloor}$ clubs. The surprising fact is that this the best possible! This can be solved using some tricks from linear algebra over the binary field. I really enjoyed the wonderful proof of this problem.

Naturally, I wanted to know to what extent this trick can be used. But I could not find any results on the generalization of this problem to other primes.

In particular, I wanted to know if we can solve the '$p$-town problem' where we replace the word 'even' in the Eventown problem with the words 'divisible by $p$' for a prime $p$. Clearly grouping people into teams of size $p$ and asking them to join the clubs, in teams only, will give us a lower bound of $2^{\lfloor \frac{n}{p}\rfloor}$ on the maximum number of clubs.

Is this the best possible? Can we find any investigation on this problem? I am very curious about the linear algebra trick! Does a linear algebra approach to this problem generalize to other primes? Or was it a curious case of a 'one-shot' trick?

Thanks!

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I've been looking for references as well. Similarly, do you know of any references for the mod n version of Oddtown? $\endgroup$
    – Andrés E. Caicedo
    Commented Mar 14, 2014 at 22:58
  • 1
    $\begingroup$ There are results in this direction known as the nonuniform Ray Chaudhuri--Wilson theorem (proved by Frankl and Wilson extending work of Ray Chaudhuri and Wilson). This produces an upper bound of $\sum_{s\le n/p} \binom{n}{s}$, which is a step in the direction you want... . $\endgroup$
    – Lucia
    Commented Mar 14, 2014 at 23:11
  • 1
    $\begingroup$ @Lucia Yes, and there are recent extensions by Grolmusz, but I have not seen these specific variants addressed. (I am not too familiar with the literature on the subject, though, so I may have missed obvious papers.) $\endgroup$
    – Andrés E. Caicedo
    Commented Mar 14, 2014 at 23:49
  • $\begingroup$ @AndresCaicedo: I'm not sure I understand your comment. The problem at hand is a special case of the Frankl-Wilson theorem where intersections lying in any set $L$ are considered. So the Frankl-Wilson theorem gives the upper bound I stated (which is not too bad). Of course this upper bound is best possible in general, but not necessarily in this case (and I don't know what the correct result here should be). $\endgroup$
    – Lucia
    Commented Mar 15, 2014 at 2:08
  • $\begingroup$ @Lucia Yes, that's what I meant. The bounds seem to vary significantly depending on the $L$ under consideration. The Frankl-Wilson result and its extensions are very general, but the versions I know of focus on the size of $L$ rather than its specific elements. $\endgroup$
    – Andrés E. Caicedo
    Commented Mar 15, 2014 at 2:18

1 Answer 1

Reset to default
5
$\begingroup$

There is a paper P. Frankl and A. M. Odlyzko. "On subsets with cardinalities of intersections divisible by a fixed integer." European Journal of Combinatorics 4(3) (1983): 215–220, in which they provide an example of l-town on $(cl)^{[n/(4l)]}$ members for every (not necessarily prime) integer $l$ and an absolute constant $c$.

In the asymptotics this gives $2^{\frac{cn \ln l}{l}}$ which beats $2^{n/l}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .