# Critical Edge Identification: A K-Truss Based Model

Weijie Zhu1,3 Mengqi Zhang2 Chen Chen1∗ Xiaoyang Wang2 Fan Zhang4 Xuemin
Lin1,3,4 1East China Normal University, China
2Zhejiang Gongshang University, China
3Zhejiang Lab, Hangzhou, China
4The University of New South Wales, Australia {weijie.zhu93, mengqiz.zjgsu,
<EMAIL_ADDRESS>{chenc<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In a social network, the strength of relationships between users can
significantly affect the stability of the network. In this paper, we use the
$k$-truss model to measure the stability of a social network. To identify
critical connections, we propose a novel problem, named $k$-truss
minimization. Given a social network $G$ and a budget $b$, it aims to find $b$
edges for deletion which can lead to the maximum number of edge breaks in the
$k$-truss of $G$. We show that the problem is NP-hard. To accelerate the
computation, novel pruning rules are developed to reduce the candidate size.
In addition, we propose an upper bound based strategy to further reduce the
searching space. Comprehensive experiments are conducted over real social
networks to demonstrate the efficiency and effectiveness of the proposed
techniques.††*Corresponding author

##  1 Introduction

As a key problem in graph theory and social network analysis, the mining of
cohesive subgraphs, such as $k$-core, $k$-truss, clique, etc, has found many
important applications in real life Cohen (2008); Tsourakakis et al. (2013);
Wen et al. (2016); Yu et al. (2013). The mined cohesive subgraph can serve as
an important metric to evaluate the properties of a network, such as network
engagement. In this paper, we use the $k$-truss model to measure the
cohesiveness of a social network. Unlike $k$-core, $k$-truss not only
emphasizes the users’ engaged activities (_i.e.,_ number of friends), but also
requires strong connections among users. That is, the $k$-truss of $G$ is the
maximal subgraph where each edge is involved in at least $k-2$ triangles. Note
that triangle is an important building block for the analysis of social
network structure Xiao et al. (2017); Cui et al. (2018). Thus the number of
edges in the $k$-truss can be utilized to measure the stability of network
structure.

Figure 1: Motivation Example

The breakdown of a strong connection may affect other relationships, which can
make certain relationships involved in less than $k-2$ triangles and removed
from the $k$-truss. Hence, it will lead to a cascading breakdown of
relationships eventually. To identify the critical edges, in this paper, we
investigate the $k$-truss minimization problem. Given a social network $G$ and
a budget $b$, $k$-truss minimization aims to find a set $B$ of $b$ edges,
which will result in the largest number of edge breaks in the $k$-truss by
deleting $B$.

Figure 1 is a toy social network with 10 users. Suppose $k$ is 4. Then only
the blue and red edges belong to the $4$-truss. If we delete edge
$(v_{2},v_{5})$, it will affect the connections among other users and lead to
the removal of all the blue edges from the $4$-truss, since they no longer
meet the requirement of $4$-truss. We can see that the deletion of one single
edge can seriously collapse the social network. The $k$-truss minimization
problem can find many applications in real life. For instance, given a social
network, we can reinforce the community by paying more attention to the
critical relationships. Also, we can strengthen the important connections to
enhance the stability of a communication network or detect vital connections
in enemy’s network for military purpose.

The main challenges of this problem lie in the following two aspects. Firstly,
we prove that the problem is NP-hard. It means that it is non-trivial to
obtain the result in polynomial time. Secondly, the number of edges in a
social network is usually quite large. Even if we only need to consider the
edges in $k$-truss as candidates, it is still a large amount of edges to
explore. To the best of our knowledge, we are the first to investigate the
$k$-truss minimization problem through edge deletion. We formally define the
problem and prove its hardness. Novel pruning rules are developed to reduce
the searching space. To further speed up the computation, an upper bound based
strategy is proposed.

##  2 Preliminaries

###  2.1 Problem Definition

We consider a social network $G$ as an undirected graph. Given a subgraph
$S\subseteq G$, we use $V_{S}$ (resp. $E_{S}$) to denote the set of nodes
(resp. edges) in $S$. $N(u,S)$ is the neighbors of $u$ in $S$. $deg(u,S)$
equals $|N(u,S)|$, denoting the degree of $u$ in $S$. $m=|E_{G}|$ is the
number of edges in $G$. Assuming the length of each edge equals 1, a triangle
is a cycle of length 3 in the graph. For $e\in E_{G}$, a containing-_e_
-triangle is a triangle which contains $e$.

######  Definition 1 ($k$-core).

Given a graph $G$, a subgraph $S$ is the k-core of $G$, denoted as $C_{k}$, if
(i) $S$ satisfies degree constraint, i.e., $deg(u,S)\geq k$ for every $u\in
V_{S}$; and (ii) $S$ is maximal, i.e., any supergraph of $S$ cannot be a
k-core.

######  Definition 2 (edge support).

Given a subgraph $S\subseteq G$ and an edge $e\in E_{S}$, the edge support of
$e$ is the number of containing-e-triangles in $S$, denoted as $sup(e,S)$.

######  Definition 3 ($k$-truss).

Given a graph $G$, a subgraph $S$ is the $k$-truss of $G$, denoted by $T_{k}$,
if (i) $sup(e,S)\geq k-2$ for every edge $e\in E_{S}$; (ii) $S$ is maximal,
i.e., any supergraph of $S$ cannot be a $k$-truss; and (iii) $S$ is non-
trivial, i.e., no isolated node in $S$.

######  Definition 4 (trussness).

The trussness of an edge $e\in E_{G}$, denoted as $\tau(e)$, is the largest
integer $k$ that satisfies $e\in E_{T_{k}}$ and $e\notin E_{T_{k+1}}$.

Based on the definitions of $k$-core and $k$-truss, we can see that $k$-truss
not only requires sufficient number of neighbors, but also has strict
constraint over the strength of edges. A $k$-truss is at least a ($k$-1)-core.
Therefore, to compute the $k$-truss, we can first compute the ($k$-1)-core and
then find the $k$-truss over ($k$-1)-core by iteratively removing all the
edges that violate the $k$-truss constraint. The time complexity is
$O(m^{1.5})$ Wang and Cheng (2012). Given a set $B$ of edges in $G$, we use
$T_{k}^{B}$ to denote the $k$-truss after deleting $B$. We use $|T_{k}^{B}|$
to denote the number of edges in $T_{k}^{B}$. We define the followers
$F(B,T_{k})$ of $B$ as the edges that are removed from $T_{k}$ due to the
deletion of $B$. Then our problem can be formally defined as follows.

Given a graph $G$ and a budget $b$, the $k$-truss minimization problem aims to
find a set $B^{*}$ of $b$ edges, such that the $|T_{k}^{B^{*}}|$ is minimized.
It is also equivalent to finding an edge set $B^{*}$ that can maximize
$|F(B^{*},T_{k})|$, _i.e.,_

$B^{*}=\operatorname*{arg\,max}_{B\subseteq E_{G}\wedge|B|=b}|F(B,T_{k})|.$

(a) Constructed Example for NP-hard Proof

(b) Structure Illustration

(c) Construction of $V$ for $R=3$

Figure 2: Example for NP-hard

According to Theorem 1 and 2, the $k$-truss minimization problem is NP-hard
for $k\geq 5$, and the objective function is monotonic but not submodular.

######  Theorem 1.

For $k\geq 5$, the $k$-truss minimization problem is NP-hard.

###### Proof.

For $k\geq 5$, we sketch the proof for $k=5$. A similar construction can be
applied for the case of $k>5$. When $k=5$, we reduce the $k$-truss
minimization problem from the maximum coverage problem Karp (1972), which aims
to find $b$ sets to cover the largest number of elements, where $b$ is a given
budget. We consider an instance of maximum coverage problem with $s$ sets
$T_{1}$, $T_{2}$, .., $T_{s}$ and $t$ elements $\\{e_{1},..,e_{t}\\}$ =
$\cup_{1\leq i\leq s}T_{i}$. We assume that the maximum number of elements
inside $T$ is $R\leq t$. Then we construct a corresponding instance of the
$k$-truss minimization problem in a graph $G$ as follows. Figure 2(a) is a
constructed example for $s=3,t=4,R=2$.

We divide $G$ into three parts, $V$, $N$ and $P$. 1) $V$ consists of $s$
parts. Each part $V_{i}$ corresponds to $T_{i}$ in the maximum coverage
problem instance. 2) $N$ consists of $t$ parts. Each part $N_{i}$ corresponds
to $e_{i}$ in the maximum coverage problem instance. 3) $P$ is a dense
subgraph. The support of edges in $P$ is no less than $k-2+b$. Specifically,
suppose $T_{i}$ consists of $r_{i}\leq R$ elements, $V_{i}$ consists of
$4R-r_{i}+1$ nodes and $8R-r_{i}$ edges. To construct $V_{i}$, we first
construct a $(4R-2r_{i})$-polygon. Then, we add a node $v^{i}_{0}$ in the
center of $(4R-2r_{i})$-polygon and add $4R-2r_{i}$ edges between $v^{i}_{0}$
and $v^{i}_{1},...,v^{i}_{4R-2r_{i}}$. Finally, we further add $r_{i}$ nodes
$v^{i}_{4R-2r_{i}+1},...,v^{i}_{4R-r_{i}}$ and $3r_{i}$ edges
$\\{(v^{i}_{0},v^{i}_{4R-2r_{i}+1}),(v^{i}_{1},v^{i}_{4R-2r_{i}+1}),(v^{i}_{2},v^{i}_{4R-2r_{i}+1}),...,(v^{i}_{0},$
$v^{i}_{4R-r_{i}}),(v^{i}_{2r_{i}-1},v^{i}_{4R-r_{i}}),(v^{i}_{2r_{i}},v^{i}_{4R-r_{i}})\\}$.
With the construction, the edges in $V$ have support no larger than 3. We use
$P$ to provide support for edges in $V$ and make the support of edges in $V$
to be 3. Each part in $N$ consists of $2R+2$ nodes and the structure is a list
of $4R$ triangles which is shown in Figure 2(a). For each element $e_{i}$ in
$T_{j}$, we add two triangles between $N_{i}$ and $V_{j}$ to make them
triangle connected. The structure is shown in 2(b). Note that each edge in
$N_{i}$ and $V_{j}$ can be used at most once. We can see that edges in $N$
have support no larger than 3. Finally, we use $P$ to provide support for
edges in $N$ and make the support of edges in $N$ to be 3. Then the
construction is completed. The construction of $V_{i}$ for $R=3$ is shown in
Figure 2(c).

With the construction, we can guarantee that 1) deleting any edge in $V_{i}$
can make all the edges in $V_{i}$ and the edges in $N_{j}$ who have
connections with $V_{i}$ deleted from the truss. 2) Only the edges in $V_{i}$
can be considered as candidates. 3) Except the followers in $N$, each $V_{i}$
has the same number of followers. In Figure 2(a), deletion of each $V_{i}$ can
make $8R$ edges (except the edges in $N$) removed. Consequently, the optimal
solution of $k$-truss minimization problem is the same as the maximum coverage
problem. Since the maximum coverage problem is NP-hard, the theorem holds. ∎

######  Theorem 2.

The objective function $f(x)=|F(x,T_{k})|$ is monotonic but not submodular.

###### Proof.

Suppose $B\subseteq B^{\prime}$. For every edge $e$ in $F(B,T_{k})$, $e$ will
be deleted from the $k$-truss when deleting $B^{\prime}$. Thus $f(B)\leq
f(B^{\prime})$ and $f$ is monotonic. Given two sets $A$ and $B$, if $f$ is
submodular, it must hold that $f(A\cup B)+f(A\cap B)\leq f(A)+f(B)$. We show
that the inequality does not hold by constructing a counter example. In Figure
1, for $k=4$, suppose $A=\\{(v_{5},v_{6})\\}$ and $B=\\{(v_{7},v_{8})\\}$. We
have $f(A)=4$, $f(B)=0$, $f(A\cup B)=12$ and $f(A\cap B)=0$. The inequation
does not hold. $f$ is not submodular. ∎

Input : $G$: a social network, $k$: truss constraint, $b$: the budget

Output : $B$: the set of deleted edges

1 $B\leftarrow\emptyset$ ; $T_{k}\leftarrow k$-truss of $G$;

2 while $|B|<b$ do

3

4 $e^{*}\leftarrow\operatorname*{arg\,max}_{e\in E_{T_{k}}}|F(e,T_{k})|$ ;

5 delete $e^{*}$ from $T_{k}$ and update $T_{k}$ ;

6 $B\leftarrow B\cup\\{e^{\ast}\\}$ ;

7

8 end while

return $B$

Algorithm 1 Baseline Algorithm

###  2.2 Baseline Algorithm

For the _k_ -truss minimization problem, a naive solution is to enumerate all
the possible edge sets of size $b$, and return the best one. However, the size
of a real-world social network is usually very large. The number of
combinations is enormous to enumerate. Due to the complexity and non-
submodular property of the problem, we resort to the greedy framework.
Algorithm 1 shows the baseline greedy algorithm. It is easy to verify that we
only need to consider the edges in the $k$-truss as candidates. The algorithm
iteratively finds the edge with the largest number of followers in the current
$k$-truss (Line 3). The algorithm terminates when $b$ edges are found. The
time complexity of the baseline algorithm is $O(bm^{2.5})$.

Input : $G$: a social network, $k$: truss constraint, $b$: the budget

Output : $B$: the set of deleted edges

1 $B\leftarrow\emptyset$ ; $T_{k}\leftarrow$ $k$-truss of $G$ ; /* compute
$k$-truss */;

2 while $|B|<b$ do

3 mark all edges in $T_{k}$ as unvisited ;

4 $T\leftarrow$ FindGroup ($T_{k}$) ; /* Line 12-19 */;

5 for each $e$ in $T$ do

6 compute $F(e,T_{k})$ ;

7 $T\leftarrow T\backslash F(e,T_{k})$ ;

8

9 $e^{\ast}\leftarrow$ the edge with the most followers ;

10 update $k$-truss $T_{k}$ ;

11 $B\leftarrow B\cup\\{e^{\ast}\\}$ ;

12

13return $B$

14 Function  _FindGroup (_$S$_)_:

15 $C\leftarrow\emptyset$ ; gID $\leftarrow 0$; /* $C$ stores the candidates
*/;

16 for each $e\in S$ do

17 if $sup(e,S)=k-2$ and $e$ is unvisited then

