0
$\begingroup$

I have two related(but separate) questions that are both heading toward something I am trying to prove(I think anyway).

  1. Let's assume that $A_1,A_2,...,A_n$ is a collection of subsets of $S$ such that $|A_i|=m$ for all $i$ and every element in the set $S$ belongs to exactly $m$ of the sets $A_1,A_2,...,A_n$. Prove that the sets $A_1,A_2,...,A_n$ have a system of distinct representatives.

Obviously I am supposed to prove that the criterion in Hall's theorem holds. And I see that $k\leq k\cdot m = \sum_{i=1}^{k}|A_i|$, but I cant really make the needed connection between the union $|\bigcup_{i=1}^{k}A_i|$ and $k$.

  1. Let's assume now that $|S|=m\cdot n$ and that $S=A_1\cup A_2\cup...\cup A_m=B_1\cup B_2\cup...\cup B_m$, where $|A_i|=|B_i|=n$ for all $i$. Prove that it is possible to re-index the sets $A_i$ such that $A_i\cap B_i=\emptyset$ for all $i$.

I don't really know where to start with this one and I am not entirely sure if it is even true but I think it is. Any help would be appreciated!

$\endgroup$

2 Answers 2

3
$\begingroup$

$$\sum_{i=1}^{k}|A_{i}|=mk$$ Note that every element in $\bigcup_{i=1}^{k}A_{i}$ appears at most $m$ times in the left hand side of the above equation, i.e. it is contained in at most $m$ of the sets $A_{1},\cdots,A_{k}$, which guarantees that $$\sum_{i=1}^{k}|A_{i}|\leq m\left|\bigcup_{i=1}^{k}A_{i}\right|.$$ Combine this inequality with the equation, and we get the desired $$\left|\bigcup_{i=1}^{k}A_{i}\right|\geq k.$$ A good view of the question is think of the elements and the sets as vertices of a bipartite graph, in which an element-representing vertex is connected by an edge to a set-representing vertex iff the element is contained in the set. The result we've just got translates to the fact that a $m$-regular bipartite graph always has a complete matching.

$\endgroup$
1
$\begingroup$

For your second question, it isn’t always possible to re-index the sets in the desired manner. To see this, let $m=n$ and $S=[n]\times[n]$. If we let $A_k=\{k\}\times[n]$ and $B_k=[n]\times\{k\}$ for each $k\in[n]$, we find that $\langle k,\ell\rangle\in A_k\cap B_\ell$ for each $\langle k,\ell\rangle\in[n]\times[n]$: each $A_k$ has non-empty intersection with each $B_\ell$.

In fact there is a counterexample whenever $n\ge m$. Let $S=[m]\times[n]$, and for $k\in[m]$ let $A_k=\{k\}\times[n]$. For $\ell\in[m]$ let

$$B_\ell=\big([m]\times\{\ell\}\big)\cup\left(\{\ell\}\times\big([n]\setminus[m]\big)\right)\,;$$

clearly $\langle k,\ell\rangle\in A_k\cap B_\ell$ for each $\langle k,\ell\rangle\in[m]\times[m]$.

$\endgroup$
3
  • $\begingroup$ I can't quite wrap my head around your argumentation, but I found the same question here:math.stackexchange.com/questions/2833429/… Someone there seems to think that this statement is true. What do you think? $\endgroup$
    – hirohe
    Commented Nov 1, 2020 at 18:39
  • $\begingroup$ @SlaveofChrist: It’s the opposite of your problem: in that one we want to show that we can always re-index them so that $A_i\cap B_i\color{red}{\ne}\varnothing$. $\endgroup$ Commented Nov 1, 2020 at 18:52
  • $\begingroup$ Oops sorry about that, my bad. $\endgroup$
    – hirohe
    Commented Nov 1, 2020 at 18:55

You must log in to answer this question.

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