Distinguishing between two sets of tournament partition

60 Views Asked by At

A "tournament" is a complete graph such that each edge is directed one way or the other (but not both). Does there exist a tournament of size $2n$ such that we can partition it into two sets $A,B$, each of size $n$, where we "cannot distinguish between $A$ and $B$"?

I put "cannot distinguish between $A$ and $B$" in quotes because I'm not sure how to define it formally. But I'll give you some examples.

$n=1$: The tournament is just two vertices $a,b$, where $a\rightarrow b$. Clearly we can distinguish between $a$ and $b$ (one has out-arrow, the other has in-arrow)

$n=2$: Suppose we choose $A=\{a,b\},B=\{c,d\}$. Let's say $a\rightarrow b$ and $c\rightarrow d$. Then we can distinguish between $A$ and $B$ by looking at whether the edge $a\rightarrow c$ or $c\rightarrow a$ exists.

So for $n=1,2$, we can always distinguish between the two sides. What about for higher $n$?

1

There are 1 best solutions below

0
On BEST ANSWER

Note that if you can check whether $x\rightarrow y$ or $y\rightarrow x$, then you can distinguish between sets $A$ and $B$ by taking any $x\in A$ and $y\in B$ and checking the direction of the edge between $x$ and $y$.

However, if you cannot do this - and instead we call subsets indistinguishable if they are isomorphic - the question becomes more involved.

First, take $n$ to be odd. Then the total number of edges in the complete graph on $2n$ vertices is $\binom{2n}{2}=n(2n-1)$, but since $n$ is odd and $2n-1$ is odd, the number of edges is odd, so we will be able to distinguish $A$ and $B$ because they must have different numbers of in-edges (and out-edges).

On the other hand, when $n$ is even, we can partition the graph into a pair of isomorphic sets. To begin, we create just the edges between $A$ and $B$. These edges form the complete bipartite graph $K_{n,n}$. Since the degree of each vertex in this complete bipartite graph is even (the degree of each vertex is $n$), there exists an Eulerian cycle. This means we can take an Eulerian orientation on $K_{n,n}$ (an Eulerian orientation is an assignment of directions such that the indegree is equal to the outdegree for each vertex). Now any (injective) mapping from one vertex set to the other vertex set forms an isomorphism. Finally, given this mapping we can choose freely any direction of edges in $A$ and then copy those directions for edges in $B$ to create the two sets $A$ and $B$ such that they are indistinguishable. I have included a graphic for $n=2$ (take the sets $A$ and $B$ as the top and bottom $2$ vertices).

dgn2