如果你也在线性代数linearalgebra这个学科遇到相关的难题，请随时添加vx号联系我们的代写客服。我们会为你提供专业的服务。 linearalgebra™长期致力于留学生网课服务，涵盖各个网络学科课程：金融学Finance，经济学Economics，数学Mathematics，会计Accounting，文学Literature，艺术Arts等等。除了网课全程托管外，linearalgebra™也可接受单独网课任务。无论遇到了什么网课困难，都能帮你完美解决！ 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)\).There exists a color \(i\) which appears at most \(\left\lfloor\frac{a}{c}\right\rfloor\) times in the minimum vertex covers, which gives that\[e(G_{i})\leq\left\lfloor\frac{a}{c}\right\rfloor(n-1)+b\leq\left\lfloor\frac {n(q-1)-b}{c}\right\rfloor(n-1)+b.\]Note that increasing \(b\) by \(1\) either increases the above bound by \(1\) or decreases it by \(n-2\), and the decrease happens after at most \(c-1\) increases. Since \(n>c\), the maximum value of the bound is achieved in the last moment before the first decrease, which occurs for \(b\) equal to the remainder of \(n(q-1)\) when divided by \(c\), as desired.The sharpness of the bound follows from a modification of a construction described in the proof of . We enumerate the vertex set by consecutive integers from \(1\) to \(n\) and assign to every vertex \(j\in[n]\) all colors from \((j-1)(q-1)\) to \(j(q-1)-1\) considered modulo \(c\). This way each vertex has \(q-1\) colors assigned and in total we have \(n(q-1)\) assignments. Now, remove the last \(r\) assignments. Since \(r\) is the remainder of \(n(q-1)\) when divided by \(c\), after the removal each color was assigned the same number of times. For every \(i\in[c]\), add to \(G_{i}\) an edge from each vertex with color \(i\) assigned to any other vertex. This gives \(\left\lfloor\frac{n(q-1)}{c}\right\rfloor(n-1)\) edges in each graph. Note that every vertex \(v\) having \(x\) assignments removed has positive outdegree in exactly \(q-1-x\) graphs, so we may still add edges from \(v\) to arbitrary \(x\) vertices and avoid creating a rainbow \(S_{0,q}\). This addition increases the number of edges in each graph by the total number of removed assignments, which is equal to \(r\). Altogether we obtain the required number of edges in each graph

## 发表回复