Skip to main content
added 16 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any odd (per bof) $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes. As bof notes in comment this is not so.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes. As bof notes in comment this is not so.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any odd (per bof) $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes. As bof notes in comment this is not so.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

added 49 characters in body
Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger thanThe next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes. $T$. I'm guessing yes.As bof notes in comment this is not so.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes. As bof notes in comment this is not so.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.

Source Link
Brendan McKay
  • 37.7k
  • 3
  • 80
  • 147

bof got it right in a comment; here are the details. Let $T$ be a tournament with $n$ vertices. Label the vertices $v_1,\ldots,v_n$ in any way such that the $\binom n2$ values $|v_i-v_j|$ are distinct. Example: $v_i=2^i$. Now, for any $N$ greater than twice the largest label, make a cyclic tournament where for each $1\le i,j\le n$ and $0\le k\lt N$ the edge from $k$ to $k+v_j-v_i \pmod N$ has the same direction as the edge from $i$ to $j$ has in $T$.

The next question is whether the transitive tournament must sometimes be exponentially larger than $T$. I'm guessing yes.

Regarding Andreas' answer, note that my answer is only for the finite case, though maybe it works in the countable case too.