| Sbornik: Mathematics |
|
|
|
|
|
Lower and upper bounds for the minimum number of edges in some subgraphs of the Johnson graph N. A. Dubinina, E. A. Neustroevaa, A. M. Raigorodskiiabcd, Ya. K. Shubina a Moscow Institute of Physics and Technology, Dolgoprudny, Moscow Region, Russia b Lomonosov Moscow State University, Moscow, Russia c Adyghe State University, Maikop, Russia d Buryat State University named after D. Banzarov, Ulan-Ude, Russia
Bibliographic databases:
     § 1. IntroductionIn this work we consider a special distance graph $G(n,r,s)$ whose vertices are points of the $n$-dimensional Boolean hypercube with precisely $r$ entries equal to one and two vertices joined by an edge if and only if the scalar product of the corresponding vectors equals $s$. This definition can also be formulated in combinatorial terms, namely, the vertices of this graph are all possible $r$-element subsets of the set $\mathcal{R}_{n}=\{1,2, \dots, n\}$, and two subsets are joined by an edge if and only if they share exactly $s$ common elements. It is the second definition that is used in this work. The graph $G(n,r,s)$ is quite important in graph theory, combinatorial geometry and the study of codes with forbidden distances. Using just these very graphs Frankl and Wilson [1] showed that the chromatic number of a space grows exponentially with dimension. In 1991 Kahn and Kalai used the results of Frankl and Wilson to disprove Borsuk’s classical conjecture that each bounded set of cardinality greater than 1 in $\mathbb{R}^{n}$ can be partitioned into $n+1$ parts of smaller diameter (see [2] and [3]). In [4]–[7] some properties of the graph $G(n,r,s)$ and other graphs of similar structure were studied. Recall that a subset of vertices of a graph $G$ is said to be independent if no two vertices of this subset are adjacent. The greatest cardinality of an independent subset of the graph $G$ is called its independence number and denoted by $\alpha(G)$. Let $W$ be a subset of vertices of the graph $G=(V, E)$. We denote by $\rho(W)$ the number of edges in the subgraph induced by $W$, that is, Also set Note that the problem of estimating the number of edges in induced subgraphs is intimately related to the theory of expander graphs and spectral graph theory (see [8]–[10]). In this work we consider upper and lower asymptotic bounds for the quantity $\rho(l)$ in the case of the graphs $G(n, 3, 1)$. Recall that the relation $f(n) \sim g(n)$ means that $\lim_{n \to \infty} f(n)/g(n)=1$. The following result was obtained in [11]–[13] Theorem 1. For the series of graphs $G(n, 3, 1)$ the following hold: (1) if a function $l=l(n)$ is such that $l=\omega(n)$ and $ l=o(n^2)$, then $\rho(l) \sim l^2/(2n)$; (2) if a function $l=l(n)$ is such that $l=\omega(n^2)$, then $\rho(l) \sim 9l^2/(2n)$. We concentrate here on the case $l=[cn^2]$, which is not covered by this theorem. We formulate some known results and present improved upper and lower estimates for various values of $c$. § 2. Known resultsFirst, let us present all known lower bounds for the quantity $\rho (l)$ which can be used in the case $l \sim cn^2$. The independence number of the graph $G(n, 3, 1)$ was found by Nagy in [14]. We will use a convenient bound for the independence number, which immediately follows from the results of that work. A classical method for estimating the number of edges in a graph with bounded independence number is provided by Turán’s theorem presented below. Proposition 1 and Theorem 2 yield the following simple estimate. Theorem 3. For the sequence of graphs $G(n, 3, 1)$ and $l=[cn^2]$ there exists a function $g(n)$ such that $\rho(l) \geqslant g(n)$ and Although in the general case the estimate obtained with the use of Turán’s theorem is optimal, it can be improved for the class of graphs $G(n, 3, 1)$. A better estimate was obtained in [11]. Theorem 4. For the sequence of graphs $G(n, 3, 1)$ and $l=[cn^2]$ there exists a function $g(n)$ such that $\rho(l) \geqslant g(n)$ and As the value of $c$ increases, the result of this theorem becomes almost best possible (see part (2) of Theorem 1), but for small values of $c$ the bound provided by Theorem 4 is negative. Results outperforming the estimates in Theorems 3 and 4 for small values of $c$ were obtained in [15]. Theorem 5. For the sequence of graphs $G(n, 3, 1)$ and $c \in(1/8,1/4]$ there exists a function $g(n)$ such that $\rho([cn^2]) \geqslant g(n)$ and Theorem 6. For the sequence of graphs $G(n, 3, 1)$ and $c \in(1/4, 1]$ there exists a function $g(n)$ such that $\rho([cn^2]) \geqslant g(n)$ and All estimates for the quantity $\rho([cn^2])$ presented above exhibit an asymptotic behaviour of the form $f(c)n^3$. Therefore, it is reasonable to compare the functions $f(c)$ on their domains of definition. We denote the functions corresponding to the estimates from Theorems 3–6 by $f_3$, $f_4$, $f_5$ and $f_6$, respectively. The behaviour of $f_3$, $f_4$, $f_5$ and $f_6$ is shown in Figure 1. Thus, for $c < 1/8$ the best result is provided by Turán’s estimate, for $c \in[1/8,1/4]$ by the estimate from Theorem 5, for $c \in(1/4, c_0]$, where $c_0 \approx 0.8537$, by the estimate form Theorem 6, and for all other values of $c$ by the estimate from Theorem 4. In this work we present an estimate which outperforms the one in Theorem 4 for all values of $c$ and an estimate which outperforms the one in Theorem 6 for $c > 1/4$. Let us turn to upper estimates. The only known upper estimate applicable to the case when $l \sim cn^2$ follows from the proof of part (2) of Theorem 1. Thus, we have the following result. Proposition 2. For the sequence of graphs $G(n, 3, 1)$ and any positive constant $c$ there exists a function $g(n)$ such that $\rho([cn^2]) \leqslant g(n)$ and § 3. Lower bounds: formulations of the results of this workTheorem 7. For the sequence of graphs $G(n,3,1)$ and any positive constant $c$ there exists a function $g(n)$ such that $\rho([cn^2]) \geqslant g(n)$ and With the estimate given in Theorem 7 we associate the function $f_7(c)={9c^2/2-3c/2}$. It is easily seen that this estimate is always significantly stronger than the one from Theorem 4 and that it outperforms the other two estimates on a wider range of values of $c$ than the estimate from Theorem 4 does. To obtain this result we use the following lemma, which is proved in § 7. Theorem 7 itself is proved in § 6. Lemma 1. In a simple graph on $v$ vertices with $e$ edges the number of pairs of edges that share a common end vertex does not exceed Nevertheless, for small values of $c$ the estimate in Theorem 7 is inferior to the ones from Theorems 3, 5 and 6. For small values of $c$ a new result is also established. Theorem 8. For the sequence of graphs $G(n, 3, 1)$ and $c \in(1/4,1]$ there exists a function $g(n)$ such that $\rho([cn^2]) \geqslant g(n)$ and With the estimate from Theorem 8 we associate the function $f_{8}(c)\!=\!{c^2\!-\!13/1320}$. This estimate outperforms the one from Theorem 6 for all $c > 1/4$. Even though the constant increases only slightly, in deriving this estimate we improve the method used to obtain the estimate in Theorem 6. Theorem 8 is proved in § 8. As before, for $c < 1/8$ the best result is provided by Turán’s estimate, for $c \in[1/8,1/4]$ by the estimate from Theorem 5, for $c \in(1/4,c_1]$, where $c_1 \approx 0.4219$, by the estimate from Theorem 8, and for all other values of $c$, by the estimate from Theorem 7. The behaviour of the new bounds $f_3$, $f_4$, $f_7$ and $f_8$ is shown in Figure 2. § 4. Upper bounds: formulations of the results of this workTheorem 9. Consider the sequence of graphs $G(n, 3, 1)$. Given a positive constant $c$ presented in the form $c=p/2+q$, where $p$ is a nonnegative integer and $q$ belongs to the interval $[0,1/2)$, one can find a function $g(n)$ such that $\rho([cn^2]) \leqslant g(n)$ and Note that the following relation holds:
