# About regular induced subgraphs of regular tournaments

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.

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

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.
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.