Proof. For each vertex $v \in V$ , let $x(v)$ be a random weight chosen uniformly in $[0,1]$ , where all choices are independent. Let $H$ be the random spanning subgraph of $G$ consisting of all edges $uv \in E$ that satisfy $x(u)+x(v) \gt 1$ . Let $G^{(2)}$ denote the auxiliary graph on the set of vertices $V$ in which two distinct vertices are adjacent if and only if their distance in $G$ is either $1$ or $2$ . The maximum degree of $G^{(2)}$ is at most $d+d(d-1)=d^2$ and hence by Lemma 2.3 the set of vertices $V$ has a partition into $t=d^2+1$ pairwise disjoint subsets $V_1,V_2, \ldots,V_t$ , where

\begin{equation*}|V_i|=n_i \in \{ \lfloor n/(d^2+1) \rfloor, \lceil n/(d^2+1) \rceil \}\end{equation*}

for all $i$ and each $V_i$ is an independent set in $G^{(2)}$ . Note that this means that the distance in $G$ between any two distinct vertices $u,v \in V_i$ is larger than $2$ . As the degree of each vertex $v$ of $G$ in $H$ is determined by the random weights assigned to it and to its neighbours, it follows that for every fixed $0 \leq k \leq d$ , the $n_i$ indicator random variables $\{Z_{v,k}\;:\;v \in V_i\}$ where $Z_{v,k}=1$ iff the degree of $v$ in $H$ is $k$ , are mutually independent. By Lemma 2.2 each $Z_{v,k}$ is a Bernoulli random variable with expectation $1/(d+1)$ . For any fixed $k$ as above it thus follows, by Lemma 2.1 and the assumption inequality (1), that the probability that the number of vertices in $V_i$ whose degree in $H$ is $k$ deviates from $n_i/(d+1)$ by at least ${\varepsilon } n_i/(d+1)$ is smaller than $\frac{1}{(d^2+1)(d+1)}$ . By the union bound over all pairs $V_i,k$ , with positive probability this does not happen for any $k$ and any $V_i$ . But in this case for every $0 \leq k \leq d$ the total number of vertices with degree $k$ in $H$ deviates from $n/(d+1)$ by less than ${\varepsilon } \sum _i n_i/(d+1)={\varepsilon } n/(d+1).$ This completes the proof.

Proof. Start by modifying $G$ to a graph $G'$ obtained by repeatedly deleting any edge connecting two vertices, both of degrees larger than $\delta$ , as long as there are such edges. Thus $G'$ is a spanning subgraph of $G$ . It has minimum degree $\delta$ and every edge in it has at least one end-point of degree exactly $\delta$ . Let $G'^{(2)}$ denote the auxiliary graph on the set of vertices $V$ in which two distinct vertices are adjacent iff they are either adjacent or have a common neighbour in $G'$ . The maximum degree in $G'^{(2)}$ is at most

\begin{equation*}\max \{ \delta +\delta (\Delta -1), \Delta +\Delta (\delta -1)\}= \delta \Delta .\end{equation*}

We can now follow the argument in the proof of the previous proposition, splitting $V$ into $\delta \Delta +1$ nearly equal pairwise disjoint sets $V_i$ , and defining a spanning random subgraph $H$ of $G'$ (and hence of $G$ ) using independent random uniform weights in $[0,1]$ as before. Here for every vertex $v$ and every integer $k$ , the probability that the degree of $v$ in $H$ is $k$ , is at most $1/(\delta +1)$ . This, the obvious monotonicity, and the fact that the events corresponding to distinct members of $V_i$ are independent, imply, by Lemma 2.1 and by the assumption inequality (2), that the probability that $V_i$ contains at least $(1+{\varepsilon })|V_i|/(\delta +1)$ vertices of degree $k$ is smaller than $\frac{1}{(\delta \Delta +1)(\Delta +1)}$ . The desired result follows from the union bound, as before.