18 GroupExpansion ($S,e$); /* Line 20-32 */;

19 gID$++$ ;

20

21

22 return $C$

23End Function

24 Function  _GroupExpansion (_$S,e$_)_:

25 $Q\leftarrow\emptyset$ $;Q.enqueue(e)$; mark $e$ as visited ;

26 while $Q\neq\emptyset$ do

27 $e^{\prime}(u,v)\leftarrow Q.dequeue()$;

28 foreach $a\in N(u,T_{k})\cap N(v,T_{k})$ do

29 if $(u,a)$ is unvisited and $sup=k-2$ then

30 $Q.enqueue((u,a))$ ;

31 mark $(u,a)$ as visited ;

32

33 if $(v,a)$ is unvisited and $sup=k-2$ then

34 $Q.enqueue((v,a))$ ;

35 mark $(v,a)$ as visited ;

36

37 update $C$ ;

38

39

40

End Function

Algorithm 2 Group based Algorithm

##  3 Group Based Solution

In this section, novel pruning techniques are developed to accelerate the
search in baseline algorithm.

###  3.1 Candidate Reduction

Before introducing the pruning rules, we first present some definitions
involved.

######  Definition 5 (triangle adjacency).

Given two triangles $\triangle_{1},$ $\triangle_{2}$ in $G$, they are triangle
adjacent if $\triangle_{1}$ and $\triangle_{2}$ share a common edge, which
means $\triangle_{1}\cap\triangle_{2}\neq\varnothing$.

######  Definition 6 (triangle connectivity).

Given two triangles $\triangle_{s},\triangle_{t}$ in $G$, they are triangle
connected, denoted as $\triangle_{s}\leftrightarrow\triangle_{t}$, if there
exists a sequence of $\theta$ triangles
$\triangle_{1},\triangle_{2},...,\triangle_{\theta}$ in $G$, such that
$\triangle_{s}=\triangle_{1},\triangle_{t}=\triangle_{\theta}$, and for $1\leq
i<\theta$, $\triangle_{i}$ and $\triangle_{i+1}$ are triangle adjacent.

For two edges $e$ and $e^{\prime}$, we say they are triangle adjacent, if $e$
and $e^{\prime}$ belong to the same triangle. As shown in the baseline
algorithm, we only need to consider the edges in $T_{k}$ as candidates. Lemma
1 shows that we only need to explore the edges in $Q$.

######  Lemma 1.

Given a $k$-truss $T_{k}$, let $P=\\{e~{}|~{}sup(e,T_{k})$ $=k-2\\}$. If an
edge $e$ has at least one follower, $e$ must be in $Q$, where
$Q=\\{e~{}|~{}e\in T_{k}\wedge\exists e^{\prime}\in P$ where $e$ and
$e^{\prime}$ are triangle adjacent$\\}$.

###### Proof.

We prove the lemma by showing that edges in $E_{G}\setminus Q$ do not have
followers. We divide $E_{G}\setminus Q$ into two sets. 1) For edge with
trussness less than $k$, it will be deleted during the $k$-truss computation.
2) For an edge $e$ in $T_{k}$, if $e$ is not triangle adjacent with any edge
in $P$, it means $e$ is triangle adjacent with edges such as $e^{\prime}$
whose $sup(e^{\prime},T_{k})>k-2$. If we delete $e$, all the edges triangle
adjacent with $e$ will still have support at least $k-2$ in $T_{k}$. Thus, $e$
has no follower. The lemma is correct. ∎

Based on Lemma 2, we can skip the edges that are the followers of the explored
ones.

######  Lemma 2.

Given two edges $e_{1},e_{2}\in T_{k}$, if $e_{1}\in F(e_{2},T_{k})$, then we
have $F(e_{1},T_{k})\subseteq F(e_{2},T_{k})$.

###### Proof.

$e_{1}\in F(e_{2},T_{k})$, it implies that $e_{1}$ will be deleted during the
deletion of $e_{2}$. Therefore, each edge in $F(e_{1},T_{k})$ will be deleted
when $e_{2}$ is deleted. Consequently, we have $F(e_{1},T_{k})\subseteq
F(e_{2},T_{k})$. ∎

To further reduce the searching space, we introduce a pruning rule based on
$k$-support group.

######  Definition 7 ($k$-support group).

Given a k-truss $T_{k}$, a subgraph $S\subseteq T_{k}$ is a $k$-support group
if it satisfies : 1) $\forall e$ $\in S$, $sup(e,T_{k})=k-2$. 2) $\forall
e_{1},e_{2}\in S$, suppose $e_{1}\in\triangle_{s}$, $e_{2}\in\triangle_{t}$.
There exists a sequence of $\theta\geq 2$ triangles
$\triangle_{1},...,\triangle_{\theta}$ with $\triangle_{s}=\triangle_{1}$,
$\triangle_{t}=\triangle_{\theta}$. For $i\in[1,\theta)$, $\triangle_{i}$
$\cap\triangle_{i+1}={e}$ and $sup(e,T_{k})=k-2$. 3) $S$ is maximal, i.e., any
supergraph of $S$ cannot be a $k$-support group.

Lemma 3 shows that edges in the same $k$-support group are equivalent. The
deletion of any edge in a $k$-support group can lead to the deletion of the
whole $k$-support group.

######  Lemma 3.

$S$ is a $k$-support group of $T_{k}$. For $\forall e\in S$, if we delete $e$,
we can have $S$ deleted from $T_{k}$.

###### Proof.

Since $S$ is a $k$-support group of $T_{k}$, for $\forall e,e^{\prime}\in S$,
suppose that $e\in\triangle_{s},e^{\prime}\in\triangle_{t}$, there exists a
sequence of $\theta$ triangles $\triangle_{1},...,\triangle_{\theta}$ with
$\triangle_{s}=\triangle_{1},\triangle_{t}=\triangle_{\theta}$. For
$i\in[1,\theta)$, $\triangle_{i}\cap\triangle_{i+1}={e_{i}}$ and
$sup(e_{i},T_{k})=k-2$. The deletion of any edge inside the group will destroy
the corresponding triangles and decrease the support of triangle adjacent
edges by 1. It will lead to a cascading deletion of subsequent triangle edges
in the group due to the violation of truss constraint. Therefore, the lemma
holds. ∎

According to Lemma 3, we only need to add one edge from a $k$-support group to
the candidate set, and the other edges in the group can be treated as the
followers of the selected edge. In the following lemma, we can further prune
the edges that are adjacent with multiple edges in a $k$-support group.

######  Lemma 4.

Suppose that $e\in T_{k}$ and $sup(e,T_{k})=w>k-2$. For a $k$-support group
$S$, if $e$ belongs to more than $w-k+2$ triangles, each of which contains at
least one edge in $S$, then $e$ is a follower of $S$.

###### Proof.

According to Lemma 3, by removing an edge from $S$, we have $S$ deleted from
$T_{k}$. Since $e$ belongs to more than $w-k+2$ triangles, each of which
contains at least one edge in $S$, the support of $e$ will decrease by more
than $w-k+2$ due to the deletion of $S$. So its support will be less than
$k-2$ and it will be deleted due to the support constraint. Thus, $e$ is a
follower of $S$. ∎

###  3.2 Group Based Algorithm

We improve the baseline algorithm by integrating all the pruning rules above,
and the details are shown in Algorithm 2. In each iteration, we first find
$k$-support groups of current $T_{k}$ and compute the candidate set $T$
according to Lemma 3 (Line 4). This process, _i.e.,_ FindGroup function,
corresponds to Line 12-19. It can be done by conducting BFS search from edges
in $T_{k}$. We use a hash table to maintain the group id (_i.e.,_ gID) for
each edge and the gID starts from 0 (Line 13). For each unvisited edge with
support of $k-2$, we conduct a BFS search from it by calling function
GroupExpansion (Line 20-32). During the BFS search, we visit the edges that
are triangle adjacent with the current edge, and push the edges with support
of $k-2$ into the queue if they are not visited (Line 25 and 28). The edges,
which are visited in the same BFS round, are marked with the current gID. For
the visited edges with support larger than $k-2$, we use a hash table to
record its coverage with the current $k$-support group, and update the
candidate set based on Lemma 4 (Line 31). According to Lemma 2, we can further
update the candidate set after computing the followers of edges (Line 7).

##  4 Upper Bound Based Solution

The group based algorithm reduces the size of candidate set by excluding the
edges in the same $k$-support group and the followers of $k$-support groups,
which greatly accelerates the baseline method. However, for each candidate
edge, we still need lots of computation to find its followers. Given an edge,
if we can obtain the upper bound of its follower size, then we can speed up
the search by pruning unpromising candidates. In this section, we present a
novel method to efficiently calculate the upper bound required.

###  4.1 Upper Bound Derivation

Before introducing the lemma, we first present some basic definitions. Recall
that $\tau(e)$ denotes the trussness of $e$.

######  Definition 8 ($k$-triangle).

A triangle $\triangle_{uvw}$ is a k-triangle, if the trussness of each edge is
no less than $k$.

######  Definition 9 ($k$-triangle connectivity).

Two triangles $\triangle_{s}$ and $\triangle_{t}$ are $k$-triangle connected,
denoted as $\triangle_{s}\stackrel{{\scriptstyle
k}}{{\leftrightarrow}}\triangle_{t}$, if there exists a sequence of
$\theta\geq 2$ triangles $\triangle_{1},...,\triangle_{\theta}$ with
$\triangle_{s}=\triangle_{1},\triangle_{t}=\triangle_{\theta}$. For
$i\in[1,\theta)$, $\triangle_{i}\cap\triangle_{i+1}={e}$ and $\tau(e)=k$.

We say two edges $e,e^{\prime}$ are $k$-triangle connected, denoted as
$e\stackrel{{\scriptstyle k}}{{\leftrightarrow}}e^{\prime}$, if and only if 1)
$e$ and $e^{\prime}$ belong to the same $k$-triangle, or 2)
$e\in\triangle_{s},e^{\prime}\in\triangle_{t}$, with
$\triangle_{s}\stackrel{{\scriptstyle k}}{{\leftrightarrow}}\triangle_{t}$.

######  Definition 10 ($k$-truss group).

Given a graph $G$ and an integer $k\geq 3$, a subgraph $S$ is a $k$-truss
group if it satisfies: 1) $\forall e\in S,\tau(e)=k$. 2) $\forall
e,e^{\prime}\in S,e\stackrel{{\scriptstyle k}}{{\leftrightarrow}}e^{\prime}$.
3) $S$ is maximal, i.e., there is no supergraph of $S$ satisfying conditions 1
and 2.

Based on the definition of $k$-truss group, Lemma 5 gives an upper bound of
$|F(e,T_{k})|$.

######  Lemma 5.

If $e$ is triangle adjacent with $\theta$ k-truss groups $g_{1}$,
$g_{2},...,g_{\theta}$, we have
$|F(e,T_{k})|\leq\sum\limits_{i=1}^{\theta}|E_{g_{i}}|$.

###### Proof.

Suppose $sup(e,T_{k})=w$, we have $w\geq k-2$, so $e$ is contained by $w$
triangles and is triangle adjacent with $2w$ edges. We divide the edges which
are triangle adjacent with $e$ in $T_{k}$ into two parts. 1)
$\tau(e^{\prime})>k$. Since the deletion of $e$ may cause $\tau(e^{\prime})$
to decrease at most 1 Huang et al. (2014); Akbas and Zhao (2017), we have
$\tau(e^{\prime})\geq k$ after deleting $e$, which means $e^{\prime}$ has no
contribution to $F(e,T_{k})$. 2) $\tau(e^{\prime})=k$. Suppose $e^{\prime}\in
g_{i}$. The deletion of $e$ can cause trussness of each edge in $g_{i}$ to
decrease at most 1. Then $e^{\prime}$ can contribute to $|F(e,T_{k})|$ with at
most $|E_{g_{i}}|$. Thus, $\sum\limits_{i=1}^{\theta}|E_{g_{i}}|$ is an upper
bound of $|F(e,T_{k})|$. ∎

###  4.2 Upper Bound Based Algorithm

Based on Lemma 5, we can skip the edges whose upper bound of follower size is
less than the best edge in the current iteration. However, given the trussness
of each edge, it may still be prohibitive to find the $k$-truss group that
contains an edge $e$, since in the worst case we need to explore all the
triangles in the graph. To compute the upper bound efficiently, we construct
an index to maintain the relationships between edges and their $k$-truss
groups.

To find the $k$-truss group for a given edge $e$, we extend the GroupExpansion
function in Line 20-32 of Algorithm 2. It also follows the BFS search manner.
The difference is that when we explore an adjacent triangle, it must satisfy
the $k$-triangle constraint, and we only enqueue an edge, whose trussness
satisfies $k$-triangle connectivity constraint. After finishing the BFS search
starting from $e$, its involved $k$-truss groups can be found.

After deleting an edge $e$ in the current iteration, the constructed $k$-truss
groups may be changed. Therefore, we need to update the $k$-truss groups for
the next iteration. The update algorithm consists of two parts, _i.e.,_ update
the trussness and update the groups affected by the changed trussness. To
update the edge trussness, we apply the algorithm in Huang et al. (2014),
which can efficiently update the edge trussness after deleting an edge $e$.
Given the edges with changed trussness, we first find the subgraph induced by
these edges. Then we reconstruct the $k$-truss groups for the induced subgraph
and update the original ones. Based on the $k$-truss groups constructed, we
can compute the upper bound of followers for edges efficiently. The final
algorithm, named UP-Edge, integrates all the techniques proposed in Section 3
and 4.

##  5 Experiment

###  5.1 Experiment Setting

In the experiments, we implement and evaluate the following algorithms. 1)
Exact: naive algorithm that enumerates all the combinations. 2) Support: in
each iteration, it selects the edge that is triangle adjacent with the edge
with minimum support in the $k$-truss. 3) Baseline: baseline algorithm in
Section 2.2. 4) GP-Edge: group based algorithm in Section 3. 5) UP-Edge: upper
bound based algorithm in Section 4.

We employ 9 real social networks (_i.e.,_ Bitcoin-alpha, Email-Eu-core,
Facebook, Brightkite, Gowalla, DBLP, Youtube, Orkut, LiveJournal) to evaluate
the performance of the proposed methods. The datasets are public
available111https://snap.stanford.edu/data/, https://dblp.org/xml/release/.
Since the Exact algorithm is too slow, we only run Exact algorithm on Email-
Eu-core and Bitcoin-alpha dataset.

