Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on the following questions but with no luck so I was hoping maybe someone can come up with help.

Let $T$ be a tournament on $n$ vertices, say $\left\{v_{1},\ldots,v_{n}\right\}$, and let $B(T)$ be the graph on the same vertices $v_{1},\ldots,v_{n}$ so that for $i<j$, $v_{i}v_{j}$ is an edge of $B(T)$ if $v_{j} \rightarrow v_{i}$ is an edge of $T$. In other words, $B(T)$ is the graph of backward edges of $T$. A transitive subset of $T$ is a subtournament that has no directed cycle. Furthermore, let $u$ be the size of the largest transitive set of $T$ and $y$ be the size of the largest clique or stable set of $G$.

  1. If $x$ is bounded (independent of $n$) does it follow that $y$ is bounded?
  2. If $y$ is bounded does it follow that $x$ is bounded?

Considering the literature, I feel like the answer for 1 should be yes and for 2 no, but I really don't see it. Maybe someone can help me. I think the problem is very interesting. The analogy between transitive subsets of tournaments and cliques and stable sets comes basically from the dualization of the Erdos-Hajnal conjecture for tournament. Erdos proved some bounds for x but I really don't think we need them here.

Note. I also posted this on MathOverflow because I'm not really sure how difficult it can be... it's either very easy or hard.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

If I haven't misunderstood your question (I assume $u$ means $x$), I think it does fall under "very easy". Note that $x \ge y$ for any $T$: any clique in $B(T)$ corresponds to an "all-backwards" subtournament of $T$ which is necessarily transitive. So the answer to 1 is yes.

The answer to 2 is no in a strong sense: if $y$ is bounded then $x$ is necessarily unbounded as a function of $n$. This follows readily from Ramsey's theorem: since $B(T)$ has no clique of size $y+1$, it must contain an independent set of size $x$ once $n$ is larger than $R(x,y+1)$. This independent set corresponds to an "all-forward" subtournament of $T$ which is again transitive.

share|improve this answer
    
Darn, you are right. Everything seems correct. I guess I just confused myself too much with these diagrams... –  TJIF Feb 12 '13 at 6:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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