European Mathematical Cup

We will for simplicity and clarity of presentation use some basic graph theoretic terms, this is in no way essential. We represent the situation by a directed graph (abbr. digraph) $G(V,E)$ where each vertex $v\in V(G)$ represents a mathematician and each edge $e\in E(G)$ represents an admiration relation. Given $v\in V(G)$ we define out-degree of $v$ denoted $o(v)$ as the number of edges starting in $v$ (so the number of mathematicians $v$ admires) and in-degree $i(v)$ as the number of edges ending in $v$ (so the number of mathematicians who admire $v$). Given $X\subseteq V$ by $G(X)$ we denote the induced subgraph (a graph with vertex set $X$ and edges inherited from $G$). We say that a digraph is a $k$-digraph if for every $v\in V(G)$ we have $i(v)\ge k$ or $o(v)\ge k$. So the question can be reformulated as: Given $G$ is a $3k+1$-digraph we can split its vertices into 2 vertex disjoint classes such that each induced subgraph on class is a $k$-digraph. We call a subset $X$ of vertices of $G$ $k$-tight if for any $Y\subseteq X$ we have a vertex $v\in Y$ such that $i_{\{G(Y)\}}(v)\le k$ and $o_{\{G(Y)\}}(v)\le k$. A partition of $V$, $(A_1,A_2)$ is feasible if $A_1$ is $k$-tight and $A_2$ is $k$-tight. We first assume there are no feasible partitions. In this case consider a minimal size subset $A_1\subseteq V(G)$ subject to $G(A_1)$ being a $k$-digraph, we define $A_2=V(G)-A_1$. Given a subset $X\subset A_1$, $G(X)$ is not a $k$-digraph so there is a vertex $v\in X$ such that $o_{\{G(X)\}}(v)<k$ and $i_{\{G(X)\}}(v)<k$ which shows that any proper subset of $A_1$ satisfies the condition of $k$-tightness. For the case of $X=A_1$ by removing any vertex $v\in A_1$ the graph $G^{\prime }=G(A_1-\{v\})$, by minimality assumption on $A_1$, must contain a vertex $w$ such that $o_G(w)<k$ and $i_G(w)<k$ so as there is only one extra vertex in $G(A_1)$, namely $v$ $o_{\{G(A_1)\}}(w)\le k$, $i_{\{G(A_1)\}}(w)\le k$. In particular this shows $A_1$ is $k$-tight. This implies $A_2$ is not $k$-tight by our assumption so there exists an $A_2^{\prime }\subseteq A_2$ such that $A_2^{\prime }$ is a $k+1$-digraph. Now applying the following proposition to extend the pair $(A_1,A_2^{\prime })$ to a full partition which satisfies the condition of the problem. Given disjoint subsets $A,B\subseteq V(G)$ we say $(A,B)$ is a solution pair if both $G(A)$ and $G(B)$ are $k$-digraphs. Proposition. If a $2k+1$ digraph $G$ admits a solution pair it admits a partition with both induced graphs of both classes being $k$-digraphs. Proof. Take a maximal solution pair $(A,B)$, the condition in the lemma guaranteeing it exists. Let $C=V(G)-(A\cup B)$, if $C$ is empty we are done so assume $|C|>0$. By our assumption $(A,B\cup C)$ is not a solution pair so there is some $x\in C$ such that $o_{\{G(B\cup C)\}}(x),i_{\{G(B\cup C)\}}(x)<k$ so as $G$ is $2k+1$ digraph $i_G(x)\ge 2k+1$ or $o_G(x)\ge 2k+1$ so either $o_{\{G(A\cup \{x\})\}}(x)>k+1$ or $i_{\{G(A\cup \{x\})\}}(x)>k+1$ so in particular $(A\cup \{x\},B)$ is a solution pair contradicting maximality and completing our argument. Hence we are left with the case in which we have at least one feasible partition. We pick the feasible partition $(A,B)$ maximizing $w(A<B)=|E(G(A))|+|E(G(B))|$. The fact that $A$ is $k$-tight implies there is an $x$ with $o_{\{G(A)\}}(x)\le k$, $i_{\{G(A)\}}(x)\le k$ so $x$ needs to have at least $k+1$ edges in or out of $B$ so $|B|\ge k+1$ and by symmetry $|A|\ge k+1$. We now prove that there exist an $X\subseteq A$ such that $G(X)$ is a $k$-digraph, by contradiction. Assuming the opposite we notice that for any $x\in B$, $B-\{x\}$ is still $k$-tight while $B$ being $k$-tight implies there is an $x\in B$ such that $o_{\{G(B)\}}(x)\le k$, $o_{\{G(B)\}}(x)\le k$ so for this $x$ we have $A\cup \{x\}$ is also $k$-tight. Hence, for $A^{\prime }=A\cup \{x\}$ and $B^{\prime }=B-\{x\}$, $(A^{\prime },B^{\prime })$ is a feasible partition. We considering the change in edges which moving $x$ causes we have $w(A^{\prime },B^{\prime })-w(A,B)\ge 3k+1-k-k-k=1$ as we know $i_{\{G(X)\}}\ge 3k+1$ or $o_{\{G(X)\}}\ge 3k+1$ so moving $x$ from $B$ to $A$ increases number of edges in $A$ by at least $3k+1-k$ while the choice of $x$ in $B$ means we lose at most $k+k$ edges in $B$. This is a contradiction to maximality of $(A,B)$. Analogously we can find $Y\subseteq B$ with $G(Y)$ a $k$-digraph. Now applying the above proposition yet again we are done.