线性代数网课代修|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.\]Therefore, we may assume that no such vertex exists in \(V\). In particular, every vertex has outdegree or indegree at least \(2\) in at least one of the graphs.We split the vertex set \(V\) into disjoint sets based on colors and directions of incident edges, similarly as in Section 3. Let \(\alpha\) and \(\gamma\) be the number of vertices that have outdegree \(0\), respectively indegree \(0\), in both graphs. For \(i\in[2]\), let \(\beta_{i}\) be the number of remaining vertices that are incident only to edges in \(G_{i}\). The remaining vertices in \(V\) can be divided into \(4\) sets depending whether outdegree or indegree is large and in which graph. For \(i\in[2]\), let \(\delta_{i}^{+}\) be the number of vertices having outdegree at least \(2\) in \(G_{i}\) and \(\delta_{i}^{-}\) the number of vertices having indegree at least \(2\) in \(G_{i}\). Let \(M\) be the set of pairs of vertices \(u,v\) such that \(uv\in E(G_{1})\) and \(vu\in E(G_{2})\). Note that every vertex appears in at most one pair in \(M\) as otherwise it has no other incident edges which contradicts the condition proven in the previous paragraph. Moreover, all \(\delta_{1}^{+}+\delta_{1}^{-}+\delta_{2}^{+}+\delta_{2}^{-}\) vertices must appear in \(M\). Thus, we can set \(m=|M|=\frac{1}{2}(\delta_{1}^{+}+\delta_{1}^{-}+\delta_{2}^{+}+\delta_{2}^{-})\).Note that all edges in \(G_{1}\), except those in \(M\), are going from \(\gamma+\beta_{1}+\delta_{1}^{+}\) vertices and to \(\alpha+\beta_{1}+\delta_{1}^{-}\) vertices. From symmetry, we may assume without loss of generality that\[\beta_{1}+\frac{1}{2}\delta_{1}^{+}+\frac{1}{2}\delta_{1}^{-}\leq\beta_{2}+ \frac{1}{2}\delta_{2}^{+}+\frac{1}{2}\delta_{2}^{-},\]we obtain\[e(G_{1}) \leq(\gamma+\beta_{1}+\delta_{1}^{+})(\alpha+\beta_{1}+\delta_{1 }^{-})+m\] \[\leq\left\lfloor\frac{(\gamma+\beta_{1}+\delta_{1}^{+}+\alpha+ \beta_{1}+\delta_{1}^{-})^{2}}{4}\right\rfloor+m\] \[\leq\left\lfloor\frac{(\gamma+\alpha+\beta_{1}+\beta_{2}+\frac{1 }{2}\delta_{1}^{+}+\frac{1}{2}\delta_{1}^{-}+\frac{1}{2}\delta_{2}^{+}+\frac{ 1}{2}\delta_{2}^{-})^{2}}{4}\right\rfloor+m\] \[=\left\lfloor\frac{(n-m)^{2}}{4}\right\rfloor+m\] \[=\left\lfloor\frac{n^{2}-m(2n-m-4)}{4}\right\rfloor\] \[\leq\left\lfloor\frac{n^{2}}{4}\right\rfloor,\]because \(m\leq\frac{1}{2}n\) and \(n\geq 4\), which concludes the proof. AcknowledgementsWe are grateful to the organizers of the 14th Emlektabla Workshop where the authors worked on the problems presented in this paper图片描述

发表回复

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