Since the properties of datasets are quite different, we set the default $k$
as 10 for 4 datasets (Gowalla, Youtube, Brightkite, DBLP) and set the default
$k$ as 20 for 3 datasets (Facebook, LiveJournal, Orkut). We set default $b$ as
5 for all datasets. All the programs are implemented in C++. All the
experiments are performed on a machine with an Intel Xeon 2.20 GHz CPU and 128
GB memory running Linux.

###  5.2 Effectiveness Evaluation

To evaluate the effectiveness of the proposed methods, we report the number of
followers by deleting $b$ edges. Since UP-Edge only accelerates the speed of
Baseline and GP-Edge, we only report the results of UP-Edge here. Due to the
huge time cost of Exact, we show the result on 3 datasets, that is, Bitcoin-
alpha, Email-Eu-core and Artificial network (generated by GTGraph with 500
nodes and 5000 edges).

We set $k=11$ and $8$ for Bitcoin-alpha and Artificial network respectively,
and vary $b$ from 1 to 4. In Figure 3(a), we can see that there is only a
slight drop when b=3. In Figure 3(b), there is only a small drop when b=4. In
Figure 3(c), as we can see, UP-Edge also shows comparable results with Exact
and they all outperform Support significantly. Similar results can be observed
in Figure 3(d)-3(f) over all the datasets and the selected datasets. Figure
3(e) and 3(f) show the results on LiveJournal by varying $b$ and $k$. As
observed, the number of followers for the two algorithms are positive
correlated with $b$, and $k$ has a great impact on follower size.

(a) Bitcoin-alpha (k=11)

(b) Artificial (k=8)

(c) Email-Eu-core (b=2)

(d) All datasets

(e) LiveJournal (vary $b$)

(f) LiveJournal (vary $k$)

Figure 3: Effectiveness Evaluation Figure 4: Case study on DBLP, k=10, b=1

Figure 4 shows a case study on DBLP with $k=10,b=1$. We can see that the edge
between Lynn A. Volk and David W. Bates is the most pivotal relationship. This
edge has 264 followers (grey edges in the figure). It is interesting that most
followers have no direct connection with them.

###  5.3 Efficiency Evaluation

To evaluate the efficiency, we compare the response time of UP-Edge and GP-
Edge with Baseline . We first conduct the experiments on all the datasets with
default settings. Figure 5 shows the response time of the three algorithms. We
can see that UP-Edge and GP-Edge significantly outperform Baseline in all the
datasets because of the pruning techniques developed. UP-Edge is faster than
GP-Edge due to the contribution of upper bound derived. Figure 6 shows the
results conducted on LiveJournal by varying $b$ and $k$. We can see that when
$b$ grows, the response time increases since more edges need to be selected.
When $k$ grows, the response time decreases since the searching space becomes
smaller.

Figure 5: Running time on all datasets

(a) LiveJournal (vary $b$)

(b) LiveJournal (vary $k$)

Figure 6: Efficiency Evaluation

##  6 Related Work

Graph processing has been a hot topic in many areas recently, which usually
requires much more computation comparing with some traditional queries Luo et
al. (2008); Wang et al. (2010, 2015). Cohesive subgraph identification is of
great importance to social network analysis. In the literature, different
definitions of cohesive subgraphs are proposed, such as $k$-core Seidman
(1983); Wen et al. (2016), $k$-truss Huang and Lakshmanan (2017), clique
Tsourakakis et al. (2013), dense neighborhood graph Kreutzer et al. (2018),
etc. In the literature, numerous research is conducted to investigate the
$k$-truss decomposition problem under different settings, including in-memory
algorithms Cohen (2008), external-memory algorithms Wang and Cheng (2012),
distributed algorithms Chen et al. (2014), etc. In some studies, authors
leverage the $k$-truss property to mine required communities Huang et al.
(2014); Huang and Lakshmanan (2017). Huang et al. Huang et al. (2016)
investigate the truss decomposition problem in uncertain graphs. Recently,
some research focuses on modifying the graph to maximize/minimize the
corresponding metric Bhawalkar et al. (2015); Zhang et al. (2017); Zhu et al.
(2018); Medya et al. (2018). Bhawalkar et al. Bhawalkar et al. (2015) propose
the anchored $k$-core problem, which tries to maximize the $k$-core by
anchoring $b$ nodes, while Zhang et al. Zhang et al. (2017) and Zhu et al. Zhu
et al. (2018) investigate the problem of $k$-core minimization by deleting
nodes and edges, respectively. In Medya et al. (2018), Medya et al. try to
maximize the node centrality by adding edges to the graph. However, these
techniques cannot be extended for our problem.

##  7 Conclusion

In this paper, we study the _k_ -truss minimization problem. We first formally
define the problem. Due to the hardness of the problem, a greedy baseline
algorithm is proposed. To speed up the search, different pruning techniques
are developed. In addition, an upper bound based strategy is presented by
leveraging the $k$-truss group concept. Lastly, we conduct extensive
experiments on real-world social networks to demonstrate the advantage of the
proposed techniques.

## References

  * Akbas and Zhao [2017] Esra Akbas and Peixiang Zhao.  Truss-based community search: a truss-equivalence based indexing approach.  PVLDB, 10(11):1298–1309, 2017.
  * Bhawalkar et al. [2015] Kshipra Bhawalkar, Jon Kleinberg, Kevin Lewi, Tim Roughgarden, and Aneesh Sharma.  Preventing unraveling in social networks: the anchored k-core problem.  SIAM Journal on Discrete Mathematics, 29(3):1452–1475, 2015.
  * Chen et al. [2014] Pei-Ling Chen, Chung-Kuang Chou, and Ming-Syan Chen.  Distributed algorithms for k-truss decomposition.  In IEEE International Conference on Big Data, 2014.
  * Cohen [2008] Jonathan Cohen.  Trusses: Cohesive subgraphs for social network analysis.  National Security Agency Technical Report, 2008.
  * Cui et al. [2018] Yi Cui, Di Xiao, and Dmitri Loguinov.  On efficient external-memory triangle listing.  TKDE, 2018.
  * Huang and Lakshmanan [2017] Xin Huang and Laks V. S. Lakshmanan.  Attribute-driven community search.  PVLDB, 2017.
  * Huang et al. [2014] Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu.  Querying k-truss community in large and dynamic graphs.  In SIGMOD, pages 1311–1322, 2014.
  * Huang et al. [2016] Xin Huang, Wei Lu, and Laks V.S. Lakshmanan.  Truss decomposition of probabilistic graphs: Semantics and algorithms.  In SIGMOD, 2016.
  * Karp [1972] Richard M. Karp.  Reducibility among combinatorial problems.  In Complexity of Computer Computations, pages 85–103, 1972.
  * Kreutzer et al. [2018] Stephan Kreutzer, Roman Rabinovich, and Sebastian Siebertz.  Polynomial kernels and wideness properties of nowhere dense graph classes.  ACM Trans. Algorithms, 15(2), 2018.
  * Luo et al. [2008] Yi Luo, Wei Wang, and Xuemin Lin.  Spark: A keyword search engine on relational databases.  In ICDE, 2008.
  * Medya et al. [2018] Sourav Medya, Arlei Silva, Ambuj Singh, Prithwish Basu, and Ananthram Swami.  Group centrality maximization via network design.  In ICDM, 2018.
  * Seidman [1983] Stephen B. Seidman.  Network structure and minimum degree.  Social Networks, 5(3):269–287, 1983.
  * Tsourakakis et al. [2013] Charalampos Tsourakakis, Francesco Bonchi, Aristides Gionis, Francesco Gullo, and Maria Tsiarli.  Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees.  In KDD, 2013.
  * Wang and Cheng [2012] Jia Wang and James Cheng.  Truss decomposition in massive networks.  Proc. VLDB Endow., 2012.
  * Wang et al. [2010] Chaokun Wang, Jianmin Wang, Xuemin Lin, Wei Wang, Haixun Wang, Hongsong Li, Wanpeng Tian, Jun Xu, and Rui Li.  Mapdupreducer: detecting near duplicates over massive datasets.  In SIGMOD, 2010.
  * Wang et al. [2015] Xiang Wang, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Wei Wang.  Ap-tree: Efficiently support continuous spatial-keyword queries over stream.  In ICDE, 2015.
  * Wen et al. [2016] Dong Wen, Lu Qin, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu.  I/O efficient core graph decomposition at web scale.  In ICDE, 2016.
  * Xiao et al. [2017] Di Xiao, Yi Cui, Daren BH Cline, and Dmitri Loguinov.  On asymptotic cost of triangle listing in random graphs.  In PODS, 2017.
  * Yu et al. [2013] Weiren Yu, Xuemin Lin, Wenjie Zhang, Lijun Chang, and Jian Pei.  More is simpler: Effectively and efficiently assessing node-pair similarities based on hyperlinks.  PVLDB, 7(1), 2013.
  * Zhang et al. [2017] Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin.  Finding critical users for social network engagement: The collapsed k-core problem.  In AAAI, 2017.
  * Zhu et al. [2018] Weijie Zhu, Chen Chen, Xiaoyang Wang, and Xuemin Lin.  K-core minimization: An edge manipulation approach.  In CIKM, 2018.


# Optimal gradient estimates of solutions to the insulated conductivity
problem in dimension greater than two

Hongjie Dong  ,  YanYan Li  and  Zhuolun Yang  Division of Applied
Mathematics, Brown University, 182 George Street, Providence, RI 02912, USA
<EMAIL_ADDRESS>Department of Mathematics, Rutgers University, 110
Frelinghuysen Rd, Piscataway, NJ 08854, USA<EMAIL_ADDRESS>Institute
for Computational and Experimental Research in Mathematics, Brown University,
121 South Main Street, Providence, RI 02903, USA<EMAIL_ADDRESS>
###### Abstract.

We study the insulated conductivity problem with inclusions embedded in a
bounded domain in $\mathbb{R}^{n}$. The gradient of solutions may blow up as
$\varepsilon$, the distance between inclusions, approaches to $0$. It was
known that the optimal blow up rate in dimension $n=2$ is of order
$\varepsilon^{-1/2}$. It has recently been proved that in dimensions $n\geq
3$, an upper bound of the gradient is of order $\varepsilon^{-1/2+\beta}$ for
some $\beta>0$. On the other hand, optimal values of $\beta$ have not been
identified. In this paper, we prove that when the inclusions are balls, the
optimal value of $\beta$ is
$[~{}-(n-1)+\sqrt{(n-1)^{2}+4(n-2)}~{}]/4\in(0,1/2)$ in dimensions $n\geq 3$.

###### Key words and phrases:

optimal gradient estimates, high contrast coefficients, insulated conductivity
problem, degenerate elliptic equation, maximum principle

###### 2020 Mathematics Subject Classification:

35J15, 35Q74, 74E30, 74G70, 78A48

H. Dong is partially supported by Simons Fellows Award 007638, NSF Grant
DMS-2055244, and the Charles Simonyi Endowment at the Institute of Advanced
Study.

Y.Y. Li is partially supported by NSF Grants DMS-1501004, DMS-2000261, and
Simons Fellows Award 677077.

Z. Yang is partially supported by NSF Grants DMS-1501004, DMS-2000261, and the
Simons Bridge Postdoctoral Fellowship at Brown University

##  1\. Introduction and main results

First we describe the nature of the domain. Let $\Omega\subset\mathbb{R}^{n}$
be a bounded domain with $C^{2}$ boundary containing two
$C^{2,\gamma}(0<\gamma<1)$ relatively strictly convex open sets $D_{1}$ and
$D_{2}$ with dist$(D_{1}\cup D_{2},\partial\Omega)>c>0$. Let

$\varepsilon:=\mbox{dist}(D_{1},D_{2})$

and $\widetilde{\Omega}:=\Omega\setminus\overline{(D_{1}\cup D_{2})}$. The
conductivity problem can be modeled by the following elliptic equation:

$\begin{cases}\mathrm{div}\Big{(}a_{k}(x)\nabla{u}_{k}\Big{)}=0&\mbox{in}~{}\Omega,\\\
u_{k}=\varphi(x)&\mbox{on}~{}\partial\Omega,\end{cases}$

where $\varphi\in{C}^{2}(\partial\Omega)$ is given, and

$a_{k}(x)=\begin{cases}k\in(0,\infty)&\mbox{in}~{}D_{1}\cup{D}_{2},\\\
1&\mbox{in}~{}\widetilde{\Omega}.\end{cases}$

In the context of electric conduction, the elliptic coefficients $a_{k}$ refer
to conductivities, and the solutions $u_{k}$ represent voltage potential. From
an engineering point of view, it is significant to estimate the magnitude of
the electric fields in the narrow region between the inclusions, which is
given by $|\nabla u_{k}|$. This problem is analogous to the Lamé system
studied by Babuška, Andersson, Smith, and Levin [BASL], where they analyzed
numerically that, when the ellipticity constants are bounded away from $0$ and
infinity, the gradient of solutions remain bounded independent of
$\varepsilon$, the distance between inclusions. Later, Bonnetier and Vogelius
[BV] proved that when $\varepsilon=0$, $|\nabla u_{k}|$ is bounded for a fixed
$k$ and circular inclusions $D_{1}$ and $D_{2}$ in dimension $n=2$. This
result was extended by Li and Vogelius [LV] to general second order elliptic
equations of divergence form with piecewise Hölder coefficients and general
shape of inclusions $D_{1}$ and $D_{2}$ in any dimension. Furthermore, they
established a stronger piecewise $C^{1,\alpha}$ control of $u_{k}$, which is
independent of $\varepsilon$. Li and Nirenberg [LN] further extended this
global Lipschitz and piecewise $C^{1,\alpha}$ result to general second order
elliptic systems of divergence form, including the linear system of
elasticity. Some higher order derivative estimates in dimension $n=2$ were
obtained in [DZ, DL, JiKang].

When $k$ equals to $\infty$ (inclusions are perfect conductors) or $0$
(insulators), it was shown in [Kel, BudCar, Mar] that the gradient of
solutions generally becomes unbounded as $\varepsilon\to 0$. Ammari et al. in
[AKLLL] and [AKL] considered the perfect and insulated conductivity problems
with circular inclusions in $\mathbb{R}^{2}$, and established optimal blow-up
rates $\varepsilon^{-1/2}$ in both cases. Yun extended in [Y1] and [Y2] the
results above allowing $D_{1}$ and $D_{2}$ to be any bounded strictly convex
smooth domains.

