2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Feb 24, 2020 at 11:01
  • $\begingroup$ Could be, I don't remember any more. @WETutorialSchool $\endgroup$
    – nonuser
    Feb 24, 2020 at 11:41
  • $\begingroup$ I mean the bound is correct, so probably you are right $p$ is odd. @WETutorialSchool $\endgroup$
    – nonuser
    Feb 24, 2020 at 11:42

1 Answer 1

1
$\begingroup$

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<q<3p,\\ p^2&\text{if}\ q\ge 3p. \end{array}\right.$$ 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<q<3p$, 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.