Extremal combinatorics problem on graph matching

59 Views Asked by At

Let $A$ and $B$ be two disjoint set of vertices. Let $\{M_i\}_1^n$ be $n$ edge-disjoint matchings from $A$ to $B$. Let $G$ be the graph with $V = A \cup B$ and $E = \cup_{i} M_i$. Assume that for every matching $M_i$, for every pair of edges $(a_1, b_1)$, $(a_2, b_2) \in M_i$ where $a_1, a_2 \in A$ and $b_1, b_2 \in B$, there exists no $b' \in B$ s.t. $(a_1, b')$ and $(a_2, b')$ are both $\in E$. Show that under this assumption $|E| = O(n^{3/2})$.

I was hinted about the version of this problem where it is assumed that every matching is exactly the induced subgraph of its vertices in $G$. Under such conditions $|E| = O(n^2)$. However I have no idea on either how this "famous" result is reached nor how I can extend it onto tackling this one.