The above gradient estimates in dimension $n=2$ were localized and extended to
higher dimensions by Bao, Li, and Yin in [BLY1] and [BLY2]. For the perfect
conductor case, they proved in [BLY1] that

$\begin{cases}\|\nabla u\|_{L^{\infty}(\widetilde{\Omega})}\leq
C\varepsilon^{-1/2}\|\varphi\|_{C^{2}(\partial\Omega)}&\mbox{when}~{}n=2,\\\
\|\nabla u\|_{L^{\infty}(\widetilde{\Omega})}\leq
C|\varepsilon\ln\varepsilon|^{-1}\|\varphi\|_{C^{2}(\partial\Omega)}&\mbox{when}~{}n=3,\\\
\|\nabla u\|_{L^{\infty}(\widetilde{\Omega})}\leq
C\varepsilon^{-1}\|\varphi\|_{C^{2}(\partial\Omega)}&\mbox{when}~{}n\geq
4.\end{cases}$

These bounds were shown to be optimal in the paper and they are independent of
the shape of inclusions, as long as the inclusions are relatively strictly
convex. Moreover, many works have been done in characterizing the singular
behavior of $\nabla u$, which are significant in practical applications. For
further works on the perfect conductivity problem and closely related ones,
see e.g. [ACKLY, BT1, BT2, DL, KLY1, KLY2, L, LLY, LWX, BLL, BLL2, DZ, KL, CY,
ADY, Gor, LimYun] and the references therein.

For the insulated conductivity problem, it was proved in [BLY2] that

$\|\nabla u\|_{L^{\infty}(\widetilde{\Omega})}\leq
C\varepsilon^{-1/2}\|\varphi\|_{C^{2}(\partial\Omega)}\quad\mbox{when}~{}n\geq
2.$ (1.1)

The upper bound is optimal for $n=2$ as mentioned above.

Yun [Y3] studied the following free space insulated conductivity problem in
$\mathbb{R}^{3}$: Let $H$ be a harmonic function in $\mathbb{R}^{3}$,
$D_{1}=B_{1}\left(0,0,1+\frac{\varepsilon}{2}\right)$, and
$D_{2}=B_{1}\left(0,0,-1-\frac{\varepsilon}{2}\right)$,

$\begin{cases}\Delta{u}=0&\mbox{in}~{}\mathbb{R}^{3}\setminus\overline{(D_{1}\cup
D_{2})},\\\ \frac{\partial
u}{\partial\nu}=0&\mbox{on}~{}\partial{D}_{i},~{}i=1,2,\\\
u(x)-H(x)=O(|x|^{-2})&\mbox{as}~{}|x|\to\infty.\end{cases}$

He proved that for some positive constant $C$ independent of $\varepsilon$,

$\max_{|x_{3}|\leq\varepsilon/2}|\nabla u(0,0,x_{3})|\leq
C\varepsilon^{\frac{\sqrt{2}-2}{2}}.$ (1.2)

He also showed that this upper bound of $|\nabla u|$ on the
$\varepsilon$-segment connecting $D_{1}$ and $D_{2}$ is optimal for
$H(x)\equiv x_{1}$. Although this result does not provide an upper bound of
$|\nabla u|$ in the complement of the $\varepsilon$-segment, it has added
support to a long time suspicion that the upper bound $\varepsilon^{-1/2}$
obtained for dimension $n=3$ in [BLY2] is not optimal.

The upper bound (1.1) was recently improved by Li and Yang [LY2] to

$\|\nabla u\|_{L^{\infty}(\widetilde{\Omega})}\leq
C\varepsilon^{-1/2+\beta}\|\varphi\|_{C^{2}(\partial\Omega)}\quad\mbox{when}~{}n\geq
3,$

for some $\beta>0$. When insulators are unit balls, a more explicit constant
$\beta(n)$ was given by Weinkove in [We] for $n\geq 4$ by a different method.
The constant $\beta(n)$ obtained in [We] presumably improves that in [LY2]. In
particular, it was proved in [We] that $\beta(n)$ approaches $1/2$ from below
as $n\to\infty$. However, the optimal blow up rate in dimensions $n\geq 3$
remained unknown. We draw reader’s attention to a recent survey paper [Kang]
by Kang, where in the conclusions section, the three-dimensional case is
described as an outstanding problem.

In this paper, we focus on the following insulated conductivity problem in
dimensions $n\geq 3$, and give an optimal gradient estimate for a certain
class of inclusions including two balls of any size:

$\left\\{\begin{aligned} -\Delta u&=0\quad\mbox{in }\widetilde{\Omega},\\\
\frac{\partial u}{\partial\nu}&=0\quad\mbox{on}~{}\partial{D}_{i},~{}i=1,2,\\\
u&=\varphi\quad\mbox{on }\partial\Omega,\end{aligned}\right.$ (1.3)

where $\varphi\in{C}^{2}(\partial\Omega)$ is given, and
$\nu=(\nu_{1},\ldots,\nu_{n})$ denotes the inner normal vector on
$\partial{D}_{1}\cup\partial{D}_{2}$.

We use the notation $x=(x^{\prime},x_{n})$, where
$x^{\prime}\in\mathbb{R}^{n-1}$. After choosing a coordinate system properly,
we can assume that near the origin, the part of $\partial D_{1}$ and $\partial
D_{2}$, denoted by $\Gamma_{+}$ and $\Gamma_{-}$, are respectively the graphs
of two $C^{2,\gamma}(0<\gamma<1)$ functions in terms of $x^{\prime}$. That is,
for some $R_{0}>0$,

$\displaystyle\Gamma_{+}=$
$\displaystyle\left\\{x_{n}=\frac{\varepsilon}{2}+f(x^{\prime}),~{}|x^{\prime}|<R_{0}\right\\},$
$\displaystyle\Gamma_{-}=$
$\displaystyle\left\\{x_{n}=-\frac{\varepsilon}{2}+g(x^{\prime}),~{}|x^{\prime}|<R_{0}\right\\},$

where $f$ and $g$ are $C^{2,\gamma}$ functions satisfying

$f(x^{\prime})>g(x^{\prime})\quad\mbox{for}~{}~{}0<|x^{\prime}|<R_{0},$
$f(0^{\prime})=g(0^{\prime})=0,\quad\nabla_{x^{\prime}}f(0^{\prime})=\nabla_{x^{\prime}}g(0^{\prime})=0,$
(1.4)
$f(x^{\prime})-g(x^{\prime})=a|x^{\prime}|^{2}+O(|x^{\prime}|^{2+\gamma})\quad\mbox{for}~{}~{}0<|x^{\prime}|<R_{0},$
(1.5)

with $a>0$. Here and throughout the paper, we use the notation $O(A)$ to
denote a quantity that can be bounded by $CA$, where $C$ is some positive
constant independent of $\varepsilon$. For $0<r\leq R_{0}$, we denote

$\displaystyle\Omega_{r}:=\left\\{(x^{\prime},x_{n})\in\widetilde{\Omega}~{}\big{|}~{}-\frac{\varepsilon}{2}\right.$
$\displaystyle\left.+g(x^{\prime})<x_{n}<\frac{\varepsilon}{2}+f(x^{\prime}),~{}|x^{\prime}|<r\right\\}.$
(1.6)

By standard elliptic estimates, the solution $u\in H^{1}(\widetilde{\Omega})$
of (1.3) satisfies

$\|u\|_{C^{1}(\widetilde{\Omega}\setminus\Omega_{R_{0}/2})}\leq C.$ (1.7)

We will focus on the following problem near the origin:

$\left\\{\begin{aligned} -\Delta u&=0\quad\mbox{in }\Omega_{R_{0}},\\\
\frac{\partial u}{\partial\nu}&=0\quad\mbox{on }\Gamma_{+}\cup\Gamma_{-},\\\
\|u\|&{}_{L^{\infty}(\Omega_{R_{0}})}\leq 1.\end{aligned}\right.$ (1.8)

It was proved in [BLY2] that for $u\in H^{1}(\Omega_{R_{0}})$ satisfying
(1.8),

$|\nabla u(x)|\leq C(\varepsilon+|x^{\prime}|^{2})^{-1/2},\quad\forall
x\in\Omega_{R_{0}},$ (1.9)

where $C$ is a positive constant depending only on $n,R_{0},a,\|f\|_{C^{2}}$,
and $\|g\|_{C^{2}}$, and is in particular independent of $\varepsilon$. The
above mentioned improvement on (1.1) in [LY2, We] also apply to (1.9).

Our main results of this paper are as follows.

######  Theorem 1.1.

For $n\geq 3$, $\varepsilon\in(0,1/4)$, let $u\in H^{1}(\Omega_{R_{0}})$ be a
solution of (1.8) with $f,g$ satisfying (1.4) and (1.5). Then there exists a
positive constant $C$ depending only on $n$, $R_{0}$, $\gamma$, a positive
lower bound of $a$, and an upper bound of $\|f\|_{C^{2,\gamma}}$ and
$\|g\|_{C^{2,\gamma}}$, such that

$|\nabla u(x)|\leq
C\|u\|_{L^{\infty}(\Omega_{R_{0}})}(\varepsilon+|x^{\prime}|^{2})^{\frac{\alpha-1}{2}}\quad\forall
x\in\Omega_{R_{0}/2},$ (1.10)

where

$\alpha=\alpha(n):=\frac{-(n-1)+\sqrt{(n-1)^{2}+4(n-2)}}{2}\in(0,1).$ (1.11)

Note that $\alpha(n)$ is monotonically increasing in $n$, and

$\alpha(n)=1-\frac{2}{n}+O(\frac{1}{n^{2}})\quad\mbox{as}~{}~{}n\to\infty.$

For $n=3$, the exponent $\frac{\alpha-1}{2}=\frac{\sqrt{2}-2}{2}$ is the same
as the exponent in (1.2). For $n\geq 4$, the exponent $\frac{\alpha-1}{2}$ is
strictly greater than the one obtained in [We].

A consequence of Theorem 1.1 is, in view of (1.7), as follows.

######  Corollary 1.2.

For $n\geq 3$, $\varepsilon\in(0,1/4)$, let $D_{1},D_{2}$ be two balls of
radius $r_{1},r_{2}$, center at $(0^{\prime},\varepsilon/2+r_{1})$ and
$(0^{\prime},-\varepsilon/2-r_{2})$, respectively. Let $u\in
H^{1}(\widetilde{\Omega})$ be the solution of $\eqref{equzero}$. Then there
exists a positive constant $C$ depending only on $n$, $r_{1}$, $r_{2}$, and
$\|\partial\Omega\|_{C^{2}}$ such that

$\|\nabla u\|_{L^{\infty}(\widetilde{\Omega})}\leq
C\|\varphi\|_{C^{2}(\partial\Omega)}\varepsilon^{\frac{\alpha-1}{2}},$ (1.12)

where $\alpha$ is given by (1.11).

Estimate (1.12) is optimal as shown in the following theorem.

######  Theorem 1.3.

For $n\geq 3$, $\varepsilon\in(0,1/4)$, let $\Omega=B_{5}$, and $D_{1},D_{2}$
be the unit balls center at $(0^{\prime},1+\varepsilon/2)$ and
$(0^{\prime},-1-\varepsilon/2)$, respectively. Let $\varphi=x_{1}$ and $u\in
H^{1}(\widetilde{\Omega})$ be the solution of (1.3). Then there exists
positive constant $C$ depending only on $n$, such that

$\|\nabla u\|_{L^{\infty}(\widetilde{\Omega}\cap
B_{2\sqrt{\varepsilon}})}\geq\frac{1}{C}\varepsilon^{\frac{\alpha-1}{2}},$
(1.13)

where $\alpha$ is given by (1.11).

######  Remark 1.4.

Estimate (1.13) holds for all $C^{2}$ domains $\Omega$ and $C^{4}$ relatively
strictly convex open sets $D_{1},D_{2}$ that are axially symmetric with
respect to $x_{n}$-axis. A modification of the proof of the theorem yields the
result.

Let us give a brief description of the proof of Theorem 1.3. Consider

$\bar{u}(x^{\prime})=\fint_{-\varepsilon/2+g(x^{\prime})<x_{n}<\varepsilon/2+f(x^{\prime})}u(x^{\prime},x_{n})\,dx_{n},\quad|x^{\prime}|<1,$

where $f(x^{\prime})=-\sqrt{1-|x^{\prime}|^{2}}+1$ and
$g(x^{\prime})=\sqrt{1-|x^{\prime}|^{2}}-1$. In the polar coordinates,
$\bar{u}(x^{\prime})=\bar{u}(r,\xi)$, where $x^{\prime}=(r,\xi)$, $0<r<1$, and
$\xi\in\mathbb{S}^{n-2}$. Since the boundary value $\varphi$ depends only on
$x_{1}$ and is odd in $x_{1}$, the projection of $\bar{u}(r,\cdot)$ to the
span of the spherical harmonics is $U_{1,1}(r)Y_{1,1}(\xi)$, where $Y_{1,1}$
is $\left.x_{1}\right|_{\mathbb{S}^{n-2}}$ modulo a harmless positive
normalization constant,

$U_{1,1}(r)=\fint_{-\varepsilon/2+g(x^{\prime})<x_{n}<\varepsilon/2+f(x^{\prime})}\hat{u}(r,x_{n})\,dx_{n},$

and

$\hat{u}(r,x_{n})=\int_{\mathbb{S}^{n-2}}u(r,\xi,x_{n})Y_{1,1}(\xi)\,d\xi.$

We analyze the equations satisfied by $U_{1,1}(r)$ and $\hat{u}(r,x_{n})$ and
establish a lower bound

$U_{1,1}(r)\geq\frac{1}{C}r^{\beta}(\varepsilon+r^{2})^{\frac{\alpha-\beta}{2}},\quad
0<r<1,$

where $\beta=\frac{2\alpha^{2}+\alpha(n-1)}{n-3+\alpha}$ and $C$ is a positive
constant independent of $\varepsilon$. It follows that

$\|\bar{u}(\sqrt{\varepsilon},\cdot)\|_{L^{2}(\mathbb{S}^{n-2})}\geq|U_{1,1}(\sqrt{\varepsilon})|\geq\frac{1}{C}\varepsilon^{\alpha/2},$

and, consequently, there exists $\xi_{0}\in\mathbb{S}^{n-2}$,
$x_{n}\in(-\varepsilon/2+g(x^{\prime}),\varepsilon/2+f(x^{\prime}))$ such that

$|u(\sqrt{\varepsilon},\xi_{0},x_{n})|\geq\frac{1}{C}\varepsilon^{\alpha/2}.$

Estimate (1.13) follows since $u(0)=0$ by the oddness of $u$ in $x_{1}$.

Theorems 1.1 and 1.3 will be proved in Sections 2 and 3, respectively.

##  2\. Proof of Theorem 1.1

In this section, we prove Theorem 1.1. Without loss of generality, we may
assume $a=1$. Namely, we consider

$f(x^{\prime})-g(x^{\prime})=|x^{\prime}|^{2}+O(|x^{\prime}|^{2+\gamma})\quad\mbox{for}~{}~{}0<|x^{\prime}|<R_{0}.$

We perform a change of variables by setting

$\left\\{\begin{aligned} y^{\prime}&=x^{\prime},\\\
y_{n}&=2\varepsilon\left(\frac{x_{n}-g(x^{\prime})+\varepsilon/2}{\varepsilon+f(x^{\prime})-g(x^{\prime})}-\frac{1}{2}\right),\end{aligned}\right.\quad\forall(x^{\prime},x_{n})\in\Omega_{R_{0}}.$
(2.1)

This change of variables maps the domain $\Omega_{R_{0}}$ to a cylinder of
height $\varepsilon$, denoted by $Q_{R_{0},\varepsilon}$, where

$Q_{s,t}:=\\{y=(y^{\prime},y_{n})\in\mathbb{R}^{n}~{}\big{|}~{}|y^{\prime}|<s,|y_{n}|<t\\}$

for $s,t>0$. Moreover,
$\det(\partial_{x}y)=2\varepsilon(\varepsilon+f(x^{\prime})-g(x^{\prime}))^{-1}$.
Let $u(x)\in H^{1}(\Omega_{R_{0}})$ be a solution of (1.8) and let
$v(y)=u(x)$. Then $v$ satisfies

$\left\\{\begin{aligned}
-\partial_{i}(a^{ij}(y)\partial_{j}v(y))&=0\quad\mbox{in
}Q_{R_{0},\varepsilon},\\\ a^{nj}(y)\partial_{j}v(y)&=0\quad\mbox{on
}\\{y_{n}=-\varepsilon\\}\cup\\{y_{n}=\varepsilon\\},\end{aligned}\right.$
(2.2)

with $\|v\|_{L^{\infty}(Q_{R_{0},\varepsilon})}\leq 1$, where the coefficient
matrix $(a^{ij}(y))$ is given by

$\displaystyle(a^{ij}(y))=\frac{2\varepsilon(\partial_{x}y)(\partial_{x}y)^{t}}{\det(\partial_{x}y)}$
$\displaystyle=\begin{pmatrix}\varepsilon+|y^{\prime}|^{2}&0&\cdots&0&a^{1n}\\\
0&\varepsilon+|y^{\prime}|^{2}&\cdots&0&a^{2n}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&\cdots&\varepsilon+|y^{\prime}|^{2}&a^{n-1,n}\\\
a^{n1}&a^{n2}&\cdots&a^{n,n-1}&\frac{4\varepsilon^{2}+\sum_{i=1}^{n-1}|a^{in}|^{2}}{\varepsilon+|y^{\prime}|^{2}}\end{pmatrix}+\begin{pmatrix}e^{1}&0&\cdots&0\\\
0&e^{2}&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\
0&0&\cdots&e^{n}\end{pmatrix},$ (2.3)

and

$a^{ni}=a^{in}=-2\varepsilon\partial_{i}g(y^{\prime})-(y_{n}+\varepsilon)\partial_{i}(f(y^{\prime})-g(y^{\prime}))$

for $i=1,\ldots,n-1$. By (1.4), we know that for $i=1,\ldots,n-1$,

$|a^{ni}(y)|=|a^{in}(y)|\leq
C\varepsilon|y^{\prime}|,\quad|e^{i}(y^{\prime})|\leq
C|y^{\prime}|^{2+\gamma},\quad\mbox{and}\quad|e^{n}(y)|\leq\frac{C\varepsilon^{2}|y^{\prime}|^{\gamma}}{\varepsilon+|y^{\prime}|^{2}}.$
(2.4)

Note that $e^{1},\ldots,e^{n-1}$ depend only on $y^{\prime}$ and are
independent of $y_{n}$. We define

$\bar{v}(y^{\prime}):=\fint_{-\varepsilon}^{\varepsilon}v(y^{\prime},y_{n})\,dy_{n}.$
(2.5)

Then $\bar{v}$ satisfies

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla\bar{v})=-\sum_{i=1}^{n-1}\partial_{i}(\overline{a^{in}\partial_{n}v})-\sum_{i=1}^{n-1}\partial_{i}(e^{i}\partial_{i}\bar{v})\quad\text{in}\,\,B_{R_{0}}\subset\mathbb{R}^{n-1},$
(2.6)

with $\|\bar{v}\|_{L^{\infty}(B_{R_{0}})}\leq 1$, where
$\overline{a^{in}\partial_{n}v}$ is the average of $a^{in}\partial_{n}v$ with
respect to $y_{n}$ in $(-\varepsilon,\varepsilon)$. Since $\frac{\partial
u}{\partial\nu}=0$ on $\Gamma_{+}$ and $\Gamma_{-}$, we have, by (1.4) and
(1.9) that

$|\partial_{n}u(x)|\leq C\left|\sum_{i=1}^{n-1}x_{i}\partial_{i}u\right|\leq
C,\quad\forall x\in\Gamma_{+}\cup\Gamma_{-}.$

By the harmonicity of $\partial_{n}u$, the estimate (1.7), and the maximum
principle,

$|\partial_{n}u|\leq C\quad\mbox{in}~{}~{}\Omega_{R_{0}},$ (2.7)

and consequently,

$|\partial_{n}v|\leq
C(\varepsilon+|y^{\prime}|^{2})/\varepsilon\quad\mbox{in}~{}~{}Q_{R_{0},\varepsilon}.$
(2.8)

Therefore, the equation (2.6) can be rewritten as

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla\bar{v})=\sum_{i=1}^{n-1}\partial_{i}F_{i}\quad\text{in}\,\,B_{R_{0}}\subset\mathbb{R}^{n-1},$
(2.9)

where $F_{i}:=-\overline{a^{in}\partial_{n}v}-e^{i}\partial_{i}\bar{v}$
satisfies, using (1.9) and (2.4),

$|F_{i}|\leq
C\left(|y^{\prime}|(\varepsilon+|y^{\prime}|^{2})+|y^{\prime}|^{2+\gamma}(\varepsilon+|y^{\prime}|^{2})^{-1/2}\right).$

For $\gamma,s\in\mathbb{R}$, we introduce the following norm

$\|F\|_{\varepsilon,\gamma,s,B_{R_{0}}}:=\sup_{y^{\prime}\in
B_{R_{0}}}\frac{|F(y^{\prime})|}{|y^{\prime}|^{\gamma}(\varepsilon+|y^{\prime}|^{2})^{1-s}}.$

######  Proposition 2.1.

For $n\geq 3$, $s\geq 0$, $1+\gamma-2s>0$, $1+\gamma-2s\neq\alpha$,
$\varepsilon>0$, and $R_{0}>0$, let $\bar{v}\in H^{1}(B_{R_{0}})$ be a
solution of

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla\bar{v})=\operatorname{div}F+G\quad\text{in}\,\,B_{R_{0}}\subset\mathbb{R}^{n-1},$

where $F,G\in L^{\infty}(B_{R_{0}})$ satisfy

$\|F\|_{\varepsilon,\gamma,s,B_{R_{0}}}<\infty,\quad\|G\|_{\varepsilon,\gamma-1,s,B_{R_{0}}}<\infty.$
(2.10)

Then for any $R\in(0,R_{0}/2)$, we have

$\Big{(}\fint_{\partial
B_{R}}|\bar{v}-\bar{v}(0)|^{2}\,d\sigma\Big{)}^{1/2}\leq
C(\|F\|_{\varepsilon,\gamma,s,B_{R_{0}}}+\|G\|_{\varepsilon,\gamma-1,s,B_{R_{0}}}+\|\bar{v}-\bar{v}(0)\|_{L^{2}(\partial
B_{R_{0}})})R^{\tilde{\alpha}},$ (2.11)

where $\tilde{\alpha}:=\min\\{\alpha,1+\gamma-2s\\}$, $\alpha$ is given in
(1.11), and $C$ is some positive constant depending only on $n$, $\gamma$,
$s$, and $R_{0}$, and is independent of $\varepsilon$.

For the proof, we use an iteration argument based on the following two lemmas.

######  Lemma 2.2.

For $n\geq 3$, $\varepsilon>0$, and $R_{0}>0$, let $v_{1}\in H^{1}(B_{R_{0}})$
satisfy

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla
v_{1})=0\quad\text{in}\,\,B_{R_{0}}\subset\mathbb{R}^{n-1}.$ (2.12)