Proof. The proof is a slight modification of the previous one. Let $G'$ be the graph obtained from $G$ as before. Let $F$ denote the auxiliary graph on the set of vertices $X$ in which two distinct vertices are adjacent iff they are either adjacent or have a common neighbour in $G'$ . The maximum degree in this graph is at most $\delta \Delta .$ We can thus follow the argument in the proof of the previous proposition, splitting $X$ into $\delta \Delta +1$ nearly equal pairwise disjoint sets $X_i$ , and defining a spanning random subgraph $H$ of $G'$ (and hence of $G$ ) using the independent random uniform weights in $[0,1]$ as before.

Proof. Let $G=(V,E)$ , $\delta$ , $\varepsilon$ and $D$ be as above. As in the previous proofs we start by modifying $G$ to a graph $G'$ obtained by repeatedly deleting any edge connecting two vertices, both of degrees larger than $\delta$ , as long as there are such edges. Thus $G'$ is a spanning subgraph of $G$ ; it has minimum degree $\delta$ and the set of all its vertices of degree exceeding $\delta$ is an independent set. Let $A$ denote the set of all vertices of degree $\delta$ in $G'$ , $B$ the set of all vertices of degrees larger than $\delta$ and at most $D$ in $G'$ (if there are any), and $C$ the set of all vertices of degree exceeding $D$ . Since all edges from the vertices of $C$ lead to vertices of $A$ (as $B \cup C$ is an independent set) it follows, by double-counting, that $|C| D \lt |A| \delta \leq n \delta$ and thus $|C| \leq n \delta/D ={\varepsilon }\frac{n}{\delta +1}.$

If $C=\emptyset$ define $G''=G'$ ; otherwise let $G''$ be the graph obtained from $G'$ as follows. For every vertex $v \in C$ of degree $d (\gt D)$ replace $v$ by a set $S_v$ of $k_v=\lfloor d/\delta \rfloor$ new vertices $v_1,v_2, \ldots,v_{k_v}$ . Split the set of neighbours of $v$ in $G'$ (that are all in $A$ ) into $k_v$ pairwise disjoint sets $N_1, N_2, \ldots, N_{k_v}$ , each of size at least $\delta$ and at most $2 \delta$ , and join the vertex $v_i$ to all vertices in $N_i$ $(1 \leq i \leq k_v)$ . Thus $G''$ is obtained by splitting all vertices of $C$ , and there is a clear bijection between the edges of $G''$ and those of $G'$ . Let $X$ be an arbitrary subset of $n$ vertices of $G''$ containing all vertices in $A \cup B$ . The graph $G''$ has minimum degree $\delta$ and maximum degree at most $D$ ; hence by Proposition 2.6 [which can be applied by the assumption inequality (3)] it has a spanning subgraph $H''$ so that no degree is repeated more than $(1+{\varepsilon })\frac{n}{\delta +1}$ times among the vertices of $X$ . Let $H$ be the spanning subgraph of $G'$ (and hence of $G$ ) consisting of exactly the set of edges of $H''$ . The degree of each vertex in $A \cup B$ in $H''$ is the same as its degree in $H$ , hence $H$ contains at most $(1+{\varepsilon })\frac{n}{\delta +1}$ vertices of each fixed degree in $A \cup B$ (which is a subset of $X$ ). We have no control on the degrees of the vertices of $C$ in $H$ , but their total number is at most ${\varepsilon } \frac{n}{\delta +1}$ . Therefore $m(H) \leq (1+2{\varepsilon })\frac{n}{\delta +1}$ , completing the proof.

Proof of Theorem 1.5 : Let $G=(V,E)$ be a $d$ -regular graph on $n$ vertices. Since the assertion is trivial for $d \leq 8$ assume $d\gt 8$ . Put $k=\lceil d/4 \rceil$ and split $V$ arbitrarily into $k$ pairwise disjoint sets of vertices $V_1, \ldots,V_k$ , each of size at most $\lceil n/k \rceil$ . For each vertex $v \in V_i$ define $a(v)=\lceil d/2 \rceil -i$ and $b(v)=\lceil d/2 \rceil +k -i$ . It is easy to check that $\deg\!(v)=d$ and each such $a(v),b(v)$ satisfy (4) and (5). By Lemma 3.1 there is a spanning subgraph $H$ of $G$ in which the degree of every $v \in V_i$ is in the set

