Given $n$ sets $A_i$, with $| A_i | = n$, prove they may be indexed $A_i = \{a_{i,j} \mid j=1,2,\ldots,n \}$, in such way that the sets $B_j = \{a_{i,j} \mid i=1,2,\ldots,n \}$, $1\leq j\leq n$, also have $| B_j | = n$. (Anonymous)
Problem
Source: Stars of Mathematics - Seniors - Problem 4
Tags: graph theory, combinatorics proposed, combinatorics
11.10.2012 13:41
Let the $B_i$ be multi-sets. We want all their values to be distinct so take an arbitrary indexation and suppose that $x$ appears more than once in $B_j$. Then there must exists $k$ such that $x \not \in B_k$ (because $x$ appears at most $n$ times amongst all $B_i$) (*). Consider the bipartite graph with vertex set $B_j \cup B_k$. Draw an edge between vertices that come from the same set $A_i$, and between vertices $(y,y)\in B_j \times B_k$. Then evidently different copies of $x$ lie in separate connected components because of (*). Take the vertices from a connected component that includes one copy of $x$ and swap the indexations $a_{i,j}\leftrightarrow a_{i,k}$. This decreases the number of sets with repeated elements, so eventually this process leads to all $B_i$ containing distinct elements.
01.08.2017 14:48
Write all sets as the rows of an $n\times n$ matrix.Consider a graph $G$ which is n-partite with partite classes of the same cardinality $n$ (kinda like $n\times n$ square) with $n^2$ vertices and we connect two iff the corresponding numbers in the rows are the same. Lemma:Consider all edge transitive subgraphs on an $n$-partite graph $G$.Prove that all these subgraphs are induced subgraphs of $n$ independent $K_n$'s with edge set same as that of $G$. Proof. We induct on the number of edges of a subgraph $H$ and suppose for argument's sake that $H$ is not 1-regular.If there isn't any edges it's obvious.Now take a vertex $v$ of $H$ so that $\text{deg}(v)\geq 2$ and simply delete one of the edges coming out of it say $e$ connecting $v-v_k$.Let $H'=H \setminus e$ by induction we can make $H'$ a subgraph of disjoint $K_n$.Let $v\in K_{j n}$ and note that $v_k$ is incident to some guy from the neighborhood of $v$(by edge transitivity) and so it can't be in any other $K_{d n}$ $\implies$ $v_k\in K_{j n}$ and hence we can add $e$ back to $H'$ with no problems. Note that the lemma allows us to prove the problem for sets where $A_1=A_2=...=A_n$.Say let wlog $A_1=\{1,2\dots n\}$ and consider a matrix so that $a_{ij}=i$ $\forall i,j$.Now just permute it so that $a_{ij}\equiv_n i+j$,rows stay permuted and columns are made of all different numbers as desired.$\blacksquare$