number of potential couples

Question

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

Answer 1

This question is complementary to the $s=t=3$ case of the Zarankiewicz problem. In general, the Zarankiewicz problem asks for the maximum number of edges in a bipartite graph, with given sizes of each part, which does not contain a subgraph isomorphic to $K_{s,t}$. The Zarankiewicz number $z(m,n;3,3)$ is therefore the maximum number of edges in a bipartite graph with $m$ vertices on one side, and $n$ on the other, which does not contain a $K_{3,3}$ subgraph. (This number is also often written $z(m,n;3)$.)

A bipartite graph $G$ does not contain a $K_{3,3}$ subgraph if and only if its "bipartite complement" (by which I mean the bipartite graph that contains exactly the crossing edges which $G$ does not) contains no $Q$-subgraph (where $Q$ is the graph outlined in the problem, with $3$ vertices on each side and no edges). Minimizing the number of edges in $G$ is equivalent to minimizing the number of edges in the bipartite complement of $G$, which is what we're doing here.

So the minimum possible value of $C(M,W)$ is exactly given, in terms of the Zarankiewicz numbers, as $MW - z(M,W;3)$.

In general, the Zarankiewicz numbers are not known exactly. Two useful sources on them may be:

• In Zarankiewicz Numbers and Bipartite Ramsey Numbers by Collins et al., Table 4 lists many known exact values of $z(m,n;3)$ for small $m$ and $n$ (both at least $6$). I think the first improvement over the table linked to in the question is for $(m,n)=(6,7)$, where $z(6,7;3)=29$ implies $C(M,W)$ must be at least $13$, not just at least $12$.
• The history of degenerate (bipartite) extremal graph problems by Füredi and Simonovits is an overview of many related problems. Theorem 3.19 gives the upper bound $z(m,n;3) \le mn^{2/3}+ 2n^{4/3} + m$, which implies the corresponding lower bound $$C(M,W) \ge \max\{MW - MW^{2/3} - 2W^{4/3} - M, MW - M^{2/3}W - 2M^{4/3} - W\}.$$ There is also a construction for the case $M=W$ that asymptotically matches this bound.