\begin{equation*}S_i=\{\lceil d/2 \rceil -i, \lceil d/2 \rceil -i+1, \lceil d/2 \rceil +k -i, \lceil d/2 \rceil +k -i+1\}.\end{equation*}

It is easy to check that no integer belongs to more than $2$ of the sets $S_i$ , implying that $m(H) \leq 2\lceil n/k \rceil \lt 8n/d+2,$ and completing the proof.

Proof of Theorem 1.6 : Let $G=(V,E)$ be a graph with $n$ vertices and minimum degree $\delta$ . As the result is trivial for $\delta \leq 16$ , assume $\delta \gt 16$ . Order the vertices of $G$ by degrees, that is, put $V=\{v_1, v_2, \ldots,v_n\}$ , where the degree of $v_i$ is $d_i$ and $d_1 \geq d_2 \geq \ldots \geq d_n$ . Put $k=\lceil \delta/4 \rceil$ and split the set of vertices into $m=\lceil n/k \rceil$ blocks $B_1, B_2, \ldots,B_m$ of consecutive vertices in the order above, each (besides possibly the last) containing $k$ vertices. Thus $B_i=\{v_{(i-1)k+1}, v_{(i-1)k+2}, \ldots,v_{ik}\}$ for all $i\lt m$ and $B_m=V-\cup _{i\lt m} B_i$ . Fix a block $B=B_i$ ; let $w_1, w_2, \ldots, w_k$ denote its vertices and let $f_1 \geq f_2 \geq \ldots \geq f_k$ be their degrees (assume now that $B$ is not the last block). For each vertex $w_i$ define $a_i=\lceil f_i/2 \rceil -i$ , $b_i=\lceil f_i/2 \rceil +k-i$ . For the last block $B_m$ define the numbers $a_i,b_i$ similarly, taking only the first $|B_m| (\leq k)$ terms defined as above. Note that the sequence $(a_1,a_2, \ldots,a_k)$ (as well as the possibly shorter one for the last block) is strictly decreasing, and so are the sequences $(a_1+1,a_2+1, \ldots,a_k+1)$ , $(b_1,b_2, \ldots,b_k)$ and $(b_1+1, b_2+1, \ldots,b_k+1)$ . Therefore, no integer belongs to more than $4$ of the sets $S(w_i)=\{a_i,a_i+1,b_i,b_i+1\}$ , $1 \leq i \leq k$ . Note also that the numbers $\deg\!(v)=f_i, a(v)=a_i, b(v)=b_i$ satisfy (4) and (5). By Lemma 3.1 there is a spanning subgraph $H$ of $G$ in which the degree of every vertex $v$ lies in the corresponding set $S(v)$ . Therefore $m(H) \leq 4m \lt 16\frac{n}{\delta }+4$ , completing the proof.

Proof of Theorem 1.7 : The proof is based on the simple known fact that the incidence matrix of any bipartite graph is totally unimodular (see, e.g., [Reference Schrijver17], page 318). Let $G=(V,E)$ be a bipartite graph and let $s=s(G)$ be its irregularity strength. By the definition of $s(G)$ there is a weight function assigning to each edge $e \in E$ a weight $w(e)$ which is a positive integer between $1$ and $s$ , so that all the sums $\sum _{e \ni v} w(e)$ , $v \in V$ are pairwise distinct. Consider the following system of linear inequalities in the variables $x(e), e \in E$ .

\begin{equation*} 0 \leq x(e) \leq 1 \ \text {for all} \ e \in E \end{equation*}

and

\begin{equation*} \left \lfloor \sum _{e \ni v} \frac {w(e)}{s} \right \rfloor \leq \sum _{e \ni v} x(e) \leq \left \lceil \sum _{e \ni v} \frac {w(e)}{s} \right \rceil \ \text {for all} \ v \in V. \end{equation*}