$$
\begin{equation*}
\frac{9c^2}{2}-c+2q\biggl(\frac 12-qr\biggr) =\frac{9c^2}{2}-\frac{p}{2}- q +q -2q^2 = \frac{9c^2}{2}- \frac{p}{2} -2q^2 < \frac{9c^2}{2}.
\end{equation*}
\notag
$$
Thus, the estimate given in Theorem 9 is stronger than the one in Proposition 2 for any values of the constant $c$. We prove Theorem 9 in § 9. Also, in this work we prove the following theorem. Theorem 10. Consider the sequence of graphs $G(n, 3, 1)$. Given a constant $1/8 \geqslant c > 0$ presented in the form $c=p(1-p)/2$, where $p\in(0,1/2)$, one can find a function $g(n)$ such that $\rho([cn^2]) \leqslant g(n)$ and For all values of $c\in(0,1/8]$ the coefficient of $n^3$ in the estimate from Theorem 10 is smaller than the one in Theorem 9. We prove Theorem 10 in § 10. However, in the case when $1/4> c >1/8$ Theorem 10 is not applicable, while the estimate provided by Theorem 9 is too weak. For this reason, in this case we consider a special construction, which, in a certain sense, resembles the construction in Theorem 10. Using it we obtain the following result. Theorem 11. Consider the sequence of graphs $G(n,3,1)$. Given a constant $1/4 > c > 0$ presented in the form $c=q(1-q)$, where $q\in(0,1/2)$, one can find a function $g(n)$ such that $\rho([cn^2]) \leqslant g(n)$ and To compare upper estimates we consider only the functions $f(c)$ that determine the coefficients of $n^3$. We denote the functions corresponding to the estimates in Proposition 2 and Theorems 9–11 by $f_2$, $f_{9}$, $f_{10}$ and $f_{11}$, respectively. The behaviour of $f_2$, $f_{9}$, $f_{10}$ and $f_{11}$ is shown in Figure 3. § 5. Estimate comparisonLet us compare the new lower estimates with the new upper estimates. We compare only the coefficients of $n^3$, which are functions of $c$. First consider the case $c <1/8$. The best lower estimate corresponds to the function $f_3(c)= c^2/2$, whereas the best upper one corresponds to
$$
\begin{equation*}
f_{10}=\frac{c^2}{2(1-p)}, \quad\text{where } c=\frac{p(1-p)}{2}, \quad p\in\biggl(0,\frac 12\biggr).
\end{equation*}
\notag
$$
It is easily seen that these estimates differ by a factor of $1-p$, so, as $c \to 0$, we have $p \to 0$ and $(1-p) \to 1$. Taking into account that $p < 1/2$, we see that the estimates differ from each other by less than two times for any $c < 1/8$. Now consider the opposite case of ‘large’ values of $c$, starting with $c_1 \approx 0.4219$. In this case the best lower estimate corresponds to the function $f_7(c)=(9c^2-3c)/2$, whereas the best upper estimate corresponds to
$$
\begin{equation*}
f_9(c)=\frac{9c^2}{2}-c+2q\biggl(\frac12-q\biggr), \quad\text{where } c=\frac{p}{2}+q, \quad 0 \leqslant q < \frac 12.
\end{equation*}
\notag
$$
The difference between these functions is $c/2+2q(1/2-q)$ and, as $c \to \infty$, we have $f_7(c) \sim f_9(c)$. For $c \in [1/8, c_1)$ the best lower estimates are provided by Theorems 5 and 8, and the best upper estimates by Theorems 11 and 9. The gap is much larger than in the cases considered above. The behaviour of the best lower and best upper estimates is shown in Figure 4. § 6. Proof of Theorem 7Let $l(n)=l=[cn^2]$. For each $n$ consider a subset $W_n$ of vertices of the graph $G(n,3,1)$ such that $|W_n|=l(n)$. For each element $i$ let $K_i$ denote the set of vertices of our subgraph that contain this element: We introduce the notation $k_i=|K_i|$. Note that each vertex is contained in precisely three distinct sets $K_i$, hence we obtain These sets have some common vertices. But if two vertices of our graph are joined by an edge, then they are simultaneously contained in a unique set $K_i$, since they share precisely $s$ common elements. Then we have Let us estimate the number of edges between vertices of $K_1$ from below. To do this we construct a new graph $F$ on $n-1$ vertices, which correspond to the elements $2, 3, \dots, n$ of the original graph. Elements $i$ and $j$ are joined by an edge in the new graph if and only if the vertex $\{1,i,j\}$ is contained in the original graph. Thus, the number of edges in $F$ is $k_1$. Note that if two vertices from $K_1$ are joined by an edge in the graph $W_n$, then the corresponding edges in the graph $F$ are not adjacent. A pair of edges in the graph $F$ is called a check mark if they share a common end vertex. Denote the number of check marks in the graph $F$ by $q$. Then the following relation holds: Thus, we need to estimate the minimum number of check marks in the graph $F$ with a fixed number of edges. We apply Lemma 1 to $F$ and obtain that the number of check marks in the graph $F$ does not exceed Then we have the estimate
$$
\begin{equation*}
\rho(K_1) \geqslant C_{k_1}^2-\frac{k_1(n-1)}{2} -\frac{k_1^2}{n-1}= \frac{n-3}{2(n-1)} k_1^2-\frac{n}{2} k_1.
\end{equation*}
\notag
$$
Now we derive similar estimates for the other sets $K_i$ and sum them all up:
$$
\begin{equation*}
\rho (W_n)=\sum_{i=1}^{n}\rho (K_i) \geqslant \sum_{i=1}^{n} \frac{n-3}{2(n-1)} k_i^2-\sum_{i=1}^{n} \frac{n}{2} k_i.
\end{equation*}
\notag
$$
We know that and the first sum can be estimated using the generalized mean inequality: Finally, we obtain the resulting lower estimate
$$
\begin{equation*}
\rho (W_n) \geqslant \frac{n-3}{2(n-1)} \,\frac{9l^2}{n}-\frac{3ln}{2} \sim \frac{9c^2n^3}{2}- \frac{3cn^3}{2}.
\end{equation*}
\notag
$$
The proof of Theorem 7 is complete. § 7. Proof of Lemma 17.1.We use induction on the number of vertices. The base case $v=1$ is obvious. To prove the induction step consider a graph $G$ such that $V(G)=v$ and $E(G)=e$. Among all such graphs we take the one in which the number of check marks is greatest. If this graphs contains an isolated vertex, then we remove it and apply the induction hypothesis. Then the number of edges is not greater than Let us compare this quantity with the required estimate:
$$
\begin{equation*}
\begin{gathered} \, \frac{e(v-1)}{2}+\frac{e^2}{v-1} \vee \frac{ev}{2}+\frac{e^2}{v}, \\ \frac{e^2}{v(v-1)} \vee \frac{e}{2}, \\ e \vee \frac{v(v-1)}{2}. \end{gathered}
\end{equation*}
\notag
$$
The value of the expression on the right-hand side is not less than that of the one on the left-hand side, since the graph contains at most $C_v^2$ edges, hence in this case the induction step is established. Now suppose that the graph $G$ has no isolated vertices. We choose a vertex $a$ of the smallest degree and let it be joined with vertices of a set $B=\{b_1, b_2, \dots, b_s\}$. Then the degree of each vertex in the graph is at least $s$. Let us show that all vertices in the set $B$ have the maximum degree, that is, Assume that this is not the case. Then there are nonadjacent vertices $f$ and $b_i$. Note that the vertex $f$ can also belong to the set $B$. Now remove the edge between the vertices $a$ and $b_i$ and add a new edge between the vertices $f$ and $b_i$. It is easily seen that the deleted edge was involved in exactly $d(b_i)-1+s-1$ check marks, while adding the new edge gives rise to $d(f)+d(b_i)-1$ new check marks. Thus, the number of check marks has increased by $d(f)- (s-1) \geqslant s-(s-1) > 0$, which contradicts the assumption of maximality. Now we remove the vertex $b_1$ and all edges incident to it. Let us calculate the number of check marks containing these edges. The number of check marks with head at the vertex $b_1$ is equal to $C_{v-1}^2$. Note also that any remaining edge is included in precisely two check marks the second edge of which is removed. Therefore, the total number of check marks containing edges incident to $b_1$ is $C_{v-1}^2+2(e-(v-1))$. Now we apply the induction hypothesis to the graph without the vertex $b_1$. As a result, the total number of check marks is not greater than
$$
\begin{equation*}
\begin{aligned} \, &C_{v-1}^2+2(e-(v-1))+\frac{(e-(v-1))(v-1)}{2}+\frac{(e-(v-1))^2}{v-1} \\ &\qquad =2(e-(v-1))+\frac{(e-1)(v-1)}{2} +\frac{(e-(v-1))^2}{v-1} \\ &\qquad =\frac{(e-1)(v-1)}{2}+\frac{e^2-(v-1)^2}{v-1} \\ &\qquad\leqslant \frac{e(v-1)}{2}+ \frac{e^2}{v-1}= \frac{ev}{2}+\frac{e^2}{v-1}-\frac{e}{2}. \end{aligned}
\end{equation*}
\notag
$$
Note that it has already been demonstrated that the inequality is always valid. Thus, this bound does not exceed the one in the induction hypothesis, which means that in this case the induction step has also been established.The proof of the lemma is complete. 7.2.Lemma 1 admits another proof, which is based on the fact that graphs with prescribed numbers of vertices and edges that contain the maximum number of check marks have a special shape. Definition. A quasi-complete graph on $v$ vertices with $e$ edges is a graph in which the vertices $1, 2, \dots, a$ induce a complete subgraph, the vertex $a+1$ is joined with the vertices $1, \dots, b$, and all other vertices are isolated, where $a$ and $b$ are uniquely defined by the conditions Suppose that a graph $G$ on $v$ vertices with $e$ edges is such that it has no fewer check marks than any other graph with the same number of vertices and edges. It was shown in [16] that such a graph $G$ is either a quasi-complete graph, or the complement of a quasi-complete graph. Thus, it is sufficient to prove the estimate for these two types of graphs. Let $G$ be a quasi-complete graph, and let $e=a(a-1)/2+b$, $0 \leqslant b < a$. Suppose that the vertices $1, \dots, a$ induce a complete subgraph and the vertex $a+1$ is joined with the vertices $1, \dots, b$. The number of check marks both of whose edges have endpoints in the set $\{1, \dots, a\}$ is equal to $a(a- 1)(a-2)/2$. The number of check marks with exactly one edge incident to the vertex $a+1$ is $b(a- 1)$. Finally, the number of check marks with both edges incident to the vertex $a+1$ is $b(b- 1)/2$. Thus, the total number of check marks in the graph $G$ is
$$
\begin{equation*}
\begin{aligned} \, &\frac{a(a-1)(a-2)}{2}+b(a-1)+\frac{b(b-1)}{2} \\ &\qquad=\frac{a(a-1)^2}{2}-\frac{a(a-1)}{2}+b(a- 1)+\frac{b(b-1)}{2}. \end{aligned}
\end{equation*}
\notag
$$
Since $b < a$, the value of the last expression does not exceed
$$
\begin{equation*}
\begin{aligned} \, \frac{a(a-1)^2}{2}+b(a-1) &=(a-1)\biggl(\frac{a(a-1)}{2}+b\biggr) \\ &\leqslant \biggl(\frac{a(a-1)}{2}+b\biggr) \sqrt{a(a-1)+2b}=e\sqrt{2e} \leqslant \frac{ev}{2}+\frac{e^2}{v}, \end{aligned}
\end{equation*}
\notag
$$
as required. The last relation is due to the inequality between arithmetic and geometric means. Now let $G$ be the complement of a quasi-complete graph. Since $\overline{G}$ is quasi-complete, it has the shape described above, and the values of $a$ and $b$ are uniquely defined by the conditions $v(v-1)/2-e=a(a-1)/2+b$ and $0 \leqslant b < a$. Thus, the graph $G$ looks as follows: each vertex with index greater than $a+1$ is joined with all other vertices, the vertex $a+1$ is joined with all other vertices but $1, 2, \dots, b$, and there are no other edges. Each vertex in the set $\{1, \dots, b\}$ has degree $v-a-1$, each vertex in the set $\{b+1, \dots, a\}$ has degree $v-a$, the vertex with index $a+1$ has degree $v-b-1$, and all other vertices have degree $v-1$. Set $c=a-b$ and $d=v-a-1$. Then the number of vertices is $b+c+d+ 1$. The total degree of vertices is Note that each vertex with index in the set $\{1, \dots, b\}$ is the head of ${d(d-1)/2}$ check marks, each vertex with index in the set $\{b+1, \dots, a\}$ is the head of ${(d+1)d/2}$ check marks, the vertex with index $a+1$ is the head of $(c+d)(c+d-1)/2$ check marks, and each of the remaining vertices is the head of $(b+c+d)(b+c+d-1)/2$ check marks. Thus, the total number of check marks is
$$
\begin{equation*}
\begin{aligned} \, g &=\frac{1}{2}\bigl(bd(d-1)+cd(d+1)+(c+d)(c+d-1) \\ &\qquad+d(b+c+d)(b+c+d-1)\bigr). \end{aligned}
\end{equation*}
\notag
$$
It is necessary to show that $g \leqslant ev/2+e^2/v$. Multiplying this inequality by $4v$ gives $4gv \leqslant 2e(v^2+2e)$. This inequality can be rewritten in terms of the parameters $b$, $c$ and $d$ as
$$
\begin{equation*}
\begin{aligned} \, &2(b+c+d+1)\bigl(bd(d-1)+cd(d+1)+(c+d)(c+d-1) \\ &\qquad\qquad+d(b+c+d)(b+c+d-1)\bigr) \\ &\qquad \leqslant \bigl(bd+c(d+1)+(c+d)+d(b+c+d)\bigr) \\ &\qquad\qquad\times\bigl((b+c+d+1)^2+bd+c(d+1)+(c+d)+d(b+c+ d)\bigr). \end{aligned}
\end{equation*}
\notag
$$
Removing parentheses and collecting like terms gives
$$
\begin{equation*}
\begin{aligned} \, 0 &\leqslant 2b^2c+b^2d^2+7b^2d+2bc^2+2bcd^2+18bcd+6bc+10bd^2+10bd \\ &\qquad + c^2d^2+9c^2d+8c^2+8cd^2+12cd+4c+3d^3+6d^2+3d, \end{aligned}
\end{equation*}
\notag
$$
which is true since $b, c$ and $ d$ are positive. Thus, the required inequality has been established in both cases. The proof of Lemma 1 is complete. § 8. Proof of Theorem 88.1.Set $l=[cn^2]$ and consider an arbitrary set $L$ of $l$ vertices in the graph $G(n, 3, 1)$. In this subset we distinguish a maximal independent set $B_1$ and denote its cardinality by $\beta_1$. Among the remaining vertices of the graph consider those connected with just one vertex in $B_1$. These vertices form a set $K_1$ of cardinality $k_1$. For each vertex $a_i \in B_1$, $1\leqslant i \leqslant \beta_1$, consider the subset $A_i \subset K_1$ of all vertices in $K_1$ that are connected with $a_i$. The set $A_i$ is a clique since if it contained a pair of nonadjacent vertices $b$, $c$, then $\{b, c\} \,{\cup}\, B_1 \setminus \{a_i\}$ would be an independent set of cardinality greater than that of $B_1$, which is impossible. For distinct $i$ and $j$ the sets $A_i$ and $A_j$ are disjoint, for otherwise the set $K_1$ would contain a vertex adjacent to two distinct vertices from $B_1$. Thus, $K_1$ contains a clique on at least $k_1/\beta_1$ vertices. Note that each vertex in $L\setminus (B_1 \cup K_1)$ is connected with at least two vertices from $B_1$. Now we can proceed in two ways. First, we can remove the set $B_1$ and all edges incident to it from the original graph. Thus we remove $v_1=\beta_1$ vertices and $e_1=k_1+2(l- \beta_1-k_1)=2l-2\beta_1-k_1$ edges. Second, we can remove both $B_1$ and a clique of cardinality precisely $[k_1/\beta_1]$ from $K_1$. In this way the number of vertices decreases by $v_1=\beta_1 +[{k_1}/{\beta_1}]$ and the number of edges by
$$
\begin{equation*}
\begin{aligned} \, e_1 &=k_1+2(l-\beta_1-k_1)+ \frac{1}{2}\biggl[\frac{k_1}{\beta_1}\biggr] \biggl(\biggl[\frac{k_1}{\beta_1}\biggr]-1\biggr) \\ &=2l-2\beta_1-k_1+ \frac{1}{2}\biggl[\frac{k_1}{\beta_1}\biggr] \biggl(\biggl[\frac{k_1}{\beta_1}\biggr]-1\biggr). \end{aligned}
\end{equation*}
\notag
$$
We repeat this procedure $T\,{-}\,1$ times more, where $T$ is specified below. Then at the $j$th step we distinguish a maximal independent set $B_j$ of cardinality $\beta_j$ and a subset $K_j$ of vertices in which each vertex is adjacent to a unique vertex in $B_j$, $|K_j|=k_j$. There is a clique on at least $k_j/\beta_j$ vertices of the set $K_j$. Before the $j$th step the graph has $l-\sum_{i=1}^{j-1}v_i$ vertices. At the $j$th step we proceed in one of the following two ways. The first way consists in removing $B_j$. Thereby we remove $v_j=\beta_j$ vertices and $e_j=2\bigl(l-\sum_{i=1}^{j}v_j\bigr)-k_j$ edges. The second way consists in removing both the set $B_j$ and a clique of size $[{k_j}/{\beta_j}]$. In this case the number of vertices removed is $v_j=\beta_j+[k_j/\beta_j]$ and the number of edges removed is
$$
\begin{equation*}
\begin{aligned} \, e_j &=2\biggl(l-\sum_{i=1}^{j-1}v_i-\beta_j-k_j\biggr)+k_j+ \frac{1}{2}\biggl[\frac{k_j}{\beta_j}\biggr]\biggl(\biggl[\frac{k_j}{\beta_j}\biggr]-1\biggr) \\ &=2\biggl(l-\sum_{i=1}^{j}v_i\biggr)-k_j+\frac{k_j^2}{2\beta_j^2}+ O\biggl(\frac{k_j}{\beta_j}\biggr), \end{aligned}
\end{equation*}
\notag
$$
where the constant $C$, which is used as $C({k_j}/{\beta_j})$ in the asymptotic upper estimate for the term $O({k_j}/{\beta_j})$, can be chosen independent of $j$. To estimate the number $T$ of steps, let us use the following lemma, which reformulates Lemma 1 in [15]. Lemma 2. Given a subgraph $H$ of the graph $G(n, 3, 1)$, a maximal independent set $B$ in $H$, $|B|=\beta$, and a set $K$, $|K|=k$, of vertices in $H$ every vertex in which is adjacent to a unique vertex in $B$, one can guarantee the inequality $\beta \leqslant n$ and at least one of the inequalities $\beta+ 2k/\beta \leqslant n$ and $k \leqslant 6\beta$. Thus, at each step we remove at most $n+6$ vertices from the graph and can assume that $T= [l/(n+6)]$. Note also that by the above lemma we have ${k_j/\beta_j=O(n)}$. Let us find the total number of edges removed in $T$ steps and denote this quantity by $S$:
$$
\begin{equation*}
\begin{aligned} \, S &=\sum_{i=1}^T e_i=\sum_{i=1}^T \biggl(2\biggl(l-\sum_{j=1}^{i}v_j\biggr)+e_i-2\biggl(l- \sum_{j=1}^{i}v_j\biggr)\biggr) \\ &=2lT-2\sum_{i=1}^{T} \sum_{j=1}^{i}v_j+\sum_{i=1}^{T} \biggl(e_i-2\biggl(l-\sum_{j= 1}^{i}v_j\biggr)\biggr) \\ &=2lT-\sum_{i=1}^T\biggl(2(T-i+1)v_i-e_i+2\biggl(l-\sum_{j=1}^{i}v_j\biggr)\biggr). \end{aligned}
\end{equation*}
\notag
$$
At each step we can proceed in one of the two ways described above: either we remove a maximal independent set, or remove both a maximal independent set and a clique. Suppose that each time we make our choice so as to minimize the value of the term $2(T-i+1)v_i-e_i+2\bigl(l- \sum_{j=1}^{i}v_j\bigr)$. Then the total number of edges removed is minimum possible. The following estimate holds:
$$
\begin{equation*}
\begin{aligned} \, S &\geqslant 2lT-\sum_{i=1}^{T}\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+ 1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2}\biggr\} \\ &\qquad+O(Tn). \end{aligned}
\end{equation*}
\notag
$$
The following series of lemmas will be used to estimate the value of $S$ more accurately. Lemmas 3 and 4 reformulate Lemmas 2 and 3 in [15], while Lemmas 5 and 6 improve them. In combination, Lemmas 2–5 enable us to estimate the expression
$$
\begin{equation*}
\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2}\biggr\}
\end{equation*}
\notag
$$
for all possible values of $T$. Moreover, the estimates of Lemmas 4–6 improve the result of Lemma 3. As the arguments presented above apply to an arbitrary $l$-vertex subgraph of the graph $G(n, 3, 1)$, these lemmas can be used to derive an estimate for the quantity $\rho(l)$. Recall that we consider the number $T=[l/(n+6)]$ of steps for $l=[cn^2]$, $c \in(1/4,1]$, and therefore steps with numbers $T$, $T-n/22+1$, $T-n/20+1$, $T-n/4+1$ are actually made for sufficiently large values of $n$. Now we can establish the estimate claimed above:
$$
\begin{equation*}
\begin{aligned} \, \rho(l) &\geqslant 2lT-\sum_{i=1}^{T-n/4+1}2(T-i)n-\sum_{i=T-n/4+2}^{T- n/20+1} \frac{(2(T-i+1)+n/2)^2}{2} \\ &\qquad-\sum_{i=T-n/20+2}^{T-n/22+1}6(T-i+1)n-48(T-i+1)^2 \\ &\qquad - \sum_{i=T-n/22+2}^{T} \frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10}+O(nT). \end{aligned}
\end{equation*}
\notag
$$
Let us compute each of the four sums separately. For the steps with numbers from $1$ to $T- n/4+1$ we have
$$
\begin{equation*}
\begin{aligned} \, \sum_{i=1}^{T-n/4+1}2(T-i)n &=2n\sum_{j=n/4-1}^{T-1}j= 2n\biggl(\frac{T^2}{2}- \frac{n^2}{32}\biggr)+O(nT) \\ &=nT^2-\frac{n^3}{16}+O(nT). \end{aligned}
\end{equation*}
\notag
$$
For the steps with numbers from $T-n/4+2$ to $T-n/20+1$ we have
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=T-n/4+2}^{T-n/20+1} \frac{(2(T-i+1)+n/2)^2}{2} \\ &\qquad= \sum_{j=n/20}^{n/4-1} \frac{(2j+n/2)^2}{2}=\sum_{j= n/20}^{n/4-1}\biggl(2j^2+nj+\frac{n^2}{8}\biggr) \\ &\qquad =\frac{2}{3}\biggl(\frac{n^3}{64}-\frac{n^3}{8000}\biggr)+ \frac{n}{2}\biggl(\frac{n^2}{16}-\frac{n^2}{400}\biggr)+\frac{n^2}{8}\biggl(\frac{n}{4}- \frac{n}{20}\biggr)+O(n^2) \\ &\qquad =n^3 \biggl(\frac{31}{3000}+\frac{3}{100}+\frac{1}{40}\biggr)+O(n^2)). \end{aligned}
\end{equation*}
\notag
$$
Now we estimate the sum for the steps with numbers from $T-n/20+2$ to ${T-n/22+1}$:
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=T-n/20+2}^{T-n/22+1}6(T-i+1)n-48(T-i+ 1)^2=\sum_{j=n/22}^{n/20-1}(6nj-48j^2) \\ &\qquad =3n\biggl(\frac{n^2}{400}-\frac{n^2}{484}\biggr)-\frac{48}{3}\biggl(\frac{n^3}{20^3}- \frac{n^3}{22^3}\biggr)+O(n^2). \end{aligned}
\end{equation*}
\notag
$$
It remains to estimate the sum for the steps with numbers from $T-n/22+2$ to $T$:
$$
\begin{equation*}
\begin{aligned} \, &\sum_{i=T-n/22+2}^{T}\frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10} =\sum_{j=1}^{n/22-1}\frac{n^2+16nj+4j^2}{10} \\ &\qquad =\frac{n^3}{220}+\frac{4n^3}{5\cdot 22^2}+\frac{4n^3}{30\cdot 22^3}+O(n^2). \end{aligned}
\end{equation*}
\notag
$$
Now we return to the estimate for $\rho(l)$, given that $T=[l/(n+6)]$:
$$
\begin{equation*}
\begin{aligned} \, \rho(l) &\geqslant 2lT-nT^2-n^3\biggl(-\frac{1}{16}\biggr)-n^3\biggl(\frac{31}{3000} +\frac{3}{100}+\frac{1}{40}\biggr) \\ &\qquad - n^3\biggl(\frac{3}{400}-\frac{3}{484}-\frac{48}{3\cdot8000}+ \frac{48}{3\cdot22^3}\biggr) \\ &\qquad- n^3\biggl(\frac{1}{220}+\frac{4}{5\cdot 22^2}+\frac{4}{30\cdot 22^3}\biggr)+O(n^2) \\ &=\frac{l^2}{n}-\frac{13n^3}{1320}+O(n^2) \sim n^3\biggl(c^2-\frac{13}{1320}\biggr). \end{aligned}
\end{equation*}
\notag
$$
Thus, we have established the estimate claimed above with the use of lemmas proved below. 8.2. Proof of Lemma 5First, let us compare the following two expressions:
$$
\begin{equation*}
\begin{aligned} \, &2(T-i+1)\beta_i+k_i \leqslant 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2} \\ &\quad\Longleftrightarrow \quad \frac{k_i^2}{2\beta_i^2} \leqslant 2(T-i+1)\frac{k_i}{\beta_i} \quad\Longleftrightarrow \quad \frac{k_i}{\beta_i} \leqslant 4(T-i+1). \end{aligned}
\end{equation*}
\notag
$$
Now let us estimate the value of the expression $2(T-i+1)\beta_i+k_i$ for $k_i/\beta_i \leqslant 4(T-i+1)$, and then the value of the expression $2(T-i+1)(\beta_i+k_i/\beta_i)+k_i-k_i^2/(2\beta_i^2)$ for $k_i/\beta_i > 4(T-i+1)$. We must demonstrate that both bounds do not exceed for any admissible values of $k_i, \beta_i$.By Lemma 2 we have either $\beta_i+2k_i/\beta_i \leqslant n$ or $k_i \leqslant 6\beta_i$. In the case when $k_i/\beta_i \leqslant 6$ we have which, in turn, does not exceed since
$$
\begin{equation*}
48(T-i+1)^2 \leqslant 4(T-i+1) \quad\Longleftrightarrow \quad T-i+1 \leqslant \frac{n}{12}.
\end{equation*}
\notag
$$
In a similar way we have
$$
\begin{equation*}
\begin{aligned} \, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2} &\leqslant 2(T-i+ 1)n+O(n) \\ &\leqslant 6(T-i+1)n-48(T-i+1)^2+O(n). \end{aligned}
\end{equation*}
\notag
$$
The case when $\beta_i+2k_i/\beta_i \leqslant n$ is much more interesting. First we note that we can restrict our considerations to the values of $\beta_i$ and $k_i$ satisfying $\beta_i+ 2k_i/\beta_i=n$. Indeed, the value of the expression
$$
\begin{equation*}
\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2}\biggr\}
\end{equation*}
\notag
$$
for some $k_i=k$ and $\beta_i=\beta$ such that $\beta+2k/\beta < n$ is not greater than its value for $\beta_i'=n-2k/\beta$ and $k_i'= k\beta_i'/\beta$, which satisfy the equality $\beta_i'+2k_i'/\beta_i'=n$. Thus,
$$
\begin{equation*}
\begin{aligned} \, 2(T-i+1)\beta_i+k_i &=2(T-i+1)\biggl(n-\frac{2k_i}{\beta_i}\biggr)+ \frac{k_i}{\beta_i}\biggl(n-\frac{2k_i}{\beta_i}\biggr) \\ &= -\frac{2k_i^2}{\beta_i^2}+\frac{k_i}{\beta_i}(n-4(T-i+1))+2n(T-i+1). \end{aligned}
\end{equation*}
\notag
$$
This function is quadratic in $k_i/\beta_i$ and it attains its maximum value for However, the value at which the maximum is attained falls outside the domain of definition, since
$$
\begin{equation*}
\frac{n -4(T-i+1)}{4} \leqslant 4(T-i+1) \quad\Longleftrightarrow\quad i \leqslant T-\frac{n}{20}+1 ,
\end{equation*}
\notag
$$
which contradicts the hypotheses of the lemma. Hence this expression attains its maximum at the endpoint of the domain of definition, namely, for $k_i/\beta_i=4(T-i+1)$, and is equal there to $6(T-i+1)n-48(T-i+1)^2$, as required. Now let us estimate the expression $2(T-i+1)(\beta_i+k_i/\beta_i)+k_i-k_i^2/(2\beta_i^2)$ from above. The following equalities hold:
$$
\begin{equation*}
\begin{aligned} \, &2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2} \\ &\qquad =2(T-i+1)\biggl(n-\frac{k_i}{\beta_i}\biggr)+\frac{k_i}{\beta_i} \biggl(n- \frac{2k_i}{\beta_i}\biggr)-\frac{k_i^2}{2\beta_i^2} \\ &\qquad =-\frac{5k_i^2}{2\beta_i^2}+\frac{k_i}{\beta_i}(n-2(T-i+1))+2(T-i+1)n. \end{aligned}
\end{equation*}
\notag
$$
This function is quadratic in ${k_i}/{\beta_i}$ and attains its maximum for However, the value at which the maximum is attained falls outside the domain of definition, since
$$
\begin{equation*}
\frac{n-2(T-i+1)}{5} > 4(T-i+1) \quad\Longleftrightarrow\quad i > T-\frac{n}{22}+1.
\end{equation*}
\notag
$$
Hence, in fact, this function also attains its maximum for $k_i/\beta_i= 4(T-i+1)$ and this maximum value is also equal to $6(T-i+1)n-48(T-i+1)^2$, which completes the proof of Lemma 5. 8.3. Proof of Lemma 6As in the proof of Lemma 5, let us estimate the value of the expression $2(T-i+1)\beta_i+ k_i$ from above for ${k_i}/{\beta_i} \leqslant 4(T-i+1)$ and the value of the expression $2(T-i+ 1)(\beta_i+{k_i}/{\beta_i})+k_i-{k_i^2}/(2\beta_i^2)$ for ${k_i}/{\beta_i} > 4(T-i+1)$. We also assume that either ${k_i}/{\beta_i} \leqslant n$ or $\beta_i+2k_i/{\beta_i}=n$. In the first case we have
$$
\begin{equation*}
\begin{aligned} \, &\min\biggl\{2(T-i+1)\beta_i+k_i, 2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i- \frac{k_i^2}{2\beta_i^2}\biggr\} \\ &\qquad \leqslant 2(T-i+1)n+O(n), \end{aligned}
\end{equation*}
\notag
$$
which does not exceed $(n^2+ 16n(T-i+1)+4(T-i+1)^2)/10+O(n)$, since
$$
\begin{equation*}
\begin{aligned} \, & 2(T-i+1)n \leqslant \frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10} \\ &\quad\Longleftrightarrow\quad n^2+4(T-i+1)^2 \geqslant 4n(T-i+1). \end{aligned}
\end{equation*}
\notag
$$
In the second case, for ${k_i}/{\beta_i} \leqslant 4(T-i+1)$, similarly to Lemma 4 we have the estimate which, in turn, does not exceed the required bound since
$$
\begin{equation*}
\begin{aligned} \, & 6(T-i+1)n-48(T-i+1)^2 \leqslant \frac{n^2+16n(T-i+1)+4(T-i+1)^2}{10} \\ &\quad\Longleftrightarrow\quad n^2+484(T-i+1)^2 \geqslant 44(T-i+1)n. \end{aligned}
\end{equation*}
\notag
$$
For ${k_i}/{\beta_i} > 4(T-i+1)$ the maximum value of the expression
$$
\begin{equation*}
\begin{aligned} \, &2(T-i+1)\biggl(\beta_i+\frac{k_i}{\beta_i}\biggr)+k_i-\frac{k_i^2}{2\beta_i^2} \\ &\qquad=-\frac{5k_i^2}{2\beta_i^2}+\frac{k_i}{\beta_i}(n-2(T-i+1))+2(T-i+1)n \end{aligned}
\end{equation*}
\notag
$$
is attained at ${k_i}/{\beta_i}=(n-2(T-i+1))/5$, this value occurs in the domain of definition, and the maximum value itself is equal to Thus, the proof of Lemma 6 is complete. § 9. Proof of Theorem 9For each $n$ starting from a certain integer we construct a subset $W_n$ of vertices of the graph $G(n,3,1)$ such that $|W_n| \geqslant cn^2$ and
$$
\begin{equation*}
\rho(W_n) \leqslant \frac{9c^2n^3}{2}-cn^3+ 2q\biggl(\frac12-q\biggr)n^3+o(n^3).
\end{equation*}
\notag
$$
Let $k$ be the greatest positive integer such that $2k \leqslant n$. Then we have $n/2 \geqslant k \geqslant (n-1)/2$. We also take the asymptotic relation $k \sim n/2$ into account. Let $A$ denote the set of elements $\{1, 2, \dots, k\}$ and $B$ denote the set $\{k+1,{k+2}, \dots, 2k\}$. We will include in $W_n$ vertices that have two elements from the set $A$ and the third element from $B$, or the other way round. Notice that the total number of such vertices is Note that starting from a certain integer $n$ this quantity exceeds $cn^2$.For each pair of elements $1 \leqslant i \leqslant k$, $k+1 \leqslant j \leqslant 2k$ consider the set $M_{i,j}$ of vertices such that both of them contain the elements $i$ and $j$ and some other element from $A$ or $B$. Then we have $|M_{i,j}|=2k-2$. The set $W_n$ will be formed as a union of several $M_{i,j}$. It must be noted that two sets of this kind are either disjoint or share a unique element in the case when they have one common index. Moreover, the intersection of any three sets $M_{i,j}$ is empty. We divide all sets $M_{i,j}$ into $k$ groups. In the first group we include the sets $M_{1,k+1}, M_{2, k+2},\dots, M_{k,2k}$. In the $i$th group we include the sets $M_{j,k+j+i-1}$, where $1 \leqslant j \leqslant k$. If $k+j+i-1 > 2k$ in this notation, then the index is reduced by $k$: in other words, each next group differs from the previous one by a cyclic shift of the second index. Now we add vertex sets $M_{i,j}$ to $W_n$ one by one, starting from the first group, until the cardinality of their union becomes greater than $cn^2$. Note that each addition increases the number of vertices by $2k-2 < n$ at most. As a result, the number of vertices in our graph is $cn^2+o(n^2)$. Suppose that the vertex set $W_n$ has been formed as the union of all sets in the first $a$ groups and $b$ first sets in the $(a+1)$st group. Then $2b$ indices occur $a+1$ times and all other indices occur $a$ times. Let $T$ be the set of pairs $(i,j)$ taken as indices of the sets $M_{i,j}$. Then $|T|=ak+b$. Also consider the set $P$ of all indices that occur $a+1$ times and the set $Q$ of all indices that occur $a$ times. We stress that $b \leqslant k-1 < n/2$. Note that
$$
\begin{equation*}
|W_n| \geqslant \frac{\sum_{(i,j) \in T} |M_{i,j}|}{2}= \frac{(2k-2)(ak+b)}{2},
\end{equation*}
\notag
$$
since each vertex we have taken is contained in at most two sets $M_{i,j}$ such that $(i,j) \in T$. This yields the asymptotic relation $a=O(1)$. Let us calculate the precise number of vertices in this union by using the inclusion-exclusion principle:
$$
\begin{equation*}
\begin{aligned} \, |W_n| &=\sum_{(i,j) \in T} |M_{i,j}| -\sum_{(i,j), (s,w) \in T} |M_{i,j} \cap M_{s,w}| \\ &=(2k-2)(ak+b)-(2k-2b)C_a^2-2bC_{a+1}^2 \sim cn^2. \end{aligned}
\end{equation*}
\notag
$$
The second equality is due to the fact that $|M_{i,j} \cap M_{s,w}|=0$ whenever the pairs $\{i,j\}$ and $\{s,w\}$ have no common elements. Note that $(2k-2b)C_a^2+2bC_{a+1}^2=o(n^2)$. This yields the relation $ak+b \sim cn= pn/2 +qn$. It is obvious that if $q \neq 0$, then starting from some integer $n$ we have $a=p$ and also $b=qn+o(n)$. Consider the case $q=0$. It can be seen that $(2k-2)(ak+b) > cn^2$ and $(2k- 2) < n$, hence $ak+b > cn=pn/2$. Therefore, starting from some integer $n$ we have $a=p$ and also $b=O(1)$. Thus, in both cases we have $a=p$ and $b=qn+o(n)$. Now let us calculate the number of edges in $W_n$. We introduce the notation Note that two adjacent vertices share a unique element, hence they occur simultaneously in precisely one set $K_i$. This yields the relation Now let us estimate the number of edges in a particular set $K_i$. Consider an arbitrary index $j$ such that $(i,j) \in T$. It is easily seen that the set $M_{i,j}$ is independent in $K_i$. At the same time any two sets $M_{i,j}$ and $M_{i,s}$ such that $s \neq j$ have a unique common vertex, hence they share no pairs of vertices. Therefore, the number of pairs of nonadjacent vertices in $K_i$ is at least Hence we obtain the estimate
$$
\begin{equation*}
\rho(K_i) \leqslant C_{|K_i|}^2-\sum_{j\colon (i,j) \in T} C_{|M_{i,j}|}^2.
\end{equation*}
\notag
$$
Combining all such inequalities gives
$$
\begin{equation*}
\rho(W_n)=\sum_{i=1}^{2k} \rho(K_i) \leqslant \sum_{i=1}^{2k} C_{|K_i|}^2-2\sum_{(i,j) \in T} C_{|M_{i,j}|}^2.
\end{equation*}
\notag
$$
First we note that
$$
\begin{equation*}
2\sum_{(i,j) \in T} C_{|M_{i,j}|}^2=2(ak+b)C_{2k-2}^2 \sim cn^3.
\end{equation*}
\notag
$$
Then for each element we estimate the number of vertices in $W_n$ containing this element from above. Consider an element $s \in Q$. Then we have taken precisely $a$ sets $M_{i,j}$ that contain $2k-2$ vertices with the element $s$. Any other set $M_{i,j}$ that we have taken contains a unique vertex with the element $s$. Hence we obtain
$$
\begin{equation*}
|K_s| \leqslant (2k-2)a+ak+b-a=3ak+b-3a \leqslant 3ak+b.
\end{equation*}
\notag
$$
Similarly, for $s \in P$ we have
$$
\begin{equation*}
\begin{aligned} \, |K_s| &\leqslant (2k-2)(a+1)+ak+b-(a+1)=3ak+2k+b-3a-3 \\ &\leqslant 3ak+2k+b. \end{aligned}
\end{equation*}
\notag
$$
Now let us estimate the full sum:
$$
\begin{equation*}
\begin{aligned} \, \sum_{i=1}^{2k} C_{|K_i|}^2 &\leqslant \sum_{i=1}^{2k} \frac{K_i^2}{2} =\sum_{i \in Q} \frac{K_i^2}{2}+\sum_{i \in P} \frac{K_i^2}{2} \\ &\leqslant \frac{(2k-2b)(3ak+b)^2+ 2b(3ak+b+2k)^2}{2} \\ &= \frac{2k(3ak+b)^2+2b \cdot 4k^2+2b \cdot 2(3ak+b) \cdot 2k}{2} \\ &=\frac{18a^2k^3+12abk^2+ 2b^2k+8bk^2 +24abk^2 +8b^2k}{2} \\ &=\frac{18a^2k^3+36abk^2+10b^2k+8bk^2}{2} \\ &= \frac{9(ak+b)^2\cdot 2k+ 8bk^2-8b^2k}{2} \\ &=\frac{9c^2n^3+o(n^3)+8bk(k-b)}{2}. \end{aligned}
\end{equation*}
\notag
$$
Thus we obtain the required estimate:
$$
\begin{equation*}
\begin{aligned} \, \rho([cn^2]) &\leqslant \rho(W_n) \leqslant \sum_{i=1}^{2k} C_{|K_i|}^2-2\sum_{(i,j) \in T} C_{|M_{i,j}|}^2 \\ &\leqslant\frac{9c^2n^3}{2}+\frac{8bk(k-b)}{2}-cn^3+o(n^3) \\ &\sim \frac{9c^2n^3}{2}-cn^3+2q\biggl(\frac 12-q\biggr)n^3. \end{aligned}
\end{equation*}
\notag
$$
The proof of Theorem 9 is complete. § 10. Proof of Theorem 10For all values of $n$ starting from some integer we will construct a subset $W_n$ of vertices of the graph $G(n,3,1)$ such that $|W_n| \geqslant [cn^2]$ and $\rho(W_n) \leqslant c^2n^3/(2(1- p))+ g(n)$, where $g(n)=o(n^3)$. Let $x=[p n]$. Fix the sets $A_{1}=\{1,2,\dots,[x/2]\}$ and $A_{2}=\{ x+ 1,\dots,n\}$. Consider
$$
\begin{equation*}
W_n^{*}=\bigcup_{i\in A_{1}}\bigcup_{j\in A_{2}}\{(2i-1,2i,j)\} .
\end{equation*}
\notag
$$
Let us find the cardinality of $W_n^{*}$. There are $[x/2]$ ways to choose the first two components in the vector representation of a vertex and $n-x$ ways to choose the third component. Thus,
$$
\begin{equation*}
\begin{aligned} \, |W_n^{*}| &=\biggl[\frac{x}{2}\biggr] (n-x) \geqslant \biggl(\frac{pn}{2}-1\biggr) (n-pn) \\ &\geqslant \frac{p(1-p)}{2} n^{2}-n \geqslant [cn^2]-n. \end{aligned}
\end{equation*}
\notag
$$
Let us calculate the number of edges in this subgraph. Edges connect vertices that have a unique element in common, that is, vertices of the form $\{2i_{k}-1,2i_{k},j\}$ for some fixed $j$. The set $W_n^{*}$ contains $[x/2]$ vertices sharing an element $j$, and any two of these vertices are adjacent. The number of edges in this clique is
$$
\begin{equation*}
\frac{1}{2} \biggl[\frac{x}{2}\biggr] \biggl(\biggl[\frac{x}{2}\biggr]-1\biggr) \leqslant \frac{1}{2}\,\frac{pn}{2} \biggl(\frac{pn}{2}-1\biggr) \leqslant \frac{p^{2}n^{2}}{8}.
\end{equation*}
\notag
$$
Note that vertices in the other cliques either intersect in the first two elements or do not intersect at all. The number of such cliques (the number of ways to choose the element $j$) is $1-[pn]$. Thus,
$$
\begin{equation*}
\rho(W_n^{*}) \leqslant \frac{p^{2}(1-p)}{8} n^3+o(n^3)=\frac{c^2}{2(1-p)} n^3+o(n^3).
\end{equation*}
\notag
$$
Notice that each element from 1 to $n$ is contained in fewer than $n$ vertices of $W_n^{*}$. Then any vertex outside $W_n^{*}$ is adjacent to fewer than $3n$ vertices of $W_n^{*}$. Hence the addition of any $y$ vertices to the set $W_n^{*}$ increases the number of edges by $C_y^2+3ny$ at most. If $|W_n^{*}| \geqslant [cn^2]$, then we take this set as $W_n$ satisfying the condition. Otherwise, we construct $W_n$ as the union of $W_n^{*}$ and $y=[cn^2]-|W_n^{*}|$ arbitrary distinct vertices outside $W_n^{*}$. Note that $y \leqslant n$; then $C_y^2+3ny=o(n^3)$. Thus, The proof of Theorem 10 is complete. § 11. Proof of Theorem 11In the graph $G(n,3,1)$ we distinguish disjoint sets of vertices $S_i$ in the following way: Then $|S_i|=n-2i$. There are exactly $m=[n/2]$ sets of this kind, and therefore we have
$$
\begin{equation*}
\sum_{i=1}^m |S_i|=nm -2 \frac{m(m+1)}{2} \sim \frac{n^2}{4}.
\end{equation*}
\notag
$$
We see that, given any constant $c<1/4$, starting from some integer $n$ there exists a smallest natural number $k \leqslant m$ such that This also yields the relation $\sum_{i=1}^k |S_i| \sim cn^2$, since the cardinality of any set $S_i$ is $o(n^2)$.Consider a subset $W_n$ of vertices of the graph $G(n,3,1)$ such that Then we haveSetting $c=q(1-q)$, where $q<1/2$, we obtain $k \sim qn$. It remains to calculate the number of edges in the set $W_n$ of vertices we have chosen. We introduce the notation Two adjacent vertices share exactly one common element, hence they are simultaneously contained in just one of the sets $K_i$. This yields the relation Note that
$$
\begin{equation*}
\begin{gathered} \, |K_1|=|K_2|=n-2,\quad |K_3|=|K_4|=n-3, \quad \dots, \\ |K_{2k-1}|=|K_{2k}|=n-k-1\quad\text{and}\quad |K_{2k+1}|=\dots=|K_{n}|=k. \end{gathered}
\end{equation*}
\notag
$$
We also bear in mind that all original sets $S_i$ are independent sets in $K_i$. Then we obtain the estimate
$$
\begin{equation*}
\begin{aligned} \, \rho(W_n) &=\sum_{i=1}^{n} \rho(K_i)=\sum_{i=1}^{2k} \rho(K_i)+\sum_{i=2k+1}^{n} \rho(K_i)=\sum_{i=1}^{2k} \rho(K_i)+(n-2k)C_k^2 \\ &\leqslant \sum_{i=1}^{2k} (C_{|K_i|}^2-C_{|S_i|}^2)+ (n-2k)C_k^2 =2 \sum_{i=1}^{k} (C_{n-i-1}^2-C_{n-2i}^2)+(n-2k)C_k^2 \\ & \sim \sum_{i=1}^{k} (n-i-1)^2-\sum_{i=1}^{k} (n-2i)^2+(n-2k)\frac{k^2}{2} \\ &\sim \frac{n^3-(n-k)^3}{3}-\frac{n^3-(n-2k)^3}{6}+(n-2k)\frac{k^2}{2} \\ &\sim n^3 \frac{1-2(1-q)^3+(1-2q)^3+3(1-2q)q^2}{6}\sim n^3 \frac{9q^2-12q^3}{6} \\ &\sim \frac{3q^2-4q^3}{2} n^3. \end{aligned}
\end{equation*}
\notag
$$
The proof of Theorem 11 is complete. 
Citation in format AMSBIB
\Bibitem{DubNeuRai24} |
|
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|