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 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.

share|improve this question
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. –  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
1  
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

1 Answer 1

up vote 1 down vote accepted
+100

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$.

share|improve this answer
    
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

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.