Then for any $0<\rho<R\leq R_{0}$, we have

$\left(\fint_{\partial
B_{\rho}}|v_{1}(y^{\prime})-v_{1}(0)|^{2}\,d\sigma\right)^{\frac{1}{2}}\leq\left(\frac{\rho}{R}\right)^{\alpha}\left(\fint_{\partial
B_{R}}|v_{1}(y^{\prime})-v_{1}(0)|^{2}\,d\sigma\right)^{\frac{1}{2}},$

where $\alpha$ is given in (1.11).

###### Proof.

By the elliptic theory, $v_{1}\in C^{\infty}(B_{R_{0}})$. Without loss of
generality, we assume that $v_{1}(0)=0$. By scaling, it suffices to prove the
lemma for $R=1$. Denote $y^{\prime}=(r,\xi)\in(0,1)\times\mathbb{S}^{n-2}$. We
can rewrite (2.12) as

$\partial_{rr}v_{1}+\left(\frac{n-2}{r}+\frac{2r}{\varepsilon+r^{2}}\right)\partial_{r}v_{1}+\frac{1}{r^{2}}\Delta_{\mathbb{S}^{n-2}}v_{1}=0\quad\mbox{in}~{}~{}B_{1}\setminus\\{0\\}.$

Take the decomposition

$v_{1}(y^{\prime})=\sum_{k=1}^{\infty}\sum_{i=1}^{N(k)}V_{k,i}(r)Y_{k,i}(\xi),\quad
y^{\prime}\in B_{1}\setminus\\{0\\},$ (2.13)

where $Y_{k,i}$ is a $k$-th degree spherical harmonics, that is,

$-\Delta_{\mathbb{S}^{n-2}}Y_{k,i}=k(k+n-3)Y_{k,i}$

and $\\{Y_{k,i}\\}_{k,i}$ forms an orthonormal basis of
$L^{2}(\mathbb{S}^{n-2})$. Here we used the fact that $V_{0,1}=0$ because
$v_{1}(0)=0$. Then $V_{k,i}(r)\in C^{2}(0,1)$ is given by

$V_{k,i}(r)=\int_{\mathbb{S}^{n-2}}v_{1}(y^{\prime})Y_{k,i}(\xi)\,d\xi,$

and satisfies

$L_{k}V_{k,i}:=V_{k,i}^{\prime\prime}(r)+\left(\frac{n-2}{r}+\frac{2r}{\varepsilon+r^{2}}\right)V_{k,i}^{\prime}(r)-\frac{k(k+n-3)}{r^{2}}V_{k,i}(r)=0\quad\mbox{in}~{}~{}(0,1)$

for each $k\in\mathbb{N}$, $i=1,2,\ldots,N(k)$. For any $k\in\mathbb{N}$, let

$\alpha_{k}:=\frac{-(n-1)+\sqrt{(n-1)^{2}+4k(k+n-3)}}{2}.$

For any $c\in\mathbb{R}$, we have, by a direct computation,

$\displaystyle
L_{k}r^{c}=r^{c-2}\Big{(}c^{2}+(n-3+2r^{2}/(\varepsilon+r^{2}))c-k(k+n-3)\Big{)}\quad\mbox{in}~{}~{}(0,1).$

Thus for $c>0$ sufficiently small, we have

$L_{k}r^{-c}\leq 0\quad\mbox{and}\quad L_{k}r^{\alpha_{k}}\leq
0\quad\mbox{in}~{}~{}(0,1).$

Therefore, for any $\gamma>0$,

$L_{k}(\pm V_{k,i}(r)-\gamma r^{-c}-|V_{k,i}(1)|r^{\alpha_{k}})\geq
0\quad\mbox{in}~{}~{}(0,1).$

Since $v_{1}\in L^{\infty}(B_{1})$, we know that $V_{k,i}(r)$ is bounded in
$(0,1)$, so we have

$\pm V_{k,i}(r)-\gamma
r^{-c}-|V_{k,i}(1)|r^{\alpha_{k}}<0\quad\mbox{as}~{}~{}r\searrow 0.$

Clearly,

$\pm V_{k,i}(r)-\gamma
r^{-c}-|V_{k,i}(1)|r^{\alpha_{k}}<0\quad\mbox{when}~{}~{}r=1.$

By the maximum principle,

$|V_{k,i}(r)|\leq\gamma
r^{-c}+r^{\alpha_{k}}|V_{k,i}(1)|\quad\mbox{for}~{}~{}0<r<1.$

Sending $\gamma\to 0$, we have

$|V_{k,i}(r)|\leq r^{\alpha_{k}}|V_{k,i}(1)|\quad\mbox{for}~{}~{}0<r<1.$
(2.14)

It follows from (2.13) and (2.14),

$\displaystyle\fint_{\partial B_{\rho}}|v_{1}(y^{\prime})|^{2}\,d\sigma$
$\displaystyle=\sum_{k=1}^{\infty}\sum_{i=1}^{N(k)}|V_{k,i}(\rho)|^{2}$
$\displaystyle\leq\rho^{2\alpha}\sum_{k=1}^{\infty}\sum_{i=1}^{N(k)}|V_{k,i}(1)|^{2}\,=\rho^{2\alpha}\fint_{\partial
B_{1}}|v_{1}(y^{\prime})|^{2}\,d\sigma.$

∎

######  Lemma 2.3.

