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

如果你也在线性代数linearalgebra这个学科遇到相关的难题,请随时添加vx号联系我们的代写客服。我们会为你提供专业的服务。 linearalgebra™长期致力于留学生网课服务,涵盖各个网络学科课程:金融学Finance,经济学Economics,数学Mathematics,会计Accounting,文学Literature,艺术Arts等等。除了网课全程托管外,linearalgebra™也可接受单独网课任务。无论遇到了什么网课困难,都能帮你完美解决!

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图片描述

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注