# Say a finite set $M$ has two partition $A_1,A_2,...A_p$ and $B_1,B_2,...B_p$ such that ...

Say a finite set $$M$$ has two partitions $$A_1,A_2,...A_p$$ and $$B_1,B_2,...B_p$$ such that $$A_i\cap B_j = \emptyset \implies |A_i|+|B_j|\geq p.$$ Prove: $$|M|\geq {1\over 2}(p^2+1).$$

As far as I can remember (now forgot) the solution was short and easy at the time a saw the problem (about 5 years ago).

My try:

Say $$A_1$$ cuts $$k$$ sets from other partition, say $$B_1,,,B_k$$. Clearly $$k\leq |A_1|$$ since each element in $$A_1$$ is in exactly one $$B_j$$. Then we have \begin{align}|A_1|+|B_1| &=|A_1|+|B_1|\\ &\vdots \\ |A_1|+|B_k| &=|A_1|+|B_k|\\ |A_1|+|B_{k+1}| &\geq p\\ &\vdots \\ |A_1|+|B_p| &\geq p \end{align} Summing all those we get $$p|A_1|+|M| \geq k|A_1|+|A_1|+p(p-k)$$ and now I don't have control over $$k$$...

• Are you sure about the bound $|M|\ge \frac{p^2+1}{2}$? Should it be $|M|\ge \frac{p^2}{2}$ instead? For even $p$, you can find a set $M$ with $|M|=\frac{p^2}2$ and partitions $A_i,B_j$ with the required property. Or do you require that $p$ be odd? Commented Feb 24, 2020 at 11:01
• Could be, I don't remember any more. @WETutorialSchool Commented Feb 24, 2020 at 11:41
• I mean the bound is correct, so probably you are right $p$ is odd. @WETutorialSchool Commented Feb 24, 2020 at 11:42