For $n\geq 3$, $s\geq 0$, $1+\gamma-2s>0$, and $\varepsilon>0$, suppose that
$F,G\in L^{\infty}(B_{1})$ satisfy (2.10) with $R_{0}=1$, and $v_{2}\in
H^{1}_{0}(B_{1})$ satisfies

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla
v_{2})=\operatorname{div}F+G\quad\text{in}\,\,B_{1}\subset\mathbb{R}^{n-1}.$
(2.15)

Then we have

$\|v_{2}\|_{L_{\infty}(B_{1})}\leq
C(\|F\|_{\varepsilon,\gamma,s,B_{1}}+\|G\|_{\varepsilon,\gamma-1,s,B_{1}}),$

where $C>0$ depends only on $n$, $\gamma$, and $s$, and is in particular
independent of $\varepsilon$.

###### Proof.

Without loss of generality, we assume
$\|F\|_{\varepsilon,\gamma,s,B_{1}}+\|G\|_{\varepsilon,\gamma-1,s,B_{1}}=1$.
Denote $r=|y^{\prime}|$. We can rewrite (2.15) as

$\Delta
v_{2}+\frac{2r}{\varepsilon+r^{2}}\partial_{r}v_{2}=\partial_{i}(F_{i}(\varepsilon+r^{2})^{-1})+2F_{i}y_{i}(\varepsilon+r^{2})^{-2}+G(\varepsilon+r^{2})^{-1}\quad\text{in}\,\,B_{1}.$
(2.16)

We use Moser’s iteration argument. By the definitions,

$\displaystyle|F_{i}(\varepsilon+r^{2})^{-1}|$ $\displaystyle\leq
r^{\gamma-2s}\|F\|_{\varepsilon,\gamma,s,B_{1}},$
$\displaystyle|F_{i}y_{i}(\varepsilon+r^{2})^{-2}|$ $\displaystyle\leq
r^{\gamma-2s-1}\|F\|_{\varepsilon,\gamma,s,B_{1}},$
$\displaystyle|G(\varepsilon+r^{2})^{-1}|$ $\displaystyle\leq
r^{\gamma-2s-1}\|G\|_{\varepsilon,\gamma-1,s,B_{1}}.$

For $p\geq 2$, we multiply the equation (2.16) with $-|v_{2}|^{p-2}v_{2}$ and
integrate by parts to obtain

$\displaystyle(p-1)\int_{B_{1}}|\nabla
v_{2}|^{2}|v_{2}|^{p-2}\,dy^{\prime}-\int_{B_{1}}\frac{2r}{\varepsilon+r^{2}}\partial_{r}v_{2}(|v_{2}|^{p-2}v_{2})\,dy^{\prime}$
$\displaystyle\leq C(p-1)\int_{B_{1}}|\nabla
v_{2}||v_{2}|^{p-2}r^{\gamma-2s}\,dy^{\prime}+C\int_{B_{1}}|v_{2}|^{p-1}r^{\gamma-2s-1}.$

The second term on the left-hand side is equal to

$\displaystyle-\frac{1}{p}\int_{\mathbb{S}^{n-2}}\int_{0}^{1}\frac{2r^{n-1}}{\varepsilon+r^{2}}\partial_{r}|v_{2}|^{p}\,drd\theta=\frac{1}{p}\int_{\mathbb{S}^{n-2}}\int_{0}^{1}\partial_{r}\Big{(}\frac{2r^{n-1}}{\varepsilon+r^{2}}\Big{)}|v_{2}|^{p}\,drd\theta\geq
0.$

Therefore, by Hölder’s inequality and using $1+\gamma-2s>0$,

$\displaystyle(p-1)\int_{B_{1}}|\nabla v_{2}|^{2}|v_{2}|^{p-2}\,dy^{\prime}$
$\displaystyle\leq C(p-1)\||\nabla
v_{2}||v_{2}|^{\frac{p-2}{2}}\|_{L^{2}(B_{1})}\|v_{2}^{p-2}\|_{L^{\frac{n-1+2\delta}{n-3+2\delta}}(B_{1})}^{1/2}\|r^{2(\gamma-2s)}\|_{L^{\frac{n-1}{2}+\delta}(B_{1})}^{1/2}$
$\displaystyle\quad+C\|v_{2}^{p-1}\|_{L^{\frac{n-1+2\delta}{n-3+2\delta}}(B_{1})}\|r^{\gamma-2s-1}\|_{L^{\frac{n-1}{2}+\delta}(B_{1})},$

where $\delta>0$ is chosen sufficiently small so that

$\|r^{2(\gamma-2s)}\|_{L^{\frac{n-1}{2}+\delta}(B_{1})}+\|r^{\gamma-2s-1}\|_{L^{\frac{n-1}{2}+\delta}(B_{1})}<\infty.$

By Young’s inequality,

$\displaystyle\frac{p-1}{2}\int_{B_{1}}|\nabla
v_{2}|^{2}|v_{2}|^{p-2}\,dy^{\prime}$ $\displaystyle\leq
C(p-1)\|v_{2}^{p-2}\|_{L^{\frac{n-1+2\delta}{n-3+2\delta}}(B_{1})}\|r^{2(\gamma-2s)}\|_{L^{\frac{n-1}{2}+\delta}(B_{1})}$
$\displaystyle\quad+C\|v_{2}^{p-1}\|_{L^{\frac{n-1+2\delta}{n-3+2\delta}}(B_{1})}\|r^{\gamma-2s-1}\|_{L^{\frac{n-1}{2}+\delta}(B_{1})}.$
(2.17)

Taking $p=2$ in the above, we have, by Hölder’s inequality,

$\displaystyle\int_{B_{1}}|\nabla v_{2}|^{2}dy^{\prime}$ $\displaystyle\leq
C+C\|v_{2}\|_{L^{\frac{n-1+2\delta}{n-3+2\delta}}(B_{1})}\leq
C+C\|v_{2}\|_{L^{\frac{2(n-1+2\delta)}{n-3+2\delta}}(B_{1})}.$

Applying the Sobolev-Poincaré inequality on the left-hand side, we have

$\|v_{2}\|_{L^{\frac{2(n-1+2\delta)}{n-3+2\delta}}(B_{1})}\leq C.$ (2.18)

From (2.17), by Hölder’s inequality,

$\displaystyle\frac{4(p-1)}{p^{2}}\int_{B_{1}}\left|\nabla|v_{2}|^{\frac{p}{2}}\right|^{2}\,dy^{\prime}$
$\displaystyle=(p-1)\int_{B_{1}}|\nabla v_{2}|^{2}|v_{2}|^{p-2}\,dy^{\prime}$
$\displaystyle\leq
Cp\|v_{2}\|^{p-2}_{L^{\frac{(n-1+2\delta)p}{n-3+2\delta}}(B_{1})}+C\|v_{2}\|^{p-1}_{L^{\frac{(n-1+2\delta)p}{n-3+2\delta}}(B_{1})},$

which implies that

$\displaystyle\|\nabla|v_{2}|^{\frac{p}{2}}\|_{L^{2}(B_{1})}^{2/p}\leq\max_{i\in\\{1,2\\}}\left(Cp^{i}\right)^{1/p}\|v_{2}\|^{(p-i)/p}_{L^{\frac{(n-1+2\delta)p}{n-3+2\delta}}(B_{1})}.$

Then by the Sobolev inequality and Young’s inequality, we have

$\displaystyle\|v_{2}\|_{L^{tp}(B_{1})}\leq$
$\displaystyle\max_{i\in\\{1,2\\}}\left(Cp^{i}\right)^{1/p}\left(\frac{p-i}{p}\|v_{2}\|_{L^{\frac{(n-1+2\delta)p}{n-3+2\delta}}(B_{1})}+\frac{i}{p}\right)$
$\displaystyle\leq$
$\displaystyle\left(Cp^{2}\right)^{1/p}\left(\|v_{2}\|_{L^{\frac{(n-1+2\delta)p}{n-3+2\delta}}(B_{1})}+\frac{2}{p}\right)\quad\mbox{when}~{}~{}n=3$

for any $t>\frac{n-1+2\delta}{n-3+2\delta}$ and,

$\|v_{2}\|_{L^{\frac{(n-1)p}{n-3}}(B_{1})}\leq\left(Cp^{2}\right)^{1/p}\left(\|v_{2}\|_{L^{\frac{(n-1+2\delta)p}{n-3+2\delta}}(B_{1})}+\frac{2}{p}\right)\quad\mbox{when}~{}~{}n>3.$

For $k\geq 0$, let

$p_{k}=2\left(t\frac{n-3+2\delta}{(n-1+2\delta)}\right)^{k}\frac{n-1+2\delta}{n-3+2\delta}\quad\mbox{when}~{}~{}n=3,$

and

$p_{k}=2\left(\frac{n-1}{n-3}\frac{n-3+2\delta}{(n-1+2\delta)}\right)^{k}\frac{n-1+2\delta}{n-3+2\delta}\quad\mbox{when}~{}~{}n>3.$

Iterating the relations above, we have, by (2.18),

$\displaystyle\|v_{2}\|_{L^{p_{k}}}$
$\displaystyle\leq\prod_{i=0}^{k-1}\left(Cp_{i}^{2}\right)^{1/p_{i}}\|v_{2}\|_{L^{p_{0}}(B_{1})}+\sum_{i=0}^{k-1}\prod_{j=0}^{k-1-i}\left(Cp_{k-1-j}^{2}\right)^{1/p_{k-1-j}}\frac{2}{p_{i}}$
$\displaystyle\leq
C\|v_{2}\|_{L^{\frac{2(n-1+2\delta)}{n-3+2\delta}}(B_{1})}+C\leq C,$ (2.19)

where $C$ is a positive constant depending on $n$, $\gamma$, and $s$, and is
in particular independent of $k$. The lemma is concluded by taking
$k\to\infty$ in (2). ∎

###### Proof of Proposition 2.1.

Without loss of generality, we assume that $\bar{v}(0)=0$ and

$\|F\|_{\varepsilon,\gamma,s,B_{R_{0}}}+\|G\|_{\varepsilon,\gamma-1,s,B_{R_{0}}}+\|\bar{v}\|_{L^{2}(\partial
B_{R_{0}})}=1.$

Consider

$\omega(\rho):=\Big{(}\fint_{\partial
B_{\rho}}|\bar{v}|^{2}\,d\sigma\Big{)}^{1/2}.$

For $0<\rho\leq R/2\leq R_{0}/2$, we write $\bar{v}=v_{1}+v_{2}$ in $B_{R}$,
where $v_{2}$ satisfies

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla
v_{2})=\operatorname{div}F+G\quad\text{in}\,\,B_{R}$

and $v_{2}=0$ on $\partial B_{R}$. Thus $v_{1}$ satisfies

$\operatorname{div}((\varepsilon+|y^{\prime}|^{2})\nabla
v_{1})=0\quad\text{in}\,\,B_{R},$

and $v_{1}=\bar{v}$ on $\partial B_{R}$. By Lemma 2.2,

$\left(\fint_{\partial
B_{\rho}}|v_{1}(y^{\prime})-v_{1}(0)|^{2}\,d\sigma\right)^{\frac{1}{2}}\leq\left(\frac{\rho}{R}\right)^{\alpha}\left(\fint_{\partial
B_{R}}|v_{1}(y^{\prime})-v_{1}(0)|^{2}\,d\sigma\right)^{\frac{1}{2}}.$ (2.20)

Since $\tilde{v}_{2}(y^{\prime}):=v_{2}(Ry^{\prime})$ satisfies

$\operatorname{div}((R^{-2}\varepsilon+|y^{\prime}|^{2})\nabla\tilde{v}_{2})=\operatorname{div}\tilde{F}+\tilde{G}\quad\text{in}\,\,B_{1},$

where $\tilde{F}(y^{\prime}):=R^{-1}F(Ry^{\prime})$ and
$\tilde{G}(y^{\prime}):=G(Ry^{\prime})$ satisfy

$\displaystyle\|\tilde{F}\|_{R^{-2}\varepsilon,\gamma,s,B_{1}}$
$\displaystyle=R^{1+\gamma-2s}\|F\|_{\varepsilon,\gamma,s,B_{R}},$
$\displaystyle\|\tilde{G}\|_{R^{-2}\varepsilon,\gamma-1,s,B_{1}}$
$\displaystyle=R^{1+\gamma-2s}\|G\|_{\varepsilon,\gamma-1,s,B_{R}},$

we apply Lemma 2.3 to $\tilde{v}_{2}$ with $\varepsilon$ replaced with
$R^{-2}\varepsilon$ to obtain

$\|v_{2}\|_{L_{\infty}(B_{R})}\leq CR^{1+\gamma-2s}.$ (2.21)

Since $\bar{v}(0)=v_{1}(0)+v_{2}(0)=0$, we have $|v_{1}(0)|=|v_{2}(0)|$.
Combining (2.20) and (2.21) yields, using $\bar{v}=v_{1}+v_{2}$, and
$\bar{v}=v_{1}$ on $\partial B_{R}$,

$\displaystyle\omega(\rho)$ $\displaystyle\leq\left(\fint_{\partial
B_{\rho}}|v_{1}(y^{\prime})-v_{1}(0)|^{2}\,d\sigma\right)^{\frac{1}{2}}+\left(\fint_{\partial
B_{\rho}}|v_{2}(y^{\prime})-v_{2}(0)|^{2}\,d\sigma\right)^{\frac{1}{2}}$
$\displaystyle\leq\left(\frac{\rho}{R}\right)^{\alpha}\left(\fint_{\partial
B_{R}}|v_{1}(y^{\prime})|^{2}\,d\sigma\right)^{\frac{1}{2}}+\left(\frac{\rho}{R}\right)^{\alpha}|v_{1}(0)|+2\|v_{2}\|_{L_{\infty}(B_{R})}$
$\displaystyle\leq\left(\frac{\rho}{R}\right)^{\alpha}\omega(R)+CR^{1+\gamma-2s}.$
(2.22)

For a positive integer $k$, we take $\rho=2^{-i-1}R_{0}$ and $R=2^{-i}R_{0}$
in (2) and iterate from $i=0$ to $k-1$. We have, using
$1+\gamma-2s\neq\alpha$,

$\displaystyle\omega(2^{-k}R_{0})$ $\displaystyle\leq
2^{-k\alpha}\omega(R_{0})+C\sum_{i=1}^{k}2^{-(k-i)\alpha}(2^{1-i}R_{0})^{1+\gamma-2s}$
$\displaystyle\leq
2^{-k\alpha}\omega(R_{0})+C2^{-k\alpha}R_{0}^{1+\gamma-2s}\frac{1-2^{k(\alpha-1-\gamma+2s)}}{1-2^{\alpha-1-\gamma+2s}}.$

