1
$\begingroup$

I want to show that there exists $c>0$ constant s.t for any tournament on $n$ vertices there are two disjoint subsets A and B s.t:

$ e(A,B)-e(B,A) \geq c n^{\frac{3}{2}}$

I know of the theorem that says that for $\min \{FIT(T,\sigma) , \sigma \in S_n \} \leq O(n^{\frac{3}{2}})$, but I don't see how this can help me here, can it?

Any hints, are appreciated.

Thanks.

  • 0
    OK, I see that also forgot to say that $e(A,B)$ is the number of directed edges from $A$ to $B$, don't know why I thought it should be clear...2012-04-08

1 Answers 1

1

Maybe I missed something, because it seems quite simple.

You could show this by spliting graph vertex set $V$ on two (almost) equal parts. To fix the idea, let $n$ be even and let $A \cup B$ be some partition of $V$ such that $|A| = |B| = n/2$. There are $n^2/4$ (undirected) edges between $A$ and $B$ and at least $n^2/8$ directed edges either from $A$ to $B$ or from $B$ to $A$ (by pigeonhole principle).

Now it is easy to select $c$ such that $n^2/8 \geq cn^{3/2}$, for all $n \geq 1$. If I'm not mistaken you could take $c=0.1$.

  • 0
    Sorry, my arguments are incorrect. I misunderstood the problem. I only showed that $e(A,B) \geq cn^{3/2}$ or $e(B,A) \geq cn^{3/2}$.2012-04-11