Krdytkyu

Let $X$ be a nonempty finite set. Without loss of generality, we can take $X = {1, 2 cdots ,n}$.

A $textit{partition}$ $mathcal{P} = {X_1, X_2 cdots X_k}$ of $X$ is a collection of pairwise disjoint nonempty subsets of $X$ whose union is $X$.

We say a partition $mathcal{P} = {X_1, X_2 cdots X_k}$ is $textit{balanced}$ if there exists a positive integer $ell$ such that $ell = |X_i|$ for all indices $i$. This number $ell$ is then called the $textit{proportion}$ of $mathcal{P}$ and we have the obvious relation $|X| = ell k$.

Finally, we say a set $T subset X$ is a $textit{traversal}$ of a partition $mathcal{P} = {X_1, X_2 cdots X_k}$ if it is the image of some function $f:mathcal{P} to X$ with the property $f(x) in x$ for any $x in mathcal{P}$.

Conjecture: If $mathcal{P}_1, mathcal{P}_2$ are any two balanced partitions of $X$ with the same proportion (say $ell$), there exists a $T subset X$ which is a traversal for both $mathcal{P}_1$ and $mathcal{P}_2$ (i.e., a simultaneous traversal).

Examples: $X={1,2,3,4,5,6}$ and partitions $mathcal{P}_1 = {{1,2}, {3,4}, {5,6}}$, and $mathcal{P}_2 = {{1,6}, {3,5}, {4,2}}$. Then $T={1,4,5}$ is a simultaneous traversal.

Context: This arises as a generalization of a group theory problem. Specifically, if one has a group $G$ and a (not necessarily normal) subgroup $H$, then one can find a set $T subset G$ which is a set of representatives for both the left and right cosets of $H$. The proof for this specific claim which I'm aware of uses group-theoretical concepts, so I'm not sure if it can be generalized to solve the above conjecture. Perhaps, in solving the more general problem, Hall's marriage theorem might be useful, although I have not been able to get this to work.

The existence of a simultaneous traversal is equivalent to the following statement:

Let $mathcal P_1$ and $mathcal P_2$ be two balanced traversals of the same proportion $ell$. Then, there exists a bijection $f:mathcal P_1rightarrow mathcal P_2$ such that $X_icap f(X_i)neq emptyset$ for all $X_iin mathcal P_1$.

To see the equivalence, just note that if we had such a bijection, we could choose elements of each set $X_icap f(X_i)$ to get a simultaneous traversal. Conversely, if we had a simultaneous traversal $T$, we can set $f(X_i)$ to be the element of $P_2$ containing the singleton $X_icap T$.

This statement is straightforwards to prove by Hall's Marriage Theorem. In particular, it becomes equivalent to the following marriage condition:

Any subset $Ssubseteq mathcal P_1$ has that $bigcup S$ intersects at least $|S|$ elements of $mathcal P_2$.

This is clear because $bigcup S$ has $|S|cdot ell$ elements, so the elements of $mathcal P_2$ intersecting $bigcup S$ must cover at least $|S|cdot ell$ elements as well, so there must be at least $ell$ of them.