3
$\begingroup$

I am encountering the following problem :

Given $p$, $q$, and $r$, is there a way of creating $p$ sets of $q$ integers between $1$ and $r$, such that :

-every integer must be in exactly $\frac{pq}{r}$ sets

-all possible pairs of sets must intersect

I am trying to prove that this is impossible for certain values of $p$, $q$ and $r$, but I need to use every condition, forgetting one of them is never enough. Would you have any ideas on what would be eventually a necessary and sufficient condition on $p$, $q$ and $r$, or an equivalent but easier way to express the problem ? Thank you in advance.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ There is an element belonging to at least $p(p-1)/2r$ pairs of sets, thus necessary condition is that $pq(pq-r)/2r^2\ge p(p-1)/2r$, $q(pq-r)\ge r(p-1)$, $r\le pq^2/(p+q-1)$. $\endgroup$
    – Fedor Petrov
    Commented Mar 20, 2017 at 14:29
  • $\begingroup$ @FedorPetrov Thank you. I actually saw this one, unfortunately it is not enough in my case. I feel like we are considering that each of the intersecting pairs provided by the elements are independent while they are linked by the fact that each set has $q$ elements. $\endgroup$
    – Alice J.
    Commented Mar 20, 2017 at 15:02
  • $\begingroup$ Look up balanced incomplete block designs. That or a minor variation should apply, and you will see some necessary conditions on the parameters. Gerhard "Block Designs Clear The Way" Paseman, 2017.03.20. $\endgroup$
    – Gerhard Paseman
    Commented Mar 20, 2017 at 15:03
  • $\begingroup$ Also, since every two blocks have an element in common, you might be considering a combinatorial projective plane. The Handbook of Combinatorial Designs should help. Gerhard "Handing It Over To Handbooks" Paseman, 2017.03.20. $\endgroup$
    – Gerhard Paseman
    Commented Mar 20, 2017 at 15:08
  • $\begingroup$ @GerhardPaseman Thanks a lot, I will look it up ! $\endgroup$
    – Alice J.
    Commented Mar 20, 2017 at 15:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .