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.

  • 1
    $\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.2012-04-07
  • 0
    Guess he meant $\in\mathcal{O}\left(n^{3/2}\right)$ (as $n\rightarrow\infty$). No idea what FIT is though.2012-04-07
  • 0
    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$(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$. – 2012-04-07
  • 1
    Yes, it's better understood now what it is, but it's even less understood now why you thought everyone would know that :-)2012-04-07
  • 0
    Who knows, I am a weird bloke. Anyhow, does someone know how to prove the claim, even references are fine by me. Thanks...2012-04-07
  • 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