0
$\begingroup$

Use a suitable graph model to reformulate the exercises as graph theoretical problem.

Given a subset $A \subseteq \mathbb{R}^{2}$ which has area $a$ and two decompositions of $A$ into subsets $A_1, A_2, ..., A_m$, and $B_1, B_2, ..., B_m$ such that all the $A_i$'s and all the $B_i$'s have the same area $a/m$. Prove that there exists a permutation $\pi$ of $\{1,2,...,m\}$ such that for all $i = 1,...,m$ we have $A_i \cap B_{\pi(i)} \neq 0$.

Possible solution:

For every area $A_1,A_2,…,A_m$ and $B_1,B_2,…,B_m$ we draw a node. For every set $A_i$ and $B_j$ which share a common area $(A_i∩B_j≠∅)$ we draw an undirected edge between their nodes. From this construction we get a bipartite graph. To show that there exists a permutation $π$ we need to find an edge matching where every node occurs exactly once (perfect matching). The figure below shows an example for two compositions and a possible permutation $π$.

enter image description here

According to König's theorem the number of edges in a perfect matching equals the number of nodes in a minimum vertex cover. Since we need either all nodes $A_i$ or $B_i$ to get a minimum vertex cover no nodes of either group are directly connected to each other — we need $m$ nodes to construct a minimal vertex cover. This means a perfect matching with $m$ edges exist. This matching gives us a correct permutation $π$ since each node in this edge matching must occur exactly once.

Remarks:

I found this possible solution to the problem, though I don't know whether it is completely correct. But, I have a few questions regarding it. From the problem definition it is clear that both subsets have the same size $a/m$. But, why is $A$ part drawn as a matrix in the figure, and $B$ part as a stack? I clearly see from the picture that, if we put $B$ on top of $A$, then $A_1$ and $A_4$ will intersect with $B_1$ and $B_2$, therefore, we have edges between them in the graph, but as I said why it is drawn like that at the first place confuses me.

And lastly, I didn't at all understand how it is proven that there in fact is a perfect matching using König's theorem. I know that the theorem says, but I'm having difficulty grasping how it is used here, and whether the whole solution to the problem is correct.

$\endgroup$
2
$\begingroup$

First the drawing. The rectangle $A$ is (an example of) the area that is going to be subdivided. Below it you see two possible subdivisions and the bipartite graph at the bottom is the one belonging to that specific pair of subdivisions. If $A$ would also have been drawn as a stack, the bipartite graph would only have 6 horizontal lines, which might convey a false impression of triviality. Note that the problem does not require the areas to be rectangles, or even connected.

Then the proof. You can easily see that the claim is false when the requirement that all the areas of the parts are identical is dropped. Since the proof does not use that requirement, it must be wrong.

Instead you can use the following argument. Let $S$ be a subset of the vertices of $A$ of size $s$. Then $S$ represents an area of size $\frac{sa}m$. Now you need at least $s$ parts of $B$ to cover this area, so $|N(S)|\geq|S|$. You have now shown that Hall's condition holds.

$\endgroup$
  • $\begingroup$ So the permutation $\pi$ is actually our perfect matching, right? You are suggesting that I drop completely the König's theorem part, and use the above statement, regarding the subset $S$ of size $s$? One more thing, what do you mean with "which might convey a false impression of triviality"? $\endgroup$ – user72151 Nov 4 '15 at 16:50
  • $\begingroup$ The perfect matching defines the permutation. Indeed, drop König, use Hall, is my advice. Finally: if the example bipartite graph is $6K_2$ as it would be when both subdivisions are the same "stack", you might think the exercise is trivial, which it isn't. $\endgroup$ – Leen Droogendijk Nov 4 '15 at 17:19
  • 2
    $\begingroup$ @portal: And the specific error in the ‘proof’ is the claim that we need all of the nodes $A_i$ or all of the nodes $B_i$ to get a minimum vertex cover. $\endgroup$ – Brian M. Scott Nov 4 '15 at 18:17

Your Answer

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