Proposition: Let $$p$$ and $$q$$ be non-negative integers. Suppose that $$M$$ is a set with two partitions $$\{A_1,A_2,\ldots,A_p\}$$ and $$\{B_1,B_2,\ldots,B_p\}$$ such that $$|A_i|+|B_j|\ge q$$ for all pairs $$i,j\in\{1,2,\ldots,p\}$$ such that $$A_i\cap B_j=\emptyset$$. Then, $$|M|\geq\left\{ \begin{array}{ll}\left\lceil\frac{pq}{2}\right\rceil &\text{if}\ 0\leq q \leq p,\\ \left\lceil\frac{6pq-p^2-q^2}{8}\right\rceil &\text{if}\ p In particular when $$q=p$$, we have $$|M|\ge \left\lceil\frac{p^2}{2}\right\rceil$$.

Proof: Let $$G(V,E)$$ be the bipartite graph such that $$V=V_A\sqcup V_B$$ where $$V_A=\{A_1,A_2,\ldots,A_p\}$$ and $$V_B=\{B_1,B_2,\ldots,B_p\},$$ and there exists an edge joining $$A_i$$ and $$B_j$$ iff $$A_i\cap B_j$$ is empty. Let $$I\subseteq E$$ be a maximal pairing of $$G$$ (i.e., a pairing of $$G$$ with the largest possible number of edges).

Wlog suppose that $$I=\big\{\{A_1,B_1\},\{A_2,B_2\},\ldots,\{A_k,B_k\}\big\}$$. Then by maximality of $$I$$, there are no edges between the vertices of $$V_A'=\{A_{k+1},A_{k+2},\ldots,A_p\}$$ and the vertices of $$V_B'=\{B_{k+1},B_{k+2},\ldots,B_p\}$$. Obviously, this means $$A_i\cap B_j\ne\emptyset$$ for every $$i,j=k+1,k+2,\ldots,p$$.

Furthermore, if there exists $$s\in\{1,2,\ldots,k\}$$ such that for some $$i,j\in\{k+1,k+2,\ldots,p\}$$, $$A_s\cap B_{j}$$ and $$A_{i}\cap B_s$$ are both empty, then $$\Big(I\setminus\big\{\{A_s,B_s\}\big\}\Big)\cup\big\{\{A_s,B_{j}\},\{A_{i},B_s\}\big\}$$ is a larger pairing of $$G$$ than $$I$$. This is a contradiction. Therefore, for every $$s\in \{1,2,\ldots,k\}$$ and for any $$i,j\in\{k+1,k+2,\ldots,p\}$$, either $$A_s\cap B_j$$ or $$A_i\cap B_s$$ is non-empty. This proves that $$|A_i|+|B_j|\geq (p-k)+(p-k)+k=2p-k$$ for all $$i,j=k+1,k+2,\ldots,p$$.

Because $$\sum_{i=1}^p|A_i|=|M|=\sum_{j=1}^p|B_j|$$, we get $$2|M|=\sum_{i=1}^p|A_i|+\sum_{j=1}^p|B_j|=\sum_{s=1}^k\big(|A_s|+|B_s|\big)+\sum_{s=k+1}^p\big(|A_s|+|B_s|\big).$$ Since $$|A_s|+|B_s|\ge q$$ for all $$s=1,2,\ldots,k$$, as well as $$|A_s|+|B_s|\ge 2p-k$$ for $$s=k+1,k+2,\ldots,p$$, we conclude that $$2|M|\ge qk+(2p-k)(p-k)=2p^2-(3p-q)k+k^2.$$ Note that $$0\le k\le p$$. If $$q\le p$$, then $$2p^2-(3p-q)k+k^2\ge 2p^2-(3p-q)p+p^2=pq$$ If $$p, then $$2p^2-(3p-q)k+k^2\ge 2p^2-(3p-q)\left(\frac{3p-q}{2}\right)+\left(\frac{3p-q}{2}\right)^2=\frac{6pq-p^2-q^2}{4}.$$ If $$q\ge 3p$$, then $$2p^2-(3p-q)k+k^2\ge 2p^2-(3p-q)0+0^2=2p^2.$$ The claim follows.

Remark: I don't think the bound in the proposition is always sharp. However, the bound above is sharp at least in the following three cases:

• $$q\ge 3p$$,
• $$q\le p$$ and $$q$$ is even, and
• $$q=p$$ and $$q$$ is odd.

When $$q\ge 3p$$, we can take $$M=\{1,2,\ldots,p^2\}$$ along with two partitions $$\{A_1,A_2,\ldots,A_p\}$$ and $$\{B_1,B_2,\ldots,B_p\}$$ with $$A_i=\big\{(i-1)p+1,(i-1)p+2,\ldots,(i-1)p+p-1,(i-1)p+p\big\}$$ and $$B_j=\big\{j,p+j,\ldots,p(p-2)+j,p(p-1)+j\big\}$$ for $$i,j=1,2,\ldots,p$$. If $$q\le p$$ and $$q=2b$$ is even, then we can take $$M=\left\{1,2,\ldots,pb\right\}$$ along with two partitions $$\{A_1,A_2,\ldots,A_p\}$$ and $$\{B_1,B_2,\ldots,B_p\}$$ with $$A_s=B_s=\big\{(i-1)b+1,(i-1)b+2,\ldots,(i-1)b+b-1,(i-1)b+b\big\}$$ for $$s=1,2,\ldots,p$$. If $$q=p$$ and $$q=2b+1$$ is odd, then we can take $$M=\left\{1,2,\ldots,2b^2+2b+1\right\}$$ with $$A_i=\big\{(i-1)b+1,(i-1)b+2,\ldots,(i-1)b+b-1,(i-1)b+b\big\}$$ and $$B_j=\big\{j,b+j,\ldots,b(b-2)+j,b(b-1)+j\big\}$$ for $$i,j=1,2,\ldots,b$$, and $$\small A_i=\big\{b^2+(i-b-1)(b+1)+1,b^2+(i-b-1)(b+1)+2,\ldots,b^2+(i-b-1)(b+1)+b,b^2+(i-b-1)(b+1)+(b+1)\big\}$$ and $$\small B_j=\big\{b^2+(j-b),b^2+(b+1)+(j-b),\ldots,b^2+(b+1)(b-1)+(j-b-1),b^2+(b+1)b+(j-b)\big\}$$ for $$i,j=b+1,b+2,\ldots,2b+1$$.