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

\]Since$\sum_{i=1}^{c}\alpha_{i}\leq(q-1)\alpha,\qquad\sum_{i=1}^{c}\beta_{i}\leq(p+q- 1)\beta\qquad\text{and}\qquad\sum_{i=1}^{c}\gamma_{i}\leq(p-1)\gamma,$from (1) we obtain$e(G_{j}) \leq\frac{1}{xy}(x\alpha_{j}+x\beta_{j}+x\gamma)(y\alpha+y\beta_ {j}+y\gamma_{j})$ $\leq\frac{1}{4xy}\big{(}y\alpha+x\alpha_{j}+(x+y)\beta_{j}+x \gamma+y\gamma_{j}\big{)}^{2}$ $\leq\frac{1}{4c^{2}xy}\big{(}(yc+x(q-1))\alpha+(x+y)(p+q-1) \beta+(xc+y(p-1))\gamma\big{)}^{2}. \tag{2}$In particular, for $x=1$ and $y=1$, since $p\leq q$ and $\alpha+\gamma=n-\beta$, this gives$e(G_{j}) \leq\frac{1}{4c^{2}}\big{(}(c+q-1)\alpha+2(p+q-1)\beta+(c+p-1) \gamma\big{)}^{2}$ $\leq\frac{1}{4c^{2}}\big{(}(c+q-1)(\alpha+\gamma)+2(p+q-1)\beta \big{)}^{2}$ $=\frac{1}{4c^{2}}\big{(}(c+q-1)n+(2p+q-1-c)\beta\big{)}^{2}.$If $c\leq t_{1}$, then the above expression is maximized at $\beta=n$ and we obtain$e(G_{j})\leq\frac{(p+q-1)^{2}}{c^{2}}n^{2},$which gives the first bound in both cases of the theorem. This bound is achieved if $A=\emptyset$, $C=\emptyset$ and $B$ is divided into $\binom{c}{p+q-1}$ equal-sized sets, one for each subset of $p+q-1$ colors assigned to the set, with edges in $G_{i}$, for $i\in[c]$, between any vertices from sets having color $i$ assigned. This is depicted in Consider now $c\geq t_{1}$ and take $x=c-p-q+1$ and $y=p$. This gives$yc+x(q-1)=(x+y)(p+q-1)=(c-q+1)(p+q-1),$so from (2) we obtain$e(G_{j}) \leq\frac{1}{4c^{2}p(c\!-\!p\!-\!q\!+\!1)}\big{(}(c-q+1)(p+q-1)( \alpha+\beta)+((c-p-q+1)c+p(p-1))\gamma\big{)}^{2}$ $=\frac{1}{4c^{2}p(c\!-\!p\!-\!q\!+\!1)}\big{(}(c-q+1)(p+q-1)n-(pq-( c-p-q+1)^{2})\gamma\big{)}^{2}.$If $c\leq t_{3}$, then the above expression is maximized at $\gamma=0$ and gives$e(G_{j})\leq\frac{(c-q+1)^{2}(p+q-1)^{2}}{4c^{2}p(c-p-q+1)}n^{2}.$ This bound is achieved when $C=\emptyset$, the set $B$ is of size $\frac{(q-1)(p+q-1)-c(q-p-1)}{2p(c-p-q+1)}n$ and is divided into $\binom{c}{p+q-1}$ equal-sized sets, one for each subset of $p+q-1$ colors assigned to the set, while set $A$ is of size $\frac{(p+q-1)(c-2p-q+1)}{2p(c-p-q+1)}n$ and is divided into $\binom{c}{q-1}$ equal-sized sets, one for each subset of $q-1$ colors assigned to the set. We put edges in $G_{i}$, for $i\in[c]$, between any vertex from a set in $A\cup B$ having color $i$ assigned to any other vertex in $A$ or a vertex in $B$ having color $i$ assigned. This construction is possible only if the mentioned sizes of sets $A$ and $B$ are non-negative, which occurs when $c\geq t_{1}$ and $c\leq t_{2}$, and so it proves the second bound in both cases of the theorem. Note that if $q\leq p+1$, then the size of $B$ is always positive, which explains why $t_{2}$ is defined in this way. This construction is illustrated in In order to prove the third bound in the first case of the theorem, consider $c$ satisfying $t_{2}\leq c\leq t_{4}$ and take $x=c$ and $y=q-1$. From (2) we get$e(G_{j})\leq\frac{1}{4c^{3}(q-1)}\big{(}2c(q-1)\alpha+(c+q-1)(p+q-1)\beta+(c^{ 2}+(p-1)(q-1))\gamma\big{)}^{2}.$The assumption $c\leq t_{4}$ implies that $c^{2}+(p-1)(q-1)\leq 2c(q-1)$, so$e(G_{j}) \leq\frac{1}{4c^{3}(q-1)}\big{(}2c(q-1)(\alpha+\gamma)+(c+q-1)(p+ q-1)\beta\big{)}^{2}$ $=\frac{1}{4c^{3}(q-1)}\big{(}2c(q-1)n-(c(q-p-1)-(q-1)(p+q-1)) \beta\big{)}^{2}.$Since $c\geq t_{2}$, the expression above is maximized at $\beta=0$ and gives$e(G_{j})\leq\frac{q-1}{c}n^{2},$ which proves the third bound in the first case of the theorem. This is the same bound as when forbidding a rainbow $S_{0,q}$, so it is achieved when $B=C=\emptyset$, while set $A$ is divided into $\binom{c}{q-1}$ equal-sized sets, one for each subset of $q-1$ colors assigned to the set, and we put edges in $G_{i}$, for $i\in[c]$, between any vertex from a set having color $i$ assigned to any other vertex. This is depicted for $q=3$ and $c=3$ in Finally, consider the last remaining bound, where we have $c\geq t_{3}$ and $c\geq t_{4}$. From (2) for $x=c-p+1$ and $y=c-q+1$ we obtain$e(G_{j}) \leq\frac{1}{4c^{2}(c\!-\!p\!+\!1)(c\!-\!q\!+\!1)}\big{(}(c^{2}-(p \!-\!1)(q\!-\!1))(\alpha+\gamma)+(2c-p-q+2)(p+q-1)\beta\big{)}^{2}$ $=\frac{1}{4c^{2}(c\!-\!p\!+\!1)(c\!-\!q\!+\!1)}\big{(}(c^{2}-(p\! -\!1)(q\!-\!1))n-((c-p-q+1)^{2}-pq)\beta\big{)}^{2}.$Since $c\geq t_{3}$, the above expression is maximized at $\beta=0$ and gives\[e(G_{j})\leq\frac{(c^{2}-(p-1)(q-1))^{2}}{4c^{2}(c-p+1)(c-q+1)}