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

2 Rainbow directed $S_{0,q}$In this section the forbidden rainbow graph is a directed star with all edges oriented away from the center. As noted earlier, the problem is the same if we forbid a directed star with all edges oriented to the center. The following theorem provides the optimal bound for the sum of the number of edges in all graphs.**Theorem**.: _For integers $n>c\geq q\geq 1$, every collection of directed graphs $G_{1},\ldots,G_{c}$ on a common set of $n$ vertices containing no rainbow $S_{0,q}$ satisfies_$\sum_{i=1}^{c}e(G_{i})\leq(q-1)(n^{2}-n).$_Moreover, this bound is sharp._Proof.: The sharpness of the bound follows from taking a collection of $q-1$ complete graphs, but there are more extremal constructions. We split the vertex set into disjoint subsets and _assign_ to each of them a different set of $q-1$ colors. This way each vertex has $q-1$ colors assigned. Then, for any two vertices $u$, $v$ and color $i\in[c]$, we add edge $uv$ to $G_{i}$ if color $i$ is assigned to $u$. Clearly this construction does not contain a rainbow $S_{0,q}$ as no vertex has positive outdegree in $q$ graphs, and each vertex has the sum of outdegrees over all graphs equal to $(q-1)(n-1)$ giving the total number of edges equal to $(q-1)(n^{2}-n)$. An example construction of this type is shown in To prove the upper bound, consider a collection of graphs $G_{1},G_{2},\ldots,G_{c}$ on a common set $V$ of $n$ vertices that does not contain a rainbow $S_{0,q}$. Let $v\in V$ be an arbitrary vertex. We will show that the total number of edges outgoing from $v$ is bounded by $(q-1)(n-1)$by connecting vertex $u\in V\setminus\{v\}$ and color $i\in[c]$ if $vu\in E(G_{i})$. The number of edges in $H$ is equal to the number of outgoing edges from $v$ that we want to bound. Note that the existence of a matching of size $q$ in $H$ means that there exists a rainbow $S_{0,q}$ with center $v$, which is not possible. Therefore, the maximum matching in $H$ is of size at most $q-1$. From Konig’s theorem this means that the minimum vertex cover is also of size at most $q-1$. As $n-1\geq c$, this implies that the maximum number of edges in $H$ is bounded by $(q-1)(n-1)$, as desired. By summing it over all vertices we obtain $\sum_{i=1}^{c}e(G_{i})\leq(q-1)(n^{2}-n)$. Note that the bound $n>c$ in is indeed needed, as otherwise the following collections of graphs contradict the theorem. If $c\geq n\geq q$, for each vertex $v$, add edges in each color from $v$ to $q-1$ other arbitrary vertices. This way$\sum_{i=1}^{c}e(G_{i})=(q-1)cn>(q-1)(n^{2}-n)$and there is no rainbow $S_{0,q}$. While if $n\leq q$, then a collection of complete directed graphs does not contain rainbow $S_{0,q}$ and satisfies$\sum_{i=1}^{c}e(G_{i})=c(n^{2}-n)>(q-1)(n^{2}-n).$The same constructions also provide an exact bound for $\min_{1\leq i\leq c}e(G_{i})$ for any $n\leq c$. implies that for integers $n>c\geq q\geq 1$, every collection of directed graphs $G_{1},\ldots,G_{c}$ on a common set of $n$ vertices containing no rainbow $S_{0,q}$ satisfies$\min_{1\leq i\leq c}e(G_{i})\leq\frac{q-1}{c}\left(n^{2}-n\right).$Moreover, if $n(q-1)$ is divisible by $c$, then one can make a construction as detailed in the beginning of the proof of , in which the number of edges in each graph is the same (see **Theorem**.: _For integers $n>c\geq q\geq 1$, every collection of directed graphs $G_{1},\ldots,G_{c}$ on a common set of $n$ vertices containing no rainbow $S_{0,q}$ satisfies_$\min_{1\leq i\leq c}e(G_{i})\leq\left\lfloor\frac{n(q-1)}{c}\right\rfloor(n-1)+r,$_where $r$ is the remainder of $n(q-1)$ when divided by $c$. Moreover, this bound is sharp._Proof.: We proceed similarly as in the proof of . Consider a collection of graphs $G_{1},G_{2},\ldots,G_{c}$ on a common set $V$ of $n$ vertices that does not contain a rainbow $S_{0,q}$. For any vertex $v\in V$ we consider an auxiliary bipartite graph $H$ between the vertices $V\setminus\{v\}$ and colors in $[c]$ created by connecting vertex $u\in V\setminus\{v\}$ and color $i\in[c]$ if $vu\in E(G_{i})$. Since the existence of a matching of size $q$ in $H$ means that there exists a forbidden rainbow $S_{0,q}$ centered in $v$, the maximum matching in $H$ is of size $q-1$. From Konig’s theorem the minimum vertex cover is also of size at most $q-1$. Let $a_{v}$ and $b_{v}$ be the numbers of vertices in the minimum vertex cover that are in the part of $H$ related with the colors and in the part related with the other vertices, respectively. In particular, in $a_{v}$ colors there are at most $n-1$ edges outgoing from $v$ and in all other colors there are at most $b_{v}$ edges outgoing from $v$. Let $a=\sum_{v\in V}a_{v}$ and $b=\sum_{v\in V}b_{v}$. Since $a_{v}+b_{v}\leq q-1$, we have $a+b\leq n(q-1)$