It follows that

$\omega(2^{-k}R_{0})\leq
2^{-k\tilde{\alpha}}\left(\omega(R_{0})+CR_{0}^{1+\gamma-2s}\right).$

For any $\rho\in(0,R_{0}/2)$, let $k$ be the integer such that
$2^{-k-1}R_{0}<\rho\leq 2^{-k}R_{0}$. Then

$\omega(\rho)\leq C\rho^{\tilde{\alpha}},\quad\forall\rho\in(0,R_{0}/2).$

Therefore, (2.11) is proved. ∎

###### Proof of Theorem 1.1.

Without loss of generality, we assume that $a=1$, $u(0)=0$ and
$\|u\|_{L^{\infty}(\Omega_{R_{0}})}=1$. We make the change of variables (2.1),
and let $v(y)=u(x)$. Then $v$ satisfies (2.2). Let $\bar{v}$ be defined as in
(2.5). By (1.9),

$\|\nabla\bar{v}(y^{\prime})\|_{\varepsilon,0,s_{0}+1,B_{R_{0}}}<\infty,$

where $s_{0}=\frac{1}{2}$. Then $\bar{v}$ satisfies the equation (2.9) with
$F$ satisfying

$\|F\|_{\varepsilon,\gamma-2s_{0},0,B_{R_{0}}}<\infty.$

By (2.8),

$|v(y^{\prime},y_{n})-\bar{v}(y^{\prime})|\leq
2\varepsilon\max_{y_{n}\in(-\varepsilon,\varepsilon)}|\partial_{n}v(y^{\prime},y_{n})|\leq
C(\varepsilon+|y^{\prime}|^{2})\quad\mbox{in}~{}~{}Q_{R_{0},\varepsilon}.$
(2.23)

By decreasing $\gamma$ if necessary, we may assume that
$1+\gamma-2s_{0}=\gamma<\alpha$. By Proposition 2.1 and (2.23), we have

$\displaystyle\fint_{Q_{2\varepsilon^{1/2},\varepsilon}}|v-\bar{v}(0)|^{2}\,dy$
$\displaystyle\leq
C\fint_{Q_{2\varepsilon^{1/2},\varepsilon}}|v-\bar{v}|^{2}\,dy+C\fint_{Q_{2\varepsilon^{1/2},\varepsilon}}|\bar{v}-\bar{v}(0)|^{2}\,dy\leq
C\varepsilon^{\tilde{\alpha}},$

where $\tilde{\alpha}=\min\\{\alpha,1+\gamma-2s_{0}\\}$. Let
$\tilde{a}^{ij}(y)=\varepsilon^{-1}a^{ij}(\varepsilon^{1/2}y)$ and
$\tilde{v}(y)=v(\varepsilon^{1/2}y)-\bar{v}(0)$. Then $\tilde{v}$ satisfies