This system has a real solution given by $x(e)=\frac{w(e)}{s}$ for all $e \in E$ . Since the $V \times E$ incidence matrix of $G$ is totally unimodular there is an integer solution as well, namely, a solution in which $x(e) \in \{0,1\}$ for all $e \in E$ . Let $H$ be the spanning subgraph of $G$ consisting of all edges $e$ with $x(e)=1$ . For each integer $k$ the vertex $v$ can have degree $k$ in $H$ only if $k-1 \lt \sum _{e \ni v} \frac{w(e)}{s} \lt k+1$ , that is, only if the integer $\sum _{e \ni v} w(e)$ is strictly between $s(k-1)$ and $s(k+1)$ . As there are only $2s-1$ such integers, and the integers $\sum _{e \ni v} w(e)$ are pairwise distinct, it follows that $m(H,k) \leq 2s-1$ .

If $G$ is regular one can repeat the above proof replacing $w(e)$ by $w(e)-1$ for every $e$ and replacing $s$ by $s-1$ . This completes the proof of Theorem 1.7.

Proof. We describe an algorithm for generating the required numbers $x(e)$ . Think of these values as variables. During the algorithm, the variables $x(e)$ will always lie in the continuous interval $[0,1]$ . Call a variable $x(e)$ fixed if $x(e) \in \{0,1\}$ , otherwise call it floating. At the beginning of the algorithm, some (or all) variables $x(e)$ will possibly be floating, and as the algorithm proceeds, floating variables will become fixed. Once fixed, a variable does not change anymore during the algorithm, and at the end all variables will be fixed. For convenience, call an edge $e$ floating iff $x(e)$ is floating.

For each edge $e \in E$ , let $y_e$ denote the corresponding column of the $V \times E$ incidence matrix of $G$ , that is, the vector of length $|V|$ defined by $y_e(v)=1$ if $v \in e$ and $y_e(v)=0$ otherwise.

