# Question on the number of directed edges in a tournament.

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.

-
$\le O(n^{3/2})$ makes no sense. What is $FIT$? Presumably $e(A,B)$ is the number of edges from $A$ to $B$? Generally, it's a good idea to introduce your notation unless you're quite certain that it's standard and well-known to everyone; this is particularly true in graph theory, where various different conventions and notations are in use. – joriki Apr 7 '12 at 10:58
Guess he meant $\in\mathcal{O}\left(n^{3/2}\right)$ (as $n\rightarrow\infty$). No idea what FIT is though. – example Apr 7 '12 at 11:10
definition of $$FIT(T,\sigma)=|edges \ of \ T \ consistent \ with \ \sigma|-|edges \ of \ T \ inconsistent \ with \ \sigma |$$ where consistency is defined by the direction of the edge is the same as in the permutation $\sigma$ of the vertices. i.e if i<j, and there's an edge $(i,j) \in E$ then $\sigma(i) <\sigma(j)$ and $(\sigma(i),\sigma(j)) \in E$. I hope now it's better understood what is $FIT$. – MathematicalPhysicist Apr 7 '12 at 11:11
Yes, it's better understood now what it is, but it's even less understood now why you thought everyone would know that :-) – joriki Apr 7 '12 at 15:52
Who knows, I am a weird bloke. Anyhow, does someone know how to prove the claim, even references are fine by me. Thanks... – MathematicalPhysicist Apr 7 '12 at 16:48

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$.
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}$. – Victor Apr 11 '12 at 16:06