$\left\\{\begin{aligned}
-\partial_{i}(\tilde{a}^{ij}(y)\partial_{j}\tilde{v}(y))&=0\quad\mbox{in
}Q_{2,\varepsilon^{1/2}},\\\
\tilde{a}^{nj}(y)\partial_{j}\tilde{v}(y)&=0\quad\mbox{on
}\\{y_{n}=-\varepsilon^{1/2}\\}\cup\\{y_{n}=\varepsilon^{1/2}\\}.\end{aligned}\right.$

For any $\mu\in(0,1)$, it is straightforward to verify that

$\frac{I}{C}\leq\tilde{a}\leq
CI\quad\mbox{and}\quad\|\tilde{a}\|_{C^{\mu}(Q_{2,\varepsilon^{1/2}})}\leq C.$

Now we define

$S_{l}:=\left\\{y\in\mathbb{R}^{n}~{}\big{|}~{}|y^{\prime}|<2,~{}(2l-1)\varepsilon^{1/2}<y_{n}<(2l+1)\varepsilon^{1/2}\right\\}$

for any integer $l$, and

$S:=\left\\{y\in\mathbb{R}^{n}~{}\big{|}~{}|y^{\prime}|<2,~{}|y_{n}|<2\right\\}.$

Note that $Q_{2,\varepsilon^{1/2}}=S_{0}$. We take the even extension of
$\tilde{v}$ with respect to $y_{n}=\varepsilon^{1/2}$ and then take the
periodic extension (so that the period is equal to $4\varepsilon^{1/2}$). More
precisely, we define, for any $l\in\mathbb{Z}$, a new function $\hat{v}$ by
setting

$\hat{v}(y):=\tilde{v}\left(y^{\prime},(-1)^{l}\left(y_{n}-2l\varepsilon^{1/2}\right)\right),\quad\forall
y\in S_{l}.$

We also define the corresponding coefficients, for $k=1,2,\ldots,n-1$,

$\hat{a}^{nk}(y)=\hat{a}^{kn}(y):=(-1)^{l}\tilde{a}^{kn}\left(y^{\prime},(-1)^{l}\left(y_{n}-2l\varepsilon^{1/2}\right)\right),\quad\forall
y\in S_{l},$

and for other indices,

$\hat{a}^{ij}(y):=\tilde{a}^{ij}\left(y^{\prime},(-1)^{l}\left(y_{n}-2l\varepsilon^{1/2}\right)\right),\quad\forall
y\in S_{l}.$

Then $\hat{v}$ and $\hat{a}^{ij}$ are defined in the infinite cylinder
$Q_{2,\infty}$. In particular, by using the conormal boundary conditions, it
is easily seen that $\hat{v}$ satisfies the equation

$\partial_{i}(\hat{a}^{ij}\partial_{j}\hat{v})=0\quad\mbox{in}\,\,S.$

By [LN]*Proposition 4.1 and [LY2]*Lemma 2.1,

$\|\nabla\hat{v}\|_{L^{\infty}(\frac{1}{2}S)}\leq C\|\hat{v}\|_{L^{2}(S)}\leq
C\varepsilon^{\frac{\tilde{\alpha}}{2}},$

which implies, after reversing the changes of variables,

$\|\nabla u\|_{L^{\infty}(\Omega_{\varepsilon^{1/2}})}\leq
C\varepsilon^{\frac{\tilde{\alpha}-1}{2}}.$

For any $R\in(\varepsilon^{1/2},R_{0}/4)$, by Proposition 2.1 and (2.23), we
have

$\fint_{Q_{4R,\varepsilon}\setminus
Q_{R/2,\varepsilon}}|v-\bar{v}(0)|^{2}\,dy\leq CR^{2\tilde{\alpha}}.$

This implies

$\fint_{\Omega_{4R}\setminus\Omega_{R/2}}|u-\bar{v}(0)|^{2}\,dx\leq
CR^{2\tilde{\alpha}}.$

We make a change of variables by setting

$\left\\{\begin{aligned} z^{\prime}&=x^{\prime},\\\
z_{n}&=2R^{2}\left(\frac{x_{n}-g(x^{\prime})+\varepsilon/2}{\varepsilon+f(x^{\prime})-g(x^{\prime})}-\frac{1}{2}\right),\end{aligned}\right.\quad\forall(x^{\prime},x_{n})\in\Omega_{4R}\setminus\Omega_{R/2}.$

This change of variables maps the domain $\Omega_{4R}\setminus\Omega_{R/2}$ to
$Q_{4R,R^{2}}\setminus Q_{R/2,R^{2}}$. Let $w(z)=u(x)-\bar{v}(0)$, so that
$w(z)$ satisfies

$\left\\{\begin{aligned}
-\partial_{i}(b^{ij}(z)\partial_{j}w(z))&=0\quad\mbox{in
}Q_{4R,R^{2}}\setminus Q_{R/2,R^{2}},\\\
b^{nj}(z)\partial_{j}w(z)&=0\quad\mbox{on
}\\{z_{n}=-R^{2}\\}\cup\\{z_{n}=R^{2}\\},\end{aligned}\right.$

where

$(b^{ij}(z))=\frac{(\partial_{x}z)(\partial_{x}z)^{t}}{\det(\partial_{x}z)}.$

It is straightforward to verify that

$\frac{I}{C}\leq b(z)\leq
CI\quad\mbox{and}\quad\|b\|_{C^{\mu}(Q_{4R,R^{2}}\setminus Q_{R/2,R^{2}})}\leq
CR^{-\mu}$

for any $\mu>0$. We can apply the “flipping argument” as above to get

$\|\nabla w\|_{L^{\infty}(Q_{2R,R^{2}}\setminus Q_{R,R^{2}})}\leq
CR^{\tilde{\alpha}-1},$

which implies

$\|\nabla u\|_{L^{\infty}(\Omega_{2R}\setminus\Omega_{R})}\leq
CR^{\tilde{\alpha}-1}$

for any $R\in(\varepsilon^{1/2},R_{0}/4)$. Therefore, we have improved the
upper bound $|\nabla u(x)|\leq C(\varepsilon+|x^{\prime}|^{2})^{-s_{0}}$ to
$|\nabla u(x)|\leq
C(\varepsilon+|x^{\prime}|^{2})^{\frac{\tilde{\alpha}-1}{2}}$, where
$\frac{\tilde{\alpha}-1}{2}=\min\left\\{\frac{\alpha-1}{2},-s_{0}+\frac{\gamma}{2}\right\\}$.
If $-s_{0}+\frac{\gamma}{2}<\frac{\alpha-1}{2}$, we take
$s_{1}=s_{0}-\frac{\gamma}{2}$ and repeat the argument above. We may decrease
$\gamma$ if necessary so that $\frac{\alpha-1}{2}\neq-s_{0}+k\frac{\gamma}{2}$
for any $k=1,2,\ldots$. After repeating the argument finite times, we obtain
the estimate (1.10). ∎

##  3\. Optimality

In this section, we prove Theorem 1.3. We will make use of the following
lemma.

######  Lemma 3.1.

For $\varepsilon>0$, there exists a unique solution $h\in
L^{\infty}((0,1))\cap C^{\infty}((0,1])$ of

$Lh:=h^{\prime\prime}(r)+\left(\frac{n-2}{r}+\frac{2r}{\varepsilon+r^{2}}\right)h^{\prime}(r)-\frac{n-2}{r^{2}}h(r)=0,\quad
0<r<1$ (3.1)

satisfying $h(1)=1$. Moreover, $h\in C([0,1])$, $h(0)=0$, and for
$\beta\geq\frac{2\alpha^{2}+\alpha(n-1)}{n-3+\alpha}$, there exist positive
constants $C(\varepsilon)$ and $C(\beta)$ such that

$r<h(r)<\min\\{C(\varepsilon)r,r^{\alpha}\\}~{}\mbox{and}~{}h(r)\geq\frac{1}{C(\beta)}r^{\beta}(\varepsilon+r^{2})^{\frac{\alpha-\beta}{2}}\quad\mbox{for}~{}~{}0<r<1,$
(3.2)

where $\alpha$ is given by (1.11) and $h$ is strictly increasing in $[0,1]$.

###### Proof.

For $0<a<1$, let $h_{a}\in C^{2}([a,1])$ be the solution of $Lh_{a}=0$ in
$(a,1)$ satisfying $h_{a}(a)=a$ and $h_{a}(1)=1$. Since $Lr>0$ and
$Lr^{\alpha}<0$ in $(0,1)$, by the maximum principle and the strong maximum
principle,

$r<h_{a}(r)<r^{\alpha},\quad a<r<1.$

Sending $a\to 0$ along a subsequence, $h_{a}\to h$ in
$C^{2}_{\text{loc}}((0,1])$ for some $h\in C([0,1])\cap C^{\infty}((0,1])$
satisfying $r\leq h(r)\leq r^{\alpha}$, $Lh=0$ in $(0,1)$, and $h(0)=0$. By
the strong maximum principle,

$r<h(r)<r^{\alpha},\quad 0<r<1.$

Let $v=r(1-r^{1/2}/2)$, by a direct computation,

$Lv=-\frac{1}{4}\left(n-\frac{1}{2}\right)r^{-\frac{1}{2}}+\frac{1}{\varepsilon}O(r)\quad\mbox{as}~{}~{}r\to
0.$

Hence $Lv<0$ in $(0,r_{0}(\varepsilon))$, for some small $r_{0}(\varepsilon)$.
By the maximum principle, we have $h\leq C(\varepsilon)v\leq C(\varepsilon)r$
in $(0,r_{0}(\varepsilon))$ for some constant $C(\varepsilon)$.

For $\beta\in\mathbb{R}$, let
$U(r)=r^{\beta}(\varepsilon+r^{2})^{\frac{\alpha-\beta}{2}}$. By a direct
computation,

$\displaystyle LU$
$\displaystyle=r^{\beta-2}(\varepsilon+r^{2})^{\frac{\alpha-\beta}{2}}\left\\{(\beta-\alpha)^{2}\left(\frac{r^{2}}{\varepsilon+r^{2}}\right)^{2}\right.$
$\displaystyle\left.+[(2\beta+n-1)(\alpha-\beta)+2\beta]\left(\frac{r^{2}}{\varepsilon+r^{2}}\right)+(n-2+\beta)(\beta-1)\right\\},\quad
0<r<1.$

Consider the second order polynomial

$p(x):=(\beta-\alpha)^{2}x^{2}+[(2\beta+n-1)(\alpha-\beta)+2\beta]x+(n-2+\beta)(\beta-1),\quad
x\in[0,1].$

Since $p(1)=0$, a sufficient condition for $LU\geq 0$ in $(0,1)$ is

$p^{\prime}(x)=2(\beta-\alpha)^{2}x+(2\beta+n-1)(\alpha-\beta)+2\beta\leq
2(\beta-\alpha)^{2}+(2\beta+n-1)(\alpha-\beta)+2\beta\leq 0.$

This is equivalent to $\beta\geq\frac{2\alpha^{2}+\alpha(n-1)}{n-3+\alpha}$.
Therefore, $U$ is a subsolution of (3.1) when
$\beta\geq\frac{2\alpha^{2}+\alpha(n-1)}{n-3+\alpha}$. Estimate (3.2) follows.

Next we show $h$ is strictly increasing in $(0,1)$. If not, there exists an
$r_{0}\in(0,1)$ such that $h^{\prime}(r_{0})=0$ and
$h^{\prime\prime}(r_{0})\leq 0$. Since $h(r_{0})>0$, we have $Lh(r_{0})<0$, a
contradiction.

Finally, we show the uniqueness of $h$. Let $h_{2}\in L^{\infty}((0,1))\cap
C^{\infty}((0,1])$ be a solution of (3.1) in $(0,1)$ satisfying $h_{2}(1)=1$.
Then $w(r):=h_{2}(r)/h(r)$ satisfies

$(Gw^{\prime})^{\prime}=0,\quad 0<r<1,$

where $G=h^{2}r^{n-2}(\varepsilon+r^{2})$. Therefore, for some constants
$C_{0}$ and $C_{1}$, we have

$h_{2}(r)=h(r)w(r)=h(r)\int_{r}^{1}\frac{C_{0}}{h^{2}(s)s^{n-2}(\varepsilon+s^{2})}\,ds+C_{1}h(r),\quad
0<r<1.$

By the first inequality in (3.2),

$h(r)\int_{r}^{1}\frac{1}{h^{2}(s)s^{n-2}(\varepsilon+s^{2})}\,ds\to+\infty$

as $r\to 0$. Therefore, since $h_{2}$ and $h$ are bounded, $C_{0}=0$,
$C_{1}=1$, and $h_{2}=h$. ∎

###### Proof of Theorem 1.3.

Step 1. By the elliptic theory, the fact that $\widetilde{\Omega}$ is
symmetric in $x_{1}$, and the fact that $\varphi$ is odd in $x_{1}$, we know
that $u$ is smooth and $u$ is odd in $x_{1}$. In
$\\{(x^{\prime},x_{n})\in\mathbb{R}^{n}~{}\big{|}~{}|x^{\prime}|<1\\}$, $f$
and $g$ can be written as

$f(x^{\prime})=\frac{|x^{\prime}|^{2}}{2}+O(|x^{\prime}|^{4})\quad\mbox{and}\quad
g(x^{\prime})=-\frac{|x^{\prime}|^{2}}{2}+O(|x^{\prime}|^{4}),$

respectively. In $\Omega_{1}$, where $\Omega_{r}$ is defined as in (1.6), we
define

$\bar{u}(x^{\prime})=\fint_{-\frac{\varepsilon}{2}+g(x^{\prime})<x_{n}<\frac{\varepsilon}{2}+f(x^{\prime})}u\,dx_{n}.$

Then $\bar{u}$ satisfies

$\operatorname{div}((\varepsilon+|x^{\prime}|^{2})\nabla\bar{u})=\operatorname{div}F,\quad\mbox{in}\,\,B_{1}\subset\mathbb{R}^{n-1},$

where

$F_{i}=-2(x_{i}+O(|x^{\prime}|^{3}))\overline{\partial_{n}ux_{n}}+O(|x^{\prime}|^{4})\partial_{i}\bar{u},$

$\overline{\partial_{n}ux_{n}}$ is the average of $\partial_{n}ux_{n}$ with
respect to $x_{n}$ in
$(-\varepsilon/2+g(x^{\prime}),\varepsilon/2+f(x^{\prime}))$. We have, by
(2.7), $|x_{n}|\leq C(\varepsilon+|x^{\prime}|^{2})$, and by (1.10),

$|F(x^{\prime})|\leq C(n)|x^{\prime}|(\varepsilon+|x^{\prime}|^{2})\quad
x^{\prime}\in B_{1}.$ (3.3)

Again, we denote $Y_{k,i}$ to be a $k$-th degree normalized spherical
harmonics so that $\\{Y_{k,i}\\}_{k,i}$ forms an orthonormal basis of
$L^{2}(\mathbb{S}^{n-2})$, $Y_{1,1}$ to be the one after normalizing
$\left.x_{1}\right|_{\mathbb{S}^{n-2}}$, and $x^{\prime}=(r,\xi)$. Since
$\bar{u}$ is odd with respect to $x_{1}=0$, and in particular $\bar{u}(0)=0$,
we have the following decomposition

$\bar{u}(x^{\prime})=U_{1,1}(r)Y_{1,1}(\xi)+\sum_{k=2}^{\infty}\sum_{i=1}^{N(k)}U_{k,i}(r)Y_{k,i}(\xi),\quad
x^{\prime}\in B_{1}\setminus\\{0\\},$ (3.4)

where $U_{k,i}(r)=\int_{\mathbb{S}^{n-2}}\bar{u}(r,\xi)Y_{k,i}(\xi)\,d\xi$ and
$U_{k,i}\in C([0,1))\cap C^{\infty}((0,1))$. Since $\bar{u}(0)=0$ and
$\varepsilon+|x^{\prime}|^{2}$ is independent of $\xi$, $U_{1,1}$ satisfies
$U_{1,1}(0)=0$ and

$LU_{1,1}:=U_{1,1}^{\prime\prime}(r)+\left(\frac{n-2}{r}+\frac{2r}{\varepsilon+r^{2}}\right)U_{1,1}^{\prime}(r)-\frac{n-2}{r^{2}}U_{1,1}(r)=H(r),\quad
0<r<1,$

where

$\displaystyle H(r)$
$\displaystyle=\int_{\mathbb{S}^{n-2}}\frac{(\operatorname{div}F)Y_{1,1}(\xi)}{\varepsilon+r^{2}}\,d\xi=\int_{\mathbb{S}^{n-2}}\frac{\partial_{r}F_{r}+\frac{1}{r}\nabla_{\xi}F_{\xi}}{\varepsilon+r^{2}}Y_{1,1}(\xi)\,d\xi$
$\displaystyle=\partial_{r}\left(\int_{\mathbb{S}^{n-2}}\frac{F_{r}}{\varepsilon+r^{2}}Y_{1,1}(\xi)\,d\xi\right)+\int_{\mathbb{S}^{n-2}}\frac{2rF_{r}Y_{1,1}}{(\varepsilon+r^{2})^{2}}-\frac{F_{\xi}\nabla_{\xi}Y_{1,1}}{r(\varepsilon+r^{2})}\,d\xi$
$\displaystyle=:A^{\prime}(r)+B(r),\quad 0<r<1,$

and $A(r),B(r)\in C^{1}([0,1))$ satisfy, in view of (3.3), that

$|A(r)|\leq C(n)r,\quad|B(r)|\leq C(n),\quad 0<r<1.$ (3.5)

Step 2. We will prove, for some constant $C_{1}(\varepsilon)$, that

$U_{1,1}(r)=C_{1}(\varepsilon)h(r)+O(r^{1+\alpha}),\quad 0<r<1.$ (3.6)

We use the method of reduction of order to write down a bounded solution $v$
satisfying $Lv=H$ in $(0,1)$, and then give an estimate $v=O(r^{1+\alpha})$.

Let $h\in C([0,1])\cap C^{\infty}((0,1])$ be the solution of $Lh=0$ satisfying
$h(0)=0$ and $h(1)=1$ as in Lemma 3.1. Let $v=hw$ and

$w(r):=\int_{0}^{r}\frac{1}{h^{2}(s)s^{n-2}(\varepsilon+s^{2})}\int_{0}^{s}h(\tau)\tau^{n-2}(\varepsilon+\tau^{2})H(\tau)\,d\tau
ds,\quad 0<r<1.$

By a direct computation,

$Lv=L(hw)=hw^{\prime\prime}+\left[2h^{\prime}+\left(\frac{n-2}{r}+\frac{2r}{\varepsilon+r^{2}}\right)h\right]w^{\prime}=\frac{h}{G}(Gw^{\prime})^{\prime}=H,$

where $G=h^{2}r^{n-2}(\varepsilon+r^{2})$. By (3.5) and the fact that
$h^{\prime}>0$, we can estimate

$\displaystyle\int_{0}^{s}h(\tau)\tau^{n-2}(\varepsilon+\tau^{2})H(\tau)\,d\tau$
$\displaystyle=\int_{0}^{s}h(\tau)\tau^{n-2}(\varepsilon+\tau^{2})A^{\prime}(\tau)\,d\tau+O(1)h(s)s^{n-1}(\varepsilon+s^{2})$
$\displaystyle=-\int_{0}^{s}h^{\prime}\tau^{n-2}(\varepsilon+\tau^{2})A(\tau)\,d\tau+O(1)h(s)s^{n-1}(\varepsilon+s^{2})$
$\displaystyle=O(1)s^{n-1}(\varepsilon+s^{2})\int_{0}^{s}h^{\prime}(\tau)\,d\tau+O(1)h(s)s^{n-1}(\varepsilon+s^{2})$
$\displaystyle=O(1)h(s)s^{n-1}(\varepsilon+s^{2}).$

Therefore, using (3.2),

$|v(r)|\leq Ch(r)\int_{0}^{r}\frac{s}{h(s)}=O(r^{1+\alpha}),\quad 0<r<1.$

Since $U_{1,1}-v$ is bounded and satisfies $L(U_{1,1}-v)=0$ in $(0,1)$, by
Lemma 3.1, $U_{1,1}-v=C_{1}(\varepsilon)h$. Hence (3.6) follows.

Step 3. We will show that $C_{1}(\varepsilon)>\frac{1}{C}$ for some positive
$\varepsilon$-independent constant $C$.

Denote
$x=(r,\xi,x_{n})\in\mathbb{R}_{+}\times\mathbb{S}^{n-2}\times\mathbb{R}$ and
write (1.3) under the condition of Theorem 1.3 as the following:

$\left\\{\begin{aligned}
u_{rr}+\frac{n-2}{r}u_{r}+\frac{1}{r^{2}}\Delta_{\mathbb{S}^{n-2}}u+u_{nn}&=0\quad\mbox{in}~{}~{}B_{5}\setminus\overline{(D_{1}\cup
D_{2})}\\\ \frac{\partial
u}{\partial\nu}&=0\quad\mbox{on}~{}\partial{D}_{i},~{}i=1,2,\\\
u&=x_{1}\quad\mbox{on }\partial B_{5}.\end{aligned}\right.$ (3.7)

Let

$\hat{u}(r,x_{n})=\int_{\mathbb{S}^{n-2}}u(r,\xi,x_{n})Y_{1,1}(\xi)\,d\xi.$

Since $u$ is odd in $x_{1}$, we have $\hat{u}(0,x_{n})=0$ for any $x_{n}$.
Multiplying (3.7) by $Y_{1,1}(\xi)$ and integrating over $\mathbb{S}^{n-2}$,
we know that $\hat{u}(r,x_{n})$ satisfies

$\left\\{\begin{aligned}
\hat{u}_{rr}+\frac{n-2}{r}\hat{u}_{r}-\frac{n-2}{r^{2}}\hat{u}+\hat{u}_{nn}&=0\quad\mbox{in}~{}~{}\widehat{B}_{5}\setminus\overline{(\widehat{D}_{1}\cup\widehat{D}_{2})}\\\
\frac{\partial\hat{u}}{\partial\nu}&=0\quad\mbox{on}~{}\partial{\widehat{D}}_{i},~{}i=1,2,\\\
\hat{u}&=0\quad\mbox{on }\\{r=0\\},\\\ \hat{u}&=r\quad\mbox{on
}\partial\widehat{B}_{5},\end{aligned}\right.$ (3.8)

where

$\displaystyle\widehat{B}_{5}$
$\displaystyle:=\\{(r,x_{n})\in\mathbb{R}_{+}\times\mathbb{R}~{}\big{|}~{}r^{2}+x_{n}^{2}<25\\},$
$\displaystyle\widehat{D}_{i}$
$\displaystyle:=\\{(r,x_{n})\in\mathbb{R}_{+}\times\mathbb{R}~{}\big{|}~{}r^{2}+(x_{n}-(-1)^{i}(1+\varepsilon/2))^{2}<1\\},$

and $\nu$ is the unit inner normal of $\partial\widehat{D}_{i}$. Clearly
$\hat{v}(r)=r$ satisfies the first line of (3.8), and
$\frac{\partial\hat{v}}{\partial\nu}<0$ on $\partial{\widehat{D}}_{i}$,
$i=1,2$. Thus, we know that $r$ is a subsolution of (3.8), and therefore
$\hat{u}\geq r$. Then

$U_{1,1}(r)=\fint_{-\varepsilon/2+g(x^{\prime})<x_{n}<\varepsilon/2+f(x^{\prime})}\hat{u}(r,x_{n})\,dx_{n}\geq
r.$

By (3.6), (3.2), and the above, we have

$r\leq U_{1,1}(r)=C_{1}(\varepsilon)h(r)+O(r^{1+\alpha})\leq
C_{1}(\varepsilon)r^{\alpha}+\frac{1}{2}r,\quad\forall 0<r\leq r_{0},$

where $r_{0}$ is a small constant independent of $\varepsilon$, which implies
that

$C_{1}(\varepsilon)\geq\frac{1}{2}r_{0}^{1-\alpha}.$

Step 4. Completion of the proof of Theorem 1.3.

It follows, in view of (3.6), Step 3, and (3.2), that there exists some
positive constant $r_{0}$ independent of $\varepsilon$ such that

$U_{1,1}(r)\geq\frac{1}{C}h(r)+O(r^{1+\alpha})\geq\frac{1}{2C}h(r),\quad
0<r\leq r_{0}.$ (3.9)

By (3.2),

$h(r)\geq\frac{1}{C}r^{\beta}(\varepsilon+r^{2})^{\frac{\alpha-\beta}{2}}\quad\mbox{for}~{}~{}\beta=\frac{2\alpha^{2}+\alpha(n-1)}{n-3+\alpha}.$
(3.10)

By (3.4), (3.9), and (3.10), we have

$\left(\int_{\mathbb{S}^{n-2}}|\bar{u}(\sqrt{\varepsilon},\xi)|^{2}\,d\xi\right)^{1/2}\geq|U_{1,1}(\sqrt{\varepsilon})|\geq\frac{1}{C}h(\sqrt{\varepsilon})\geq\frac{1}{C}\varepsilon^{\alpha/2}.$

Then, there exists a $\xi_{0}\in\mathbb{S}^{n-2}$ such that
$|\bar{u}(\sqrt{\varepsilon},\xi_{0})|\geq\frac{1}{C}\varepsilon^{\alpha/2}$.
Since $\bar{u}$ is the average of $u$ in the $x_{n}$ direction, there exists
an $x_{n}$ such that

$|u(\sqrt{\varepsilon},\xi_{0},x_{n})|\geq\frac{1}{C}\varepsilon^{\alpha/2}.$
(3.11)

Estimate (1.13) follows from (3.11) and $u(0)=0$. ∎

## References