Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
Yes, this is another way of looking at it :) – Erel Segal-Halevi Jun 10 '13 at 18:31
I calculated the values up to 21:… and no, it is not in the OEIS, although there are some very similar ones:… – Erel Segal-Halevi Jun 11 '13 at 4:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.