Start the algorithm with $x(e)=z(e)$ for all $e \in E$ . As long as the vectors $y_e$ corresponding to the floating edges $e$ (assuming there are such edges) are not linearly independent over the reals, let $\sum _{e \in E'} c_e y_e=0$ be a linear dependence, where $E'$ is a set of floating edges and $c_e \neq 0$ for all $e \in E'$ . Note that for any real $\nu$ , if we replace $x(e)$ by $x(e)+\nu c_e$ then the values of the sums

(7) \begin{equation} \sum _{e \ni v} x(e) \ \text{for all} \ v \in V \end{equation}

stay unchanged. As $\nu$ varies this determines a line of values of the variables $x(e)$ (in which the only ones that change are the variables $x(e)$ for $e \in E'$ ) so that the sums in (7) stay fixed along the line. By choosing $\nu$ appropriately we can find a point along this line in which all variables stay in $[0,1]$ and at least one of the floating variables in $E'$ reaches $0$ or $1$ . We now update the variables $x(e)$ as determined by this point, thus fixing at least one of the floating variables. Continuing in this manner the algorithm finds an assignment of the variables $x(e)$ so that for each $v \in V$ , $\sum _{e \ni v} x(e)=\sum _{e \ni v} z(e)$ and the set of vectors $y_e, e \in E'$ , where $E'$ is the set of floating edges, is linearly independent. Note that this implies that the set of edges in each connected component of the graph $(V,E')$ is either a tree, or contains exactly one cycle, which is odd.

As long as there is a connected component consisting of floating edges, which is not an odd cycle or a single edge, let $V''$ be the set of all vertices of such a component whose degree in the component exceeds $1$ . Let $E''$ be the set of edges of this component (recall that all of these edges are floating). Consider the following system of linear equations.

(8) \begin{equation} \sum _{e \ni v} x(e)=\sum _{e \ni v} z(e) \ \text{for all} \ v \in V''. \end{equation}

This system is viewed as one in which the only variables are $x(e)$ for $e \in E''$ . The other $x(e)$ appearing in the system are already fixed, and are thus considered as constants, and the values $z(e)$ are also constants. It is easy to check that the number of variables in this system, which is $|E''|$ , exceeds the number of equations, which is the number of vertices of degree at least $2$ in the component. Therefore there is a line of solutions, and as before we move to a point on this line which keeps all variables $x(e)$ in $[0,1]$ and fixes at least one variable $x(e)$ for some $e \in E''$ , shifting it to either $0$ or $1$ . Note, crucially, that each of the sums $\sum _{e \ni v} x(e)$ for $v \in V''$ stays unchanged, but the value of this sum for vertices of degree $1$ in the component may change.

Continuing this process we keep reducing the number of floating edges. When the graph of floating edges contains only connected components which are odd cycles or isolated edges we finish by rounding each floating variable $x(e)$ to either $0$ or $1$ , whichever is closer to its current value, where $x(e)=1/2$ is always rounded to $1$ . Once this is done, all variables $x(e)$ are fixed, that is $x(e) \in \{0,1\}$ for all $e$ . It remains to show that (6) holds for each $v \in V$ . To this end note that as long as the degree of $v$ in the graph consisting of all floating edges is at least $2$ , and the component in which it lies is not an odd cycle, the value of the sum $\sum _{e \ni v} x(e)$ stays unchanged (and is thus equal exactly to $\sum _{e \ni v} z(e)$ ) even after modifying the variables $x(e)$ in the corresponding step of the algorithm. Therefore, at the first time the degree of $v$ in this floating graph (the graph of floating edges) becomes $1$ , if this ever happens, the sum $\sum _{e \ni v} x(e)$ is still exactly $\sum _{e \ni v} z(e)$ . Afterwards this sum can change only by the change in the value of the unique floating edge incident with it, which is less than $1$ (as this value has been in the open interval $(0,1)$ and will end being either $0$ or $1$ ). The only case in which the final sum $\sum _{e \ni v} x(e)$ can differ by $1$ from $\sum _{e \ni v} z(e)$ is if the final step in which all floating edges incident with $v$ become fixed is a step in which the connected component of $v$ in the floating graph is an odd cycle, $x(e)=1/2$ for both edges of this component incident with $v$ , and both are rounded to the same value $1$ . In this case (6) holds with equality, and in all other cases it holds with a strict inequality. This completes the proof of the lemma.

Proof of Theorem 1.8 : The proof is similar to that of Theorem 1.7, replacing the argument using the total unimodularity of the incidence matrix of the graph by Lemma 4.1. Let $G=(V,E)$ be a graph let $s=s(G)$ be its irregularity strength. Thus there is a weight function assigning to each edge $e \in E$ a weight $w(e)$ which is a positive integer between $1$ and $s$ , so that all the sums $\sum _{e \ni v} w(e)$ , $v \in V$ are pairwise distinct. Define $z: E \mapsto [0,1]$ by $z(e)=w(e)/s$ for each $e \in E$ . By Lemma 4.1 there is a function $x: E \mapsto \{0,1\}$ so that for every $v \in V$ (6) holds. Let $H$ be the spanning subgraph of $G$ consisting of all edges $e$ with $x(e)=1$ . For each integer $k$ the vertex $v$ can have degree $k$ in $H$ only if

\begin{equation*} k-1 \leq \sum _{e \ni v} z(e) =\sum _{e \ni v} \frac {w(e)}{s} \lt k+1, \end{equation*}

that is, only if the integer $\sum _{e \ni v} w(e)$ is at least $s(k-1)$ and strictly smaller than $s(k+1)$ . As there are only $2s$ such integers, and the integers $\sum _{e \ni v} w(e)$ are pairwise distinct, it follows that $m(H,k) \leq 2s$ .

If $G$ is regular one can repeat the above proof replacing $w(e)$ by $w(e)-1$ for every $e$ and replacing $s$ by $s-1$ . This completes the proof.

Proof. We first prove (i). Given $j$ and $v$ , since $c_1(\!\deg\!(v)) \geq 1$ as $\deg\!(v) \geq \delta$ , there is at most one integer $1 \leq i \leq \delta -{s^*}$ such that $h(\!\deg\!(v), i) = c_1(\!\deg\!(v)) i + c_2 \cdot \deg\!(v) + c_3{\sqrt{\deg\!(v)}} + c_4 \in [j, j+1)$ . Thus each vertex independently has probability at most $\lfloor \sqrt{\delta } \rfloor/ \delta$ to satisfy $h(\!\deg\!(v), Z(v)) \in [j, j+\lfloor \sqrt{\delta } \rfloor )$ . By Chernoff’s Inequality (Lemma 2.1) and a union bound over $0 \leq j \leq n-1$ and $v$ , the probability that (i) is violated is at most $ n^2 e^{-(16(n/\delta ) (\sqrt{\delta }) \ln n)/(3 (n/\delta )(\sqrt{\delta }))} \lt n^2 e^{-4 \ln n} = 1/n^2$ .

To prove (ii), note that for each vertex $v$ , each of its neighbours independently has probability $\frac{{s^*}}{\delta }$ to be in $S$ . Therefore its expected degree in $S$ is $\frac{\deg\!(v){s^*}}{\delta }$ . By Chernoff’s Inequality and a union bound over $v$ , (ii) is violated with probability at most $2ne^{- 0.25 \deg\!(v){s^*}/(3\delta )} \lt 1/n^2$ .

To prove (iii), note that for each $1 \leq i \leq \delta -{s^*}$ , each neighbour of $v$ independently has probability $i/\delta$ to be in $B_{\delta -{s^*}-i+1} \cup \ldots \cup B_{\delta -{s^*}}$ , and thus the expected number of its neighbours in $B_{\delta -{s^*}-i+1} \cup \ldots \cup B_{\delta -{s^*}}$ is $\frac{i\deg\!(v)}{\delta }$ . By Chernoff’s Inequality, for any positive value $\mu$ , given $v \in B_i$ , the probability that (iii) is violated is at most $2e^{-\mu ^{2}/(3\max (i\deg\!(v)/\delta, \mu ))}$ . Plugging in $\mu = 12\sqrt{i \deg\!(v)/\delta } \ln n$ and noting that $\max (i\deg\!(v)/\delta, \mu )) \leq 12 \frac{i \deg\!(v)}{\delta } \ln n$ , the probability that (iii) is violated for $v \in B_i$ is at most $2 e^{- 12 \ln n/ 3}= 2/n^4$ . By a union bound over all vertices the probability that (iii) is violated is much smaller than $1/n^2$ .

Similarly we can prove (iv). Given $v \in S_i$ , each edge incident to $v$ independently has probability $\frac{\delta -{s^*}}{\delta } \cdot \frac{\delta - 4{s^*} i}{\delta -{s^*}} = \frac{\delta - 4{s^*} i}{\delta }$ to be active. Thus the expected number of active edges incident to $v \in S_i$ is $\frac{\deg\!(v)(\delta - 4{s^*} i)}{\delta }$ . Again by Chernoff’s Inequality and a union bound over $v$ , the first statement in (iv) is violated with probability at most $n 2e^{- \deg\!(v) \ln ^2 n/ (3(\delta - 4{s^*} i)\deg\!(v)/\delta )} \lt n2e^{-\ln ^2n/3}\lt 1/n^2$ . Similarly, for a neighbour $u$ of $v \in S_i$ , the edge $(v, u)$ randomly and independently has probability $\frac{\delta - 4{s^*} i}{\delta } \frac{32\delta \ln n}{{s^*} \sqrt{\deg\!(u)}} \leq \frac{32 (\delta - 4{s^*} i) \ln n}{{s^*} \sqrt{\delta }}$ to be both active and removable. By Chernoff’s Inequality and a union bound over $v$ the probability that the second statement is violated is much smaller than $1/n^2$ .

(v) is proved in almost the same way. Fix $1 \leq i \leq k$ and $u \in B$ . Each edge $uv$ independently has probability $\frac{{s^*}}{k\delta } \cdot \frac{\delta - 4{s^*} i}{\delta -{s^*}}$ to be active and satisfy $v \in S_i$ ; and it has probability $\frac{{s^*}}{k\delta } \cdot \frac{\delta - 4{s^*} i}{\delta -{s^*}} \cdot \frac{32\delta \ln n}{{s^*} \sqrt{\deg\!(u)}} = \frac{32 \ln n}{k} \cdot \frac{\delta - 4{s^*} i}{(\delta -{s^*})\sqrt{\deg\!(u)}} \gt \frac{30 \ln n}{k \sqrt{\deg\!(u)}}$ to be both active and removable and incident to $S_i$ . Thus for any $u \in B$ the expected number of edges $uv$ with $v \in S$ which are both active and removable is at least ${30\ln n}{\sqrt{\deg\!(u)}}$ . Applying Chernoff’s Inequality and a union bound it follows that the probability that the statement fails is much smaller than $2/n^2$ .

Proof. Given $v \in S_i$ we bound the number of vertices $u$ in $L(v)$ by bounding the number of vertices $u$ in all sets $S_j$ where $j$ satisfies both inequalities (11) and (12). These two inequalities together imply

\begin{equation*} \frac {\deg\!(v)}{\deg\!(u)} \left (1-\frac {4{s^*} i}{\delta } - \frac {34\ln n}{\delta ^{\epsilon }} \right ) - \frac {3{s^*}}{\delta } \leq 1-\frac {4{s^*} j}{\delta } \leq \frac {\deg\!(v)}{\deg\!(u)} \left ( 1 - \frac {4{s^*} i}{\delta } + \frac {3{s^*}}{\delta } \right ) + \frac {34\ln n}{\delta ^{\epsilon }}. \end{equation*}

This means the value of $\frac{4{s^*} j}{ \delta }$ can only lie in an interval of length $\frac{\deg\!(v)}{\deg\!(u)}\left (\frac{3{s^*}}{\delta } + \frac{34\ln n}{\delta ^{\epsilon }} \right ) + \frac{34\ln n}{\delta ^{\epsilon }} +\frac{3{s^*}}{\delta } \leq \frac{2\deg\!(v)}{\delta }\left (\frac{3{s^*}}{\delta } + \frac{34\ln n}{\delta ^{\epsilon }} \right ) \leq \frac{2\deg\!(v)}{\delta } \frac{37\ln n}{\delta ^{\epsilon }}$ where the last inequality uses $\epsilon \lt 1/4$ . This implies $j$ can only lie in an interval of length at most $\frac{\delta }{4{s^*}} \frac{2\deg\!(v)}{\delta } \frac{37\ln n}{\delta ^{\epsilon }} = \frac{\deg\!(v)}{2{s^*}} \frac{37\ln n}{\delta ^{\epsilon }}$ .

Since with probability $\frac{{s^*}}{k \delta }$ , the vertex $u$ lies in $S_j$ for any given $j$ , the probability that $u$ satisfies $u \in S_j$ for some $j$ with $I_{v,i} \cap I_{u,j} \neq \emptyset$ is at most

\begin{equation*}\frac {{s^*}}{k \delta } \left (\frac {\deg\!(v)}{2{s^*} } \frac {37\ln n}{\delta ^{\epsilon }}+1\right ) \leq \frac {{s^*}}{k \delta }\frac {\deg\!(v)}{{s^*} } \frac {37\ln n}{\delta ^{\epsilon }} = \frac {37\deg\!(v) \ln n}{k \delta ^{1+\epsilon } }. \end{equation*}

The first inequality uses the fact that $\epsilon \lt 1/4$ . Thus $\mathbb{E}[|L(v)|] \leq n\frac{37\deg\!(v) \ln n}{k \delta ^{1+\epsilon } }$ . Since the events for different vertices $u$ are independent, by Chernoff’s Inequality the probability that $|L(v)| \geq n\frac{42\deg\!(v) \ln n}{k \delta ^{1+\epsilon } }$ is at most $n^{-4}$ . By a union bound over $v$ , the desired result follows.

Proof. We use a modified version of the algorithm by Kalkowski, Karoński, and Pfender [Reference Kalkowski, Karoński and Pfender10]. All edge weights in $S$ are initialized to be $1/2$ .

Order the vertices of $S$ arbitrarily as $v_1, v_2, \ldots$ and process them sequentially starting from $v_1$ . When processing $v_i$ , we will find a set $\Lambda _{v_i}$ of the form $\{\frac{12a}{4}, \frac{12a+1}{4}\}$ for some $a \in \mathbb{Z}$ , such that throughout the later stages of the algorithm, $\Lambda _{v_i}$ will stay unchanged and the weight of $v_i$ will always stay in $\Lambda _{v_i}$ . Suppose we are processing $v_i$ for $i \geq 1$ . For each forward edge, that is, edge $v_i v_j$ where $j \gt i$ if exists, we allow to change the edge weight by increasing it by $0$ or $1/4$ ; for each backward edge $v_i v_j$ where $j \lt i$ if exists, we allow to change the weight by adding an element of $\{-1/4, 0, 1/4\}$ , where if the current weight of $v_j$ is the maximum value in $\Lambda _{v_j}$ , we can only change this backward edge by adding a member of $\{-1/4, 0\}$ , whereas if the current weight of $v_j$ is the minimum value in $\Lambda _{v_j}$ , we can only change this backward edge by adding a member of $\{0, 1/4\}$ . This rule guarantees the weight of $v_j$ which has been processed always stays in $\Lambda _{v_j}$ . Furthermore, by all combinations of the allowable changes, the weight of $v_i$ can achieve any value in an arithmetic progression $P_i$ with common difference $1/4$ and of length $\deg _S(v_i)$ . In addition, by our constraints on the structure of the sets $\Lambda _{v_i}$ , a vertex $v_i$ has weight in $\Lambda _{v_i} = \{\frac{12a}{4}, \frac{12a+1}{4}\}$ if and only if $v_i$ has weight in $J_{v_i} = \{\frac{12a}{4}, \frac{12a+1}{4}, \frac{12a+2}{4}, \ldots, \frac{12a+11}{4}\}$ . Thus there must be a set $ \{\frac{12b}{4}, \frac{12b+1}{4}, \frac{12b+2}{4}, \ldots, \frac{12b+11}{4}\} \subset P_i$ for some $b \in \mathbb{Z}$ which is shared by at most $\lfloor |L(v)|/ (( |P_i| -22)/12) \rfloor$ sets $J_{v_j}$ for $v_j \in L(v)$ and $j \lt i$ . Fix such a set $\{\frac{12b}{4}, \frac{12b+1}{4}, \frac{12b+2}{4}, \ldots, \frac{12b+11}{4}\} \subset P_i$ as $J_{v_i}$ and then ensure that the weight of $v_i$ lies in $\{ \frac{12b}{4}, \frac{12b+1}{4}\} = \Lambda _{v_i}$ by adjusting the weights of forward and backward edges appropriately, and then continue to $v_{i+1}$ . By Claim 5.3 and Lemma 5.2 (ii) which implies that $|P_i| \geq 0.5{s^*} \deg\!(v)/\delta$ ,

\begin{equation*} |L(v)|/ (( |P_i| -22)/12) \lt \frac {12 \cdot \frac {42n\deg\!(v) \ln n}{k \delta ^{1+\epsilon } } }{ 0.25 \deg\!(v) {s^*}/ \delta } = \frac {48\cdot 42 n}{k } \frac {\ln n}{\delta ^{\epsilon } {s^*} } = \frac {2016 n \ln n \ln \ln n}{\delta ^{1+\epsilon }} \end{equation*}

where the equality is by plugging in $k{s^*} = \delta/ \ln \ln n$ . Therefore we have shown that each set $J_{v_i}$ can be shared by at most $\lfloor \frac{2016 n \ln n \ln \ln n}{\delta ^{1+\epsilon }} \rfloor$ other $J_{v_j}$ for $v_j \in L(v_i)$ . Furthermore, if $J_v$ is different from $J_u$ which implies $J_v$ is disjoint from $J_u$ , then since the weight of $v$ is in $\Lambda _v \subset J_v$ and the weight of $u$ is in $\Lambda _u \subset J_u$ , the difference between the weights of $u$ and $v$ is at least $11/4$ . Lastly, notice that each edge changes its weight at most twice (once as a forward edge and once as a backward edge), so all edge weights in $S$ stay in $\{0, 1/4, 1/2, 3/4, 1\}$ . Therefore the first statement holds. The second statement holds by noticing that when $\delta ^{1+\epsilon } \gt 2016 n \ln n \ln \ln n$ , then $\lfloor \frac{2016 n \ln n \ln \ln n}{\delta ^{1+\epsilon }} \rfloor = 0$ .