A tournament on $2k$ vertices contains no $7$-cycles. Show that its vertices can be partitioned into two sets, each with size $k$, such that the edges between vertices of the same set do not determine any $3$-cycles. Calvin Deng.
Problem
Source: ELMO Shortlist 2012, C4
Tags: induction, floor function, ceiling function, inequalities, pigeonhole principle, combinatorics proposed, combinatorics
29.10.2012 23:01
here is an outline for what I did (without any details): lemma 1.tournament $T$ isn't strongly connected so we can partition $T$ into two non-empty subgraphs $A$ and $B$ such that all the edges between $A$ and $B$ are from $A$ to $B$. lemma 2. tournament $T$ with $n$ vertices is strongly connected so we can find a cycle with length $k$ in $T$.(for all $3\leq k \leq n$) now suppose the problem is true for $k=1,2,3,4,5$. because our tournament,say it $T$, contains no $7$-cycle and lemma $2$ we know that $T$ isn't strongly connected.hence apply lemma $1$ and partition $T$ into $A$ and $B$.now consider two cases : $1.$ $A$ and $B$ are even. for this case use the induction hypothesis and partition $A$ into $A_{1},A_{2}$ and $B$ into $B_{1},B_{2}$ and then consider $A_{1}\cup B_{1}$ and $A_{2}\cup B_{2}$ for our desired partition $2.$ $A$ and $B$ are odd.assume $\left | A \right |\geq \left | B \right |$. use again lemma $2$ so we partition $A$ into to subgraphs $A_{1}$ and $A_{2}$ such that all the edges between two subgraphs are from $A_{1}$ to $A_{2}$.again consider two cases: $a.$ $A_{1}$ is even and $A_{2}$ is odd. consider $A_{1}$ and $A_{2}\cup B$ and back to the case $1$ $b.$ $A_{1}$ is odd and $A_{2}$ is even. now consider $A_{2}$ and $A_{1}\cup B$.then use induction hypothesis and partition $A_{2}$ into $X_{1},X_{2}$ and partition $A_{1}\cup B$ into $Y_{1},Y_{2}$ now $X_{1}\cup Y_{1}$ and $X_{2}\cup Y_{2}$ have our desire property.so we are done
19.11.2012 05:39
mlm95 wrote: lemma 1.tournament $T$ isn't strongly connected so we can partition $T$ into two non-empty subgraphs $A$ and $B$ such that all the edges between $A$ and $B$ are from $A$ to $B$. lemma 2. tournament $T$ with $n$ vertices is strongly connected so we can find a cycle with length $k$ in $T$.(for all $3\leq k \leq n$) Yes; this means we can partition $T$ into strongly connected graphs $A_i$ (equivalently, $A_i$ that contain full cycles) for $i=1,2,\ldots,m$ such that whenever $i<j$, all edges between $A_i$ and $A_j$ are directed toward $A_j$. (USA TST 2009.6 also uses this fact.) But we can similarly show that $|A_i|\le 6$ for all $i$ (otherwise $T$ has a 7-cycle), so it suffices to show that every strongly connected tournament $G$ with $n\le6$ vertices can be partitioned into two transitive sub-tournaments of size $\lfloor{n/2}\rfloor$ and $\lceil{n/2}\rceil$, which is relatively simple to verify: for $n\le 4$, it's obvious; for $n=5$, a counterexample would require every partition to have at least one triangle, so at least $\binom{5}{3}=10$ triangles total; for $n=6$, a counterexample would require every partition to have at least one triangle, so at least $\frac{1}{2}\binom{6}{3}=10$ triangles in all. But it's easy to show that there are $\binom{n}{3}-\sum_{v\in G}\binom{d(v)}{2}\le \binom{n}{3}-n\binom{\binom{n}{2}/n}{2}$ triangles in $G$ by Jensen, so the rest is just computation. We also cannot replace 7 with any larger number: suppose $k=4$, $m=2$, $|A_1|=1$, $|A_2|=7$, and $A_2$ is the graph with vertex set $S=\mathbb{Z}/7\mathbb{Z}$ and edges satisfying $x\to \{x+1,x+2,x+4\}$ for every $x\in S$ (this is well-defined since $0\notin \{1,2,4\}+\{1,2,4\}$). Assume for the sake of contradiction that $T=A_1\cup A_2$ can be partitioned into two transitive sets of size 4; then there must exist a set $U$ of 4 vertices in $A_2$ such that $U$ and $V=S\setminus U$ each have no 3-cycles. By pigeonhole, $U$ must have some two neighboring residues, so WLOG assume $0,1\in U$. Now observe that $0\to_1 1\to_2 3\to_4 0$ and $0\to_1 1\to_4 5\to_2 0$ form 3-cycles, so $3,5\notin U\implies 3,5\in V$. But $2\to_1 3\to_2 5\to_ 4 2$, so $2\notin V\implies 2\in U$, contradicting the fact that $1\to_1 2\to_2 4\to_4 1$ and $0\to_2 2\to_4 6\to_1 0$ are both 3-cycles (as $U$ must contain one of $4,6$).