A potential couple is a pair of a man and a woman that like each other (assume that 'like' is a symmetric relation).
Given a group of $M$ men and $W$ women, I want to know how many different potential couples there are; mark this number by $C(M,W)$.
Suppose we know that, in a certain group of men and women, $C(3,3) \geq 1$, i.e., in every triple of men and triple of women, there is at least one man and one woman that like each other. What is a lower bound for $C(M,W)$?
I started by looking at $C(3,4)$. If there are 3 men and 4 women, we can put one woman aside, then we know that there is a potential couple within the remaining 3 men and 3 women, then we can put the woman of that couple aside and return the 4th woman, then again we have 3 men and 3 women that must contain a different potential couple, so the total number of couples must be at least 2: $C(3,4) \geq 2$. The same goes for 4 men and 3 women (in general, $C(M,W)=C(W,M)$).
Continuing the same way, $C(3,W)=C(W,3) \geq W-2$.
A similar calculation leads to: $C(4,W) \geq W-1$.
However, for $C(4,6)$ we can get a better bound than $5$ - since $C(3,6) \geq 4$, at least one of the 3 men must be involved in at least 2 potential couples. If we put this man aside, and then bring the 4th man, that 4th man must be involved in 2 potential couples. Therefore, $C(4,6) \geq C(3,6)+2 \geq 6$.
In general, for calculating a lower bound on $C(M,W)$, we can EITHER take a lower bound on $C(M-1,W)$, divide it by M, take the ceiling and add, OR take a lower bound on $C(M,W-1)$, divide it by W, take the ceiling and add. So to get the best lower bound, we should take the maximum of these two.
I created a spreadsheet with the lower bounds on $C(M,W)$ up to $M=W=21$, where you can see the exact formula that I used. I cannot see any pattern - can you?
Can you suggest a closed formula for $C(M,W)$, or at least an asymptotic bound?
EDIT: András Salamon helped me clarify what I mean:
Let $Q$ be the bipartite graph with 3 vertices in each bipartition, and containing no edges.
I am looking for a lower bound on the number of different edges in a $Q$-free bipartite graph with partitions of size $M$ and $W$.