3
$\begingroup$

Let $T$ be a regular tournament, and $u \in V(T)$. Let $Out(u) \subset V(T)$ denote the set of vertices such that the edges between $u$ and them go out of $u$. Similarly define $In(u)$. Let two distinct vertices $u,v$ be called $\textbf{antipodal}$ if $Out(u) \setminus v = In(v) \setminus u$ (and thus also $In(u) \setminus v = Out(v) \setminus u$). Put more concretely, if $w$ is any other vertex, then either $u$ goes into $w$ AND $w$ goes into $v$, or vice versa.

Given $u$, let $v$ be called an $\textbf{antipode}$ of $u$ if $u$ and $v$ are antipodal. Note that this is poor notation as $u$ could have more than one antipode.

Does every regular tournament have an antipodal pair of vertices? Furthermore, does every vertex have at least one antipode?

Note that the first problem is equivalent to showing that a regular tournament on $2n+1$ vertices contains an induced subgraph on $2n-1$ vertices that is a regular tournament.

The motivation for this problem is the following observation (if it's correct). $T$ has a size $2n-1$ subgraph that is a regular tournament if and only if, for any partition of $2n+1$ into odd numbers, $T$ can be partitioned into regular tournaments as subgraphs of sizes corresponding to the partition.

Perhaps this result is too strong to be true, I have only verified it for some very small examples.

$\endgroup$
2
  • $\begingroup$ The definition of Out(u) depends on Out(u)? $\endgroup$ Jul 7 at 2:14
  • $\begingroup$ ah right let me fix that, thanks $\endgroup$ Jul 7 at 2:16

2 Answers 2

3
$\begingroup$

There are regular tournaments here and if you choose one at random except on the smallest sizes you will find a counterexample with high probability.

Enumeration gives a bound (which could be turned into an accurate estimate but I won't). Let $T(n)$ be the number of (labelled) regular tournaments with $n$ vertices. To make a regular tournament with $n+2$ vertices and an antipodal pair, take a regular tournament with $n$ vertices and add to it to new vertices $v\to w$. There are less than $2^n$ ways to add the edges between the new vertices and the old vertices such that $v,w$ are antipodal, then you can multiply by $n^2$ for the labels of the new vertices. So the number of regular tournaments on $n+2$ vertices that have an antipodal pair is at most $n^2 2^n T_n$. However, $T_{n+2}$ is approximately $2^{2n}n^{-1}T_n$. So only an exponentially small fraction of regular tournaments have an antipodal pair.

Ref for enumeration: B. D. McKay, The asymptotic numbers of regular tournaments, eulerian digraphs and eulerian oriented graphs, Combinatorica, 10 (1990) 367-377.

$\endgroup$
4
$\begingroup$

This looks like a rare property, and it is. For example, you may take the residues modulo $2n+1$ as a vertex set; choose a random subset $A\subset \{-n, \dots, - 1,1, \dots, n\}$ satisfying the property $|A\cap \{-a, a\}|=1$ for all $a=1,\ldots,n$, and draw edges from $x$ to $x+A$ for all residues $x$ modulo $2n+1$.The probability that $(x+A) \setminus y=(y-A)\setminus x$ is exponentially small for all $x\ne y$. Thus for almost all $A$ you do not have antipodes.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.