# 线性代数网课代修|ENGO361代写|ENGO361英文辅导|ENGO361

4 Rainbow directed $S_{1,1}$In this section we consider $c\geq 2$ directed graphs $G_{1},G_{2},\ldots,G_{c}$ on a common vertex set and forbid a rainbow star $S_{1,1}$, which is a directed path of length $2$. The following theorem provides the optimal bound for the sum of the number of edges in all graphs.**Theorem**.: _For integers $c\geq 2$ and $n\geq 3$, every collection of directed graphs $G_{1},\ldots,G_{c}$ on a common set of $n$ vertices containing no rainbow $S_{1,1}$ satisfies_$\sum_{i=1}^{c}e(G_{i})\leq\begin{cases}n^{2}-n&\text{if }c\leq 3, c\big{\lfloor}\frac{n^{2}}{4}\big{\rfloor}&\text{if }c\geq 4.\end{cases}$_Moreover, the above bounds are sharp._Proof.: The bound for $c\leq 3$ is obtained when $G_{1}$ is a complete directed graph and all $G_{i}$ for $i\in[c]\setminus\{1\}$ are empty graphs. While for $c\geq 4$ the bound is achieved when each graph is the same balanced complete bipartite graph with all edges oriented in the same direction. This is depicted in We prove the upper bound by induction on $n$. For $n=3$ and $n=4$ it is easy to verify that the bound holds. Consider then a collection of directed graphs $G_{1},\ldots,G_{c}$ on a common set $V$ of $n\geq 5$ vertices containing no rainbow $S_{1,1}$ and assume that the bound holds for all collections on a smaller number of vertices.For a subset $U\subset V$ and a vertex $v\in V$ by $e(U,v)$ we denote the total number of edges in all graphs $G_{1},\ldots,G_{c}$ between the set $U$ and the vertex $v$. If $U$ consists of only one vertex $u$, we write $e(u,v)$ instead of $e(\{u\},v)$ for brevity.Assume first that there are two vertices $u$ and $v$ such that there exists an edge $uv$ in at least two colors. To avoid rainbow $S_{1,1}$, for each vertex $x\in V\setminus\{u,v\}$, there are no edges $xu$ nor $vx$, and if $ux\in E(G_{i})$ and $xv\in E(G_{j})$, then $i=j$. This means that $e(\{u,v\},x)\leq c$. Moreover, if there is an edge $vu$ in some color, then between $\{u,v\}$ and $x$ we can have edges only in that color, so $e(\{u,v\},x)\leq 2$. Consider those cases separately. If $e(u,v)\leq c$, then, together with the inductive assumption on $V\setminus\{u,v\}$, for $c\leq 3$ we obtain$\sum_{i=1}^{c}e(G_{i})\leq c+c(n-2)+(n-2)^{2}-(n-2)=n^{2}-n-(3-c)(n-1)-(n-3) \leq n^{2}-n,$ while for $c\geq 4$ we have$\sum_{i=1}^{c}e(G_{i})\leq c+c(n-2)+c\left\lfloor\frac{(n-2)^{2}}{4}\right\rfloor= c\left\lfloor\frac{n^{2}}{4}\right\rfloor.$On the other hand, if $e(u,v)>c$, then for $c\leq 3$ we obtain$\sum_{i=1}^{c}e(G_{i})\leq 2c+2(n-2)+(n-2)^{2}-(n-2)=n^{2}-n-2(n-4)-2(3-c)\leq n ^{2}-n,$while for $c\geq 4$ we have$\sum_{i=1}^{c}e(G_{i})\leq 2c+2(n-2)+c\left\lfloor\frac{(n-2)^{2}}{4}\right\rfloor =c\left\lfloor\frac{n^{2}}{4}\right\rfloor-(c-4)(n-3)-2(n-4)\leq c\left\lfloor \frac{n^{2}}{4}\right\rfloor.$Therefore, we are left with the case when between any pair of vertices there are at most two edges (at most one edge in each direction). But then $\sum_{i=1}^{c}e(G_{i})\leq 2\binom{n}{2}=n^{2}-n$, which gives the correct bound for $c\leq 3$ and is smaller than $c\left\lfloor\frac{n^{2}}{4}\right\rfloor$ for $c\geq 4$, as desired. Since the extremal construction for $c\geq 4$ in has the same number of edges in each graph, this theorem immediately implies the optimal bound for $\min_{1\leq i\leq c}e(G_{i})$ if $c\geq 4$. We will show that for $c\leq 3$ the same bound holds.**Theorem**.: _For any integers $c\geq 2$ and $n\geq 4$, every collection of directed graphs $G_{1},\ldots,G_{c}$ on a common set of $n$ vertices containing no rainbow $S_{1,1}$ satisfies_$\min_{1\leq i\leq c}e(G_{i})\leq\left\lfloor\frac{n^{2}}{4}\right\rfloor.$_Moreover, this bound is sharp._Proof.: The bound is achieved when each graph is the same balanced complete bipartite graph with all edges oriented in the same direction (see Note that it is enough to consider $c=2$, because if the theorem is true for $2$ colors, then it also holds for any larger number of colors. We proceed by induction on $n$. For $n=4$ it is easy to verify that the theorem holds (note that for $n=3$ it is not true as one can have a directed triangle oriented clockwise in $G_{1}$ and anticlockwise in $G_{2}$). Consider then two directed graphs $G_{1}$, $G_{2}$ on a common set $V$ of $n\geq 5$ vertices containing no rainbow $S_{1,1}$ and assume that the theorem holds for all pairs of graphs on a smaller number of vertices. Assume first that there exists a vertex $v\in V$ incident to at most $2$ edges in each of the graphs. Then, from the induction assumption on $V\setminus\{v\}$ we obtain\[\min_{1\leq i\leq 2}e(G_{i})\leq 2+\left\lfloor\frac{(n-1)^{2}}{4}\right\rfloor= \left\lfloor\frac{n^{2}-2n+9}{4}\right\rfloor\leq\left\lfloor\frac{n^{2}}{4} \right\rfloor