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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .