Introduction
Let G = ( V , E ) G=(V,E) G = ( V , E ) n n n Δ > 1 \Delta>1 Δ > 1 { L i } i ∈ G \{L_i\}_{i\in G} { L i } i ∈ G x ∈ ∏ i L i \mathbf{x}\in\prod_i L_i x ∈ ∏ i L i i ∼ j i\sim j i ∼ j x i ≠ x j x_i\ne x_j x i = x j μ \mu μ μ \mu μ x \mathbf{x} x i i i 1 n P \frac{1}{n}\mathcal{P} n 1 P 1 / n 1/n 1/ n
max x min { t : ∥ 1 x T ( 1 n P ) t − μ ∥ T V ≤ 1 4 } . \max_{\mathbf{x}}\min\left\{t:\left\|\mathbf{1}_{\mathbf{x}}^{\mathsf{T}}\left(\frac{1}{n}\mathcal{P}\right)^t-\mu\right\|_{\mathrm{TV}}\le\frac{1}{4}\right\}. x max min { t : 1 x T ( n 1 P ) t − μ TV ≤ 4 1 } . To bound the mixing time of 1 n P \frac{1}{n}\mathcal{P} n 1 P
Theorem 1.1. If the second largest eigenvalue of 1 n P \frac{1}{n}\mathcal{P} n 1 P 1 − ε 1-\varepsilon 1 − ε 1 n D = I − 1 n P \frac{1}{n}\mathcal{D}=I-\frac{1}{n}\mathcal{P} n 1 D = I − n 1 P ε \varepsilon ε 1 n P \frac{1}{n}\mathcal{P} n 1 P O ( n ⋅ log ( 1 μ min ) / ε ) O\left(n\cdot\log\left(\frac{1}{\mu_{\min}}\right)/\varepsilon\right) O ( n ⋅ log ( μ m i n 1 ) / ε ) μ min = min x μ ( x ) \mu_{\min}=\min_{\mathbf{x}}\mu(\mathbf{x}) μ m i n = min x μ ( x )
Suppose that the size of every list is at least q q q q ≥ Δ + 2 q \ge\Delta+ 2 q ≥ Δ + 2
Conjecture 1.2. For any graph G G G Δ \Delta Δ q ≥ Δ + 2 q \ge\Delta+ 2 q ≥ Δ + 2 n n n
In the early 1990s, Jerrum [19 ] showed that q ≥ 2 Δ + 1 q \ge2\Delta+ 1 q ≥ 2Δ + 1 [25 ] improved this to 11 Δ / 6 11\Delta/6 11Δ/6 ( 11 / 6 − ε ) Δ (11/6-\varepsilon)\Delta ( 11/6 − ε ) Δ
Local to Global Theorems. With the introduction of the spectral independence technique [3 ] a new challenge started: To come up with new local-to-global arguments to analyze Markov chains. It is worth noting that even though classical proof techniques such as the correlation decay or path coupling methods could be translated to spectral independence [3 , 12 , 21 BCC⁺22] it seemed the main strength of the spectral independence machinery stems from the local-to-global technique known as the trickledown theorem [24 ] which was used to count bases of matroids [4 ] .
Towards this goal, analyzing Glauber dynamics for graph coloring was considered as a benchmark. The first improvement over the classical trickledown technique came from the Matrix trickledown theorems [2 , 1 CCC⁺25] which were used to obtain near optimal bounds for edge coloring problems [WZZ24], or to sample from the Sherrington-Kirkpatrick model [1 ] . Later, this was extended to the C C C [22 , 23 ] that itself lead to improved analysis of the multi-state hardcore model or improved analysis of the Hard core model on planar graphs [16 ] . Later on, Göbel, Jenssen, Michelen, Pappik, Perkins and Schiller [GJM⁺26] observed that the matrix trickledown of [CCC⁺25] can be seen as a discrete Bochner inequality. This led to several improvement for various problems [11 BLO26, 10 ] . In this paper, we establish the discrete Bochner inequality over O ( Δ ) O(\Delta) O ( Δ )
Background on Bochner Inequality. The discrete Bochner type inequalities were recently recently used in [GJM⁺26] to re-prove the trickledown theorem of Chen, Chen, Chen, Yin, and Zhang [CCC⁺25]. For background on this technique see [6 Equation 1.16.6, Proposition 4.8.3] and references therein. Bochner-type methods have also been used to establish spectral-gap and mixing-time bounds in a variety of settings, including the Sherrington-Kirkpatrick model [Wan26, BLO26], matroid intersection [10 ] , and several recent works by OpenAI.
Let P i f P_i f P i f f f f L i \mathcal{L}_i L i
P i f ( x ) = E μ [ f ( X 1 , … , X n ) ∣ X j = x j , ∀ j ≠ i ] . P_i f(\mathbf{x}) = \mathbb{E}_{\mu}[f(X_1,\ldots,X_n)\mid X_j = x_j,\forall j \ne i]. P i f ( x ) = E μ [ f ( X 1 , … , X n ) ∣ X j = x j , ∀ j = i ] . Throughout the paper we use bold letters to denote vectors.
Then, we can write P = ∑ i P i P = \sum_i P_i P = ∑ i P i P i P_i P i P P P 1 n P \frac{1}{n}P n 1 P D i = I − P i D_i=I-P_i D i = I − P i D = ∑ i D i D=\sum_i D_i D = ∑ i D i P i , D i P_i,D_i P i , D i f f f P i 2 f = P i f P_i^2f=P_if P i 2 f = P i f
⟨ f , g ⟩ μ = E X ∼ μ [ f ( X ) g ( X ) ] . \langle f,g\rangle_\mu=\mathbb{E}_{X\sim\mu}[f(X)g(X)]. ⟨ f , g ⟩ μ = E X ∼ μ [ f ( X ) g ( X )] . It is not hard to see that P i , D i P_i,D_i P i , D i f , g f,g f , g ⟨ f , P i g ⟩ = ⟨ P i f , g ⟩ \langle f,P_ig\rangle=\langle P_if,g\rangle ⟨ f , P i g ⟩ = ⟨ P i f , g ⟩ D i = I − P i D_i=I-P_i D i = I − P i D i D_i D i
Fact 1.3. If for any function f : Ω → R f:\Omega\to\mathbb{R} f : Ω → R
⟨ D f , D f ⟩ μ ≥ ε ⋅ ⟨ D f , f ⟩ μ = ε ⋅ ∑ i ⟨ D i f , f ⟩ μ , (1) \langle Df,Df\rangle_\mu\geq\varepsilon\cdot\langle Df,f\rangle_\mu=\varepsilon\cdot\sum_i\langle D_if,f\rangle_\mu, \tag*{(1)} ⟨ D f , D f ⟩ μ ≥ ε ⋅ ⟨ D f , f ⟩ μ = ε ⋅ i ∑ ⟨ D i f , f ⟩ μ , (1) then the spectral gap of the Glauber dynamics 1 n P \frac{1}{n}P n 1 P is at least ε / n \varepsilon/n ε / n
Proof. Given an arbitrary function g g g D ⪰ 0 D\succeq0 D ⪰ 0 f = D − 1 / 2 g f=D^{-1/2}g f = D − 1/2 g D D D D D D
⟨ D g , g ⟩ = ⟨ D f , D f ⟩ ≥ ε ⋅ ⟨ D f , f ⟩ = ε ⋅ ⟨ g , g ⟩ , \langle Dg,g\rangle=\langle Df,Df\rangle\geq\varepsilon\cdot\langle Df,f\rangle=\varepsilon\cdot\langle g,g\rangle, ⟨ D g , g ⟩ = ⟨ D f , D f ⟩ ≥ ε ⋅ ⟨ D f , f ⟩ = ε ⋅ ⟨ g , g ⟩ , where all the inner-products are with respect to μ \mu μ
Top Link Spectral Expansion. A natural approach to prove (1) is to lower-bound ⟨ D i f , D j f ⟩ μ \langle D_if,D_jf\rangle_\mu ⟨ D i f , D j f ⟩ μ i , j ∈ G i,j\in G i , j ∈ G [4 ] . See the following lemma and the proof.
Lemma 1.4. Given a graph H H H with vertices 1 and 2. If H H H has no edges then ⟨ D 1 f , D 2 f ⟩ μ ≥ 0 \langle D_1f,D_2f\rangle_\mu\geq0 ⟨ D 1 f , D 2 f ⟩ μ ≥ 0 Otherwise, suppose s ≥ 5 s\geq5 s ≥ 5 and ∣ L 1 ∣ , ∣ L 2 ∣ ≥ s + 1 |L_1|,|L_2|\geq s+1 ∣ L 1 ∣ , ∣ L 2 ∣ ≥ s + 1 Then for every f ∈ L 2 ( μ ) f\in L^2(\mu) f ∈ L 2 ( μ ) we have
2 ⟨ D 1 f , D 2 f ⟩ μ ≥ − 1 s ( ∥ D 1 f ∥ μ 2 + ∥ D 2 f ∥ μ 2 ) . 2\langle D_1f,D_2f\rangle_\mu\geq-\frac{1}{s}\left(\lVert D_1f\rVert_\mu^2+\lVert D_2f\rVert_\mu^2\right). 2 ⟨ D 1 f , D 2 f ⟩ μ ≥ − s 1 ( ∥ D 1 f ∥ μ 2 + ∥ D 2 f ∥ μ 2 ) . Proof. If H H H μ \mu μ D 1 , D 2 D_1,D_2 D 1 , D 2
⟨ D 1 f , D 2 f ⟩ μ = ⟨ f , D 1 D 2 f ⟩ μ = ∥ D 1 D 2 f ∥ μ 2 ≥ 0. \langle D_1f,D_2f\rangle_\mu=\langle f,D_1D_2f\rangle_\mu=\lVert D_1D_2f\rVert_\mu^2\geq0. ⟨ D 1 f , D 2 f ⟩ μ = ⟨ f , D 1 D 2 f ⟩ μ = ∥ D 1 D 2 f ∥ μ 2 ≥ 0. Now suppose H H H P P P { 1 } × L 1 \{1\}\times L_1 { 1 } × L 1 { 2 } × L 2 \{2\}\times L_2 { 2 } × L 2 ( 1 , a ) (1,a) ( 1 , a ) ( 2 , b ) (2,b) ( 2 , b ) a ≠ b a\ne b a = b [11 Eq. (4)] ,
2 ⟨ D 1 f , D 2 f ⟩ μ ≥ − λ 2 ( P ) ( ∥ D 1 f ∥ μ 2 + ∥ D 2 f ∥ μ 2 ) , 2\langle D_1f,D_2f\rangle_\mu\geq-\lambda_2(P)\left(\lVert D_1f\rVert_\mu^2+\lVert D_2f\rVert_\mu^2\right), 2 ⟨ D 1 f , D 2 f ⟩ μ ≥ − λ 2 ( P ) ( ∥ D 1 f ∥ μ 2 + ∥ D 2 f ∥ μ 2 ) , where λ 2 ( P ) \lambda_2(P) λ 2 ( P ) [2 proof of Proposition IV.4] that λ 2 ( P ) ≤ 1 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ≤ 1 / s \lambda_2(P)\leq\frac{1}{\sqrt{(\ell_1-1)(\ell_2-1)}}\leq1/s λ 2 ( P ) ≤ ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 ≤ 1/ s
Having this, we can obtain that the Glauber dynamics has a spectral gap at least 1 / Δ n 1/\Delta n 1/Δ n q > 2 Δ + 2 q>2\Delta+2 q > 2Δ + 2
⟨ D f , D f ⟩ ≥ ∑ i ⟨ D i f , f ⟩ μ + ∑ { i , j } ∈ E ( G ) 2 ⟨ D i f , D j f ⟩ μ ≥ ∑ i ( 1 − deg ( i ) q − Δ ) ⋅ ⟨ D i f , f ⟩ μ ≥ 1 Δ ⟨ D f , f ⟩ μ . \langle Df,Df\rangle\geq\sum_i\langle D_if,f\rangle_\mu+\sum_{\{i,j\}\in E(G)}2\langle D_if,D_jf\rangle_\mu\geq\sum_i\left(1-\frac{\deg(i)}{q-\Delta}\right)\cdot\langle D_if,f\rangle_\mu\geq\frac{1}{\Delta}\langle Df,f\rangle_\mu. ⟨ D f , D f ⟩ ≥ i ∑ ⟨ D i f , f ⟩ μ + { i , j } ∈ E ( G ) ∑ 2 ⟨ D i f , D j f ⟩ μ ≥ i ∑ ( 1 − q − Δ deg ( i ) ) ⋅ ⟨ D i f , f ⟩ μ ≥ Δ 1 ⟨ D f , f ⟩ μ . Main Contribution
The first idea to improve over the q > 2 Δ q > 2\Delta q > 2Δ ⟨ D i ‾ f , D j ‾ f ⟩ μ \langle\overline{D_i}f,\overline{D_j}f\rangle_\mu ⟨ D i f , D j f ⟩ μ i , j i,j i , j i , j i,j i , j i i i j j j Lemma 1.4 , the second eigenvalue of the simple random walk on this graph is ≤ 1 / s \le1/s ≤ 1/ s 1 / s 1/s 1/ s [2 Proposition IV.4] )
⟨ D i ‾ f , D j ‾ f ⟩ ≥ E x ∼ μ ∑ c ∈ L i ∩ L j ( f ( x ) − f ( x i → c ) ) ( f ( x ) − f ( x j → c ) ) . \langle\overline{D_i}f,\overline{D_j}f\rangle\ge\mathbb{E}_{\mathbf{x}\sim\mu}\sum_{c\in L_i\cap L_j}(f(\mathbf{x})-f(\mathbf{x}^{i\to c}))(f(\mathbf{x})-f(\mathbf{x}^{j\to c})). ⟨ D i f , D j f ⟩ ≥ E x ∼ μ c ∈ L i ∩ L j ∑ ( f ( x ) − f ( x i → c )) ( f ( x ) − f ( x j → c )) . In the above D i ‾ \overline{D_i} D i x i → c \mathbf{x}^{i\to c} x i → c i i i c c c ∇ i f \nabla_i f ∇ i f ∇ i f ( x ) c = f ( x ) − f ( x i → c ) \nabla_i f(\mathbf{x})_c=f(\mathbf{x})-f(\mathbf{x}^{i\to c}) ∇ i f ( x ) c = f ( x ) − f ( x i → c ) j j j 1 / s 1/s 1/ s ⟨ D i ‾ f , D j ‾ f ⟩ ≥ ⟨ ∇ i f , ∇ j f ⟩ \langle\overline{D_i}f,\overline{D_j}f\rangle\ge\langle\nabla_i f,\nabla_j f\rangle ⟨ D i f , D j f ⟩ ≥ ⟨ ∇ i f , ∇ j f ⟩
Theorem 1.5. If for every vertex i i i ∣ L i ∣ ≥ s + deg ( i ) |L_i| \ge s+\deg(i) ∣ L i ∣ ≥ s + deg ( i ) s > 2 ∣ λ min ( A G ) ∣ s>2|\lambda_{\min}(A_G)| s > 2∣ λ m i n ( A G ) ∣ Δ \Delta Δ O ( n 2 ) O(n^2) O ( n 2 )
Throughout the article, instead of lower-bounding q − Δ q-\Delta q − Δ s s s G G G λ min ( A G ) ≥ − 2 \lambda_{\min}(A_G)\ge-2 λ m i n ( A G ) ≥ − 2 s > 4 s>4 s > 4
The above theorem can be seen as analogous to the work of [CCC+25] who showed that the Glauber dynamics mixes rapidly for the hardcore model as long as the activity threshold is < 1 ∣ λ min ( A G ) ∣ − 1 <\frac{1}{|\lambda_{\min}(A_G)|-1} < ∣ λ m i n ( A G ) ∣ − 1 1 ≈ e Δ \approx\frac{e}{\Delta} ≈ Δ e Δ \Delta Δ [14 ] ). This may seem very surprising and possibly contradictory with Conjecture 1.2 . The main observation is that if G G G Theorem 1.5 fails as bad eigenvectors of links of co-dimension 2 “match up” (as the graph has no odd cycles). So, the main way to make progress is to avoid doing a worst case analysis for links of co-dimension 2 which only assumes every vertex has s s s s s s
In other words, the observation is that in graphs close to bipartite one typically expects many more than s s s ≳ Δ \gtrsim\Delta ≳ Δ C C C
Instead, we analyzed such links using the new Bochner inequality and by using AI. We say a graph H H H G G G v v v v v v H H H H = { v } ∪ H ′ H=\{v\}\cup H' H = { v } ∪ H ′ H ′ H' H ′ leaves . To extend Theorem 1.5 first we analyzed cones which are “stars”, i.e., the induced graph on H ′ H' H ′ G G G [18 ] . The main advantage of studying a star is that in a typical proper coloring we expect many of the leaves to share colors and that leaves significantly more than s s s Lemma 1.4 above).
Then, we analyze the more general case of a cone. Roughly speaking, it seems we should “lose” now at the center because, e.g., if H ′ H' H ′ s s s Lemma 1.4 to win. Putting these together, for any cone and any function f f f
Theorem 1.6 (Main Technical Theorem). For any t > 0 t>0 t > 0 H = { v } ∪ H ′ H=\{v\}\cup H' H = { v } ∪ H ′ v v v H ′ H' H ′ ∣ H ′ ∣ = d |H'|=d ∣ H ′ ∣ = d s ≥ 5 s\ge5 s ≥ 5 ∣ L i ∣ ≥ s + deg H ( i ) |\mathcal{L}_i|\ge s+\deg_H(i) ∣ L i ∣ ≥ s + deg H ( i ) i ∈ H i\in H i ∈ H
2 ⟨ D v f , D H ′ f ⟩ μ + t ∥ D v f ∥ μ 2 + β d t ( s − 1 ) ∥ D H ′ f ∥ μ 2 + O ( Δ t s 3 ) ⟨ f , D H ′ f ⟩ μ ≥ 0. 2\langle D_vf,D_{H'}f\rangle_\mu+t\|D_vf\|_\mu^2+\frac{\beta_d}{t(s-1)}\|D_{H'}f\|_\mu^2+O\left(\frac{\Delta}{ts^3}\right)\langle f,D_{H'}f\rangle_\mu\ge0. 2 ⟨ D v f , D H ′ f ⟩ μ + t ∥ D v f ∥ μ 2 + t ( s − 1 ) β d ∥ D H ′ f ∥ μ 2 + O ( t s 3 Δ ) ⟨ f , D H ′ f ⟩ μ ≥ 0. where D H ′ = ∑ i ∈ H ′ D i D_{H'}=\sum_{i\in H'}D_i D H ′ = ∑ i ∈ H ′ D i β d = 1 − ( s − 1 s ) d \beta_d=1-\left(\frac{s-1}{s}\right)^d β d = 1 − ( s s − 1 ) d
Summing up the above inequality over a carefully chosen distribution of cones proves our main theorem.
Theorem 1.7 (Main). There exists an absolute constant C > 0 C>0 C > 0 s ≥ 5 s\ge5 s ≥ 5 ∣ L i ∣ ≥ s + deg ( i ) |\mathcal{L}_i|\ge s+\deg(i) ∣ L i ∣ ≥ s + deg ( i ) i ∈ G i\in G i ∈ G
D 2 ≥ ( 1 − Δ β Δ s + C Δ 2 s 3 ) D = : ( 1 − γ ) D . D^2\ge\left(1-\sqrt{\frac{\Delta\beta_\Delta}{s}+\frac{C\Delta^2}{s^3}}\right)D=:(1-\gamma)D. D 2 ≥ ( 1 − s Δ β Δ + s 3 C Δ 2 ) D =: ( 1 − γ ) D . Consequently, if q > α Δ q>\alpha\Delta q > α Δ α > α ∗ \alpha>\alpha^* α > α ∗ α ∗ = 2 − exp ( − 1 / ( α ∗ − 1 ) ) ≈ 1.7408 \alpha^*=2-\exp\left(-1/(\alpha^*-1)\right)\approx1.7408 α ∗ = 2 − exp ( − 1/ ( α ∗ − 1 ) ) ≈ 1.7408 Δ \Delta Δ c α n \frac{c_\alpha}{n} n c α c α > 0 c_\alpha>0 c α > 0
We emphasize that the above bound on s s s
Proof overview
In this section we explain the main ideas to prove Theorem 1.6. Fix an arbitrary cone with center v v v H ′ H' H ′ H H H s + 1 s+1 s + 1 v v v s + ∣ H ′ ∣ s+|H'| s + ∣ H ′ ∣
To prove Theorem 1.6 we mainly need to study the action of the operator D v D H ′ D_vD_{H'} D v D H ′ f ∈ L 2 ( μ ) f \in L^2(\mu) f ∈ L 2 ( μ ) f f f H ′ H' H ′ f f f h ∗ h^* h ∗ P v D H ( f − h ∗ ) = 0 P_vD_H(f-h^*)=0 P v D H ( f − h ∗ ) = 0 D v h ∗ = 0 D_vh^*=0 D v h ∗ = 0 D v D_v D v h ∗ h^* h ∗ h ∗ h^* h ∗ ⟨ D v f , D H ′ f ⟩ μ ≥ ⟨ D v f , D v D H ′ h ∗ ⟩ μ \langle D_vf,D_{H'}f\rangle_\mu\ge\langle D_vf,D_vD_{H'}h^*\rangle_\mu ⟨ D v f , D H ′ f ⟩ μ ≥ ⟨ D v f , D v D H ′ h ∗ ⟩ μ D v f D_vf D v f ∥ D v D H ′ h ∗ ∥ μ \lVert D_vD_{H'}h^*\rVert_\mu ∥ D v D H ′ h ∗ ∥ μ
We are left with studying the action of the D v D H ′ D_vD_{H'} D v D H ′ h h h D H ′ h D_{H'}h D H ′ h D H ′ h D_{H'}h D H ′ h h ′ h' h ′ D H ′ h D_{H'}h D H ′ h
First, we define a new operator D H ′ − v D_{H'}^{-v} D H ′ − v D H ′ − v h D_{H'}^{-v}h D H ′ − v h D H ′ h D_{H'}h D H ′ h h ′ = D H ′ − v h h'=D_{H'}^{-v}h h ′ = D H ′ − v h h ′ h' h ′ c ∈ L v c\in L_v c ∈ L v
( h ′ − D H ′ h ) ( c , x ) = ( D H ′ − v h − D H h ) ( c , x ) = { ∑ i ∈ H ′ Π i , c − v h ( x ) if c ∉ x 0 otherwise (h'-D_{H'}h)(c,\mathbf{x})=(D_{H'}^{-v}h-D_Hh)(c,\mathbf{x})=
\begin{cases}
\sum_{i\in H'}\Pi_{i,c}^{-v}h(\mathbf{x}) & \text{if }c\notin\mathbf{x}\\
0 & \text{otherwise}
\end{cases} ( h ′ − D H ′ h ) ( c , x ) = ( D H ′ − v h − D H h ) ( c , x ) = { ∑ i ∈ H ′ Π i , c − v h ( x ) 0 if c ∈ / x otherwise where Π i , c − v \Pi_{i,c}^{-v} Π i , c − v e i , c − v e_{i,c}^{-v} e i , c − v c c c i ∈ H ′ i\in H' i ∈ H ′ c ∉ L i c\notin L_i c ∈ / L i Π i , c − v = 0 \Pi_{i,c}^{-v}=0 Π i , c − v = 0
∑ c ∈ L v E x [ I ( c ∉ x ) ( ∑ i ∈ H ′ Π i , c − v h ) 2 ] μ (2) \sum_{c\in L_v}\mathbb{E}_{\mathbf{x}}\left[\mathbb{I}(c\notin\mathbf{x})\left(\sum_{i\in H'}\Pi_{i,c}^{-v}h\right)^2\right]_\mu \tag*{(2)} c ∈ L v ∑ E x I ( c ∈ / x ) ( i ∈ H ′ ∑ Π i , c − v h ) 2 μ (2) Observe that the inner-sum is just an expression on the subgraph H ′ H' H ′ Π i , c \Pi_{i,c} Π i , c D i D_i D i D i ∝ ∑ c ∈ L i Π i , c D_i\propto\sum_{c\in L_i}\Pi_{i,c} D i ∝ ∑ c ∈ L i Π i , c E ( c , x ) [ ( D h ) 2 ] \mathbb{E}_{(c,\mathbf{x})}[(Dh)^2] E ( c , x ) [( D h ) 2 ] H H H H ′ H' H ′ x \mathbf{x} x c c c ⟨ D i f , D j f ⟩ \langle D_if,D_jf\rangle ⟨ D i f , D j f ⟩ ⟨ Π i , c f , Π j , c f ⟩ \langle\Pi_{i,c}f,\Pi_{j,c}f\rangle ⟨ Π i , c f , Π j , c f ⟩ i , j i,j i , j
We then upper-bound (2) in Lemma 5.2. The main observation is the following: Since every vertex i ∈ H ′ i\in H' i ∈ H ′ s + deg H ′ ( i ) s+\deg_{H'}(i) s + deg H ′ ( i ) H ′ H' H ′ c c c ( s − 1 s ) ∣ H ′ ∣ \left(\frac{s-1}{s}\right)^{|H'|} ( s s − 1 ) ∣ H ′ ∣ β ∣ H ′ ∣ ∥ ∑ i Π i , c − v h ∥ 2 \beta|H'|\left\|\sum_i\Pi_{i,c}^{-v}h\right\|^2 β ∣ H ′ ∣ ∑ i Π i , c − v h 2 c c c y \mathbf{y} y x \mathbf{x} x c ≠ x c \ne x c = x y i = c y_i = c y i = c 1 ∣ L i − v ∣ \frac{1}{|\mathcal{L}_i^{-v}|} ∣ L i − v ∣ 1 y i = x i y_i = x_i y i = x i Π i , c − v \Pi_{i,c}^{-v} Π i , c − v P x [ c ≠ x ] \mathbb{P}_x[c \ne x] P x [ c = x ] 1 − P x [ c ≠ x ] 1-\mathbb{P}_x[c \ne x] 1 − P x [ c = x ]
Lastly, to finish the proof of Theorem 1.6 we need to prove an upper-bound on ∥ ∑ i ∈ H Π i , c − v h ∥ 2 \left\|\sum_{i\in H}\Pi_{i,c}^{-v}h\right\|^2 ∑ i ∈ H Π i , c − v h 2 § 4 . In particular, the crux of the proof is Lemma 4.3 in which we upper-bound a cross term ∑ c ⟨ Π i , c f , Π j , c f ⟩ \sum_{c}\langle\Pi_{i,c}f,\Pi_{j,c}f\rangle ∑ c ⟨ Π i , c f , Π j , c f ⟩ ⟨ D 1 f , D 2 f ⟩ \langle D_1f,D_2f\rangle ⟨ D 1 f , D 2 f ⟩ [2 ] . The proof follows by decomposing f f f f f f f ( x i , x j ) = ∑ c α i , c 1 [ x i = c ] + ∑ c β c 1 [ x j = c ] f(x_i,x_j)=\sum_c\alpha_{i,c}\mathbf{1}[x_i=c]+\sum_c\beta_c\mathbf{1}[x_j=c] f ( x i , x j ) = ∑ c α i , c 1 [ x i = c ] + ∑ c β c 1 [ x j = c ]
Concurrent work
Independent of our work, Chen and Liu proved a near-optimal bound on the mixing time of the Glauber dynamics for graphs of girth > 4 >4 > 4 [11 ] . In another line, Haqi [17 ] independently proved that the Glauber dynamics mixes rapidly to generate a proper coloring of line graphs if q ≥ 2 Δ + 4 q\ge2\Delta+4 q ≥ 2Δ + 4
Acknowledgements
The proof of Theorem 1.5 is human made. The proof of Theorem 1.6 follows from a long interaction between human and AI. We started by first understanding an improved bound on sampling proper colorings of triangle free graphs and then we tried to extend the argument to all graphs.
The research is supported by a Simons Investigator Award 928589, an AFOSR grant FA9550261B166, and a Lazowska Endowed Professorship in Computer Science & Engineering. AL is also supported by the Computer Science & Engineering Educators’ Endowed Fellowship and the Jonathan Hsieh and Kathleen Ting Endowed Fund.
Preliminaries
We define D i = I − P i D_i=I-P_i D i = I − P i P i f = E [ f ∣ X − i ] P_if=\mathbb{E}[f\mid X_{-i}] P i f = E [ f ∣ X − i ] P i , D i : L 2 ( μ ) → L 2 ( μ ) P_i,D_i:L^2(\mu)\to L^2(\mu) P i , D i : L 2 ( μ ) → L 2 ( μ )
For a matrix M ∈ R m × n M\in\mathbb{R}^{m\times n} M ∈ R m × n ∥ M ∥ : = max x ∈ R n ∖ { 0 } ∥ M x ∥ 2 ∥ x ∥ 2 \|M\|:=\max_{x\in\mathbb{R}^n\setminus\{0\}}\frac{\|Mx\|_2}{\|x\|_2} ∥ M ∥ := max x ∈ R n ∖ { 0 } ∥ x ∥ 2 ∥ M x ∥ 2 ∥ M ∥ 1 \|M\|_1 ∥ M ∥ 1 M M M ∥ M ∥ ∞ \|M\|_\infty ∥ M ∥ ∞ M M M ∥ M ∥ ≤ ∥ M ∥ 1 ∥ M ∥ ∞ \|M\|\le\sqrt{\|M\|_1\|M\|_\infty} ∥ M ∥ ≤ ∥ M ∥ 1 ∥ M ∥ ∞
For a vertex i i i H ⊂ G H\subset G H ⊂ G N H ( i ) N_H(i) N H ( i ) i i i H H H
Given a graph G G G i i i L i \mathcal{L}_i L i C C C L i − C \mathcal{L}_i^{-C} L i − C L i ∖ C \mathcal{L}_i\setminus C L i ∖ C x \mathbf{x} x L i − x N ( i ) \mathcal{L}_i^{-\mathbf{x}_{N(i)}} L i − x N ( i ) L i ∖ x N ( i ) \mathcal{L}_i\setminus\mathbf{x}_{N(i)} L i ∖ x N ( i ) ℓ i \ell_i ℓ i ℓ i − C \ell_i^{-C} ℓ i − C L i \mathcal{L}_i L i L i − C \mathcal{L}_i^{-C} L i − C
For a set S S S X ∼ S X\sim S X ∼ S X X X S S S
Lemma 2.1 (Matrix Hoeffding Inequality). Let G G G H \mathcal{H} H
z = ( z v ) v ∈ V ( G ) ∈ H V ( G ) . z=(z_v)_{v\in V(G)}\in\mathcal{H}^{V(G)}. z = ( z v ) v ∈ V ( G ) ∈ H V ( G ) . Then we have
∑ i , j ∈ G A G ( i , j ) ⟨ z i , z j ⟩ H ≥ λ min ( A G ) ∑ i ∈ G ∥ z i ∥ H 2 . \sum_{i,j\in G} A_G(i,j)\langle z_i,z_j\rangle_{\mathcal{H}}\geq\lambda_{\min}(A_G)\sum_{i\in G}\lVert z_i\rVert_{\mathcal{H}}^2. i , j ∈ G ∑ A G ( i , j ) ⟨ z i , z j ⟩ H ≥ λ m i n ( A G ) i ∈ G ∑ ∥ z i ∥ H 2 . Local Inequalities over Subgraphs
Throughout the paper we study local inequalities for a subgraph H ⊂ G H\subset G H ⊂ G G ∖ H G\setminus H G ∖ H i ∈ H i\in H i ∈ H L i \mathcal{L}_i L i
Ω H = { x ∈ ∏ i L i : x i ≠ x j ∀ i j ∈ E ( H ) } and μ H = Unif ( Ω H ) . \Omega_H=\left\{x\in\prod_i\mathcal{L}_i:x_i\neq x_j\ \forall ij\in E(H)\right\}
\qquad\text{and}\qquad
\mu_H=\operatorname{Unif}(\Omega_H). Ω H = { x ∈ i ∏ L i : x i = x j ∀ ij ∈ E ( H ) } and μ H = Unif ( Ω H ) . We note that operators D i , P i D_i,P_i D i , P i
( P i H f ) ( x ) = E μ H [ f ∣ X − i = x − i ] = 1 ℓ i − x N H ( i ) ∑ c ∈ L i − x N H ( i ) f ( x i → c ) and ( D i H f ) ( x ) = f ( x ) − ( P i H f ) ( x ) , (P_i^Hf)(x)=\mathbb{E}_{\mu_H}[f\mid X_{-i}=x_{-i}]
=\frac{1}{\ell_i^{-x_{N_H(i)}}}\sum_{c\in\mathcal{L}_i^{-x_{N_H(i)}}}f(x_{i\to c})
\qquad\text{and}\qquad
(D_i^Hf)(x)=f(x)-(P_i^Hf)(x), ( P i H f ) ( x ) = E μ H [ f ∣ X − i = x − i ] = ℓ i − x N H ( i ) 1 c ∈ L i − x N H ( i ) ∑ f ( x i → c ) and ( D i H f ) ( x ) = f ( x ) − ( P i H f ) ( x ) , so we can just remove the subscript H H H D i D_i D i
Conditioned on X − i = x − i X_{-i}=x_{-i} X − i = x − i X i X_i X i L i − x N H ( i ) \mathcal{L}_i^{-x_{N_H(i)}} L i − x N H ( i ) c ∈ L i − x N H ( i ) c\in\mathcal{L}_i^{-x_{N_H(i)}} c ∈ L i − x N H ( i ) p i , c ( x ) = P μ [ X i = c ∣ X − i = x − i ] p_{i,c}(x)=\mathbb{P}_{\mu}[X_i=c\mid X_{-i}=x_{-i}] p i , c ( x ) = P μ [ X i = c ∣ X − i = x − i ]
e i , c ( x ) = 1 { x i = c } − p i , c p i , c ( 1 − p i , c ) = { 1 − p i , c p i , c , x i = c , − p i , c 1 − p i , c , x i ≠ c . e_{i,c}(x)=\frac{\mathbb{1}\{x_i=c\}-p_{i,c}}{\sqrt{p_{i,c}(1-p_{i,c})}}
=
\begin{cases}
\sqrt{\dfrac{1-p_{i,c}}{p_{i,c}}}, & x_i=c,\\
-\sqrt{\dfrac{p_{i,c}}{1-p_{i,c}}}, & x_i\neq c.
\end{cases} e i , c ( x ) = p i , c ( 1 − p i , c ) 1 { x i = c } − p i , c = ⎩ ⎨ ⎧ p i , c 1 − p i , c , − 1 − p i , c p i , c , x i = c , x i = c . Otherwise, if c ∉ L i − x N H ( i ) c\notin\mathcal{L}_i^{-x_{N_H(i)}} c ∈ / L i − x N H ( i ) e i , c = 0 e_{i,c}=0 e i , c = 0 e i , c e_{i,c} e i , c H ′ ⊂ H H'\subset H H ′ ⊂ H H ∖ H ′ H\setminus H' H ∖ H ′
For c ∈ L i − x N H ( i ) c\in\mathcal{L}_i^{-x_{N_H(i)}} c ∈ L i − x N H ( i )
E μ [ e i , c ( X ) ∣ X − i = x − i ] = 0 and E μ [ e i , c ( X ) 2 ∣ X − i = x − i ] = 1. \mathbb{E}_{\mu}[e_{i,c}(X)\mid X_{-i}=x_{-i}]=0
\qquad\text{and}\qquad
\mathbb{E}_{\mu}[e_{i,c}(X)^2\mid X_{-i}=x_{-i}]=1. E μ [ e i , c ( X ) ∣ X − i = x − i ] = 0 and E μ [ e i , c ( X ) 2 ∣ X − i = x − i ] = 1. We naturally assume all these functions are defined over H H H H H H
For a vertex i i i H = { i } H=\{i\} H = { i } 1 { x i = c } \mathbb{1}\{x_i=c\} 1 { x i = c } c ∈ L i H c\in\mathcal{L}_i^H c ∈ L i H μ \mu μ D i H D_i^H D i H e i , c e_{i,c} e i , c ℓ i \ell_i ℓ i ℓ i − 1 \ell_i-1 ℓ i − 1
More generally, for H H H i ∈ H i\in H i ∈ H
For distinct colors c , c ′ c,c' c , c ′
E μ [ e i , c ( X ) e i , c ′ ( X ) ∣ X − i = x − i ] = − p i , c p i , c ′ ( 1 − p i , c ) ( 1 − p i , c ′ ) = − 1 ℓ i − x N H ( i ) − 1 . (3) \mathbb{E}_{\mu}[e_{i,c}(X)e_{i,c'}(X)\mid X_{-i}=x_{-i}]
=-\sqrt{\frac{p_{i,c}p_{i,c'}}{(1-p_{i,c})(1-p_{i,c'})}}
=-\frac{1}{\ell_i^{-x_{N_H(i)}}-1}. \tag*{(3)} E μ [ e i , c ( X ) e i , c ′ ( X ) ∣ X − i = x − i ] = − ( 1 − p i , c ) ( 1 − p i , c ′ ) p i , c p i , c ′ = − ℓ i − x N H ( i ) − 1 1 . (3) D i e i , c = e i , c . D_i e_{i,c}=e_{i,c}. D i e i , c = e i , c . Now, we let Π i , c \Pi_{i,c} Π i , c e i , c e_{i,c} e i , c c ∈ L i − x N H ( i ) c\in\mathcal{L}_i^{-x_{N_H(i)}} c ∈ L i − x N H ( i ) h ∈ L 2 ( μ ) h\in L^2(\mu) h ∈ L 2 ( μ )
( Π i , c h ) ( x ) : = { e i , c ( x ) E μ [ h ( X ) e i , c ( X ) ∣ X − i = x − i ] if c ∈ L i − x N H ( i ) , 0 otherwise. (\Pi_{i,c}h)(x):=
\begin{cases}
e_{i,c}(x)\mathbb{E}_{\mu}[h(X)e_{i,c}(X)\mid X_{-i}=x_{-i}] & \text{if }c\in\mathcal{L}_i^{-x_{N_H(i)}},\\
0 & \text{otherwise.}
\end{cases} ( Π i , c h ) ( x ) := { e i , c ( x ) E μ [ h ( X ) e i , c ( X ) ∣ X − i = x − i ] 0 if c ∈ L i − x N H ( i ) , otherwise. We note that we might sometimes drop the superscript of H H H
For a graph consisting of one edge on vertices 1 and 2, we fix c ∈ L 1 ∩ L 2 c\in\mathcal{L}_1\cap\mathcal{L}_2 c ∈ L 1 ∩ L 2 ( x , y ) ∈ Ω (x,y)\in\Omega ( x , y ) ∈ Ω x , y ≠ c x,y\ne c x , y = c e 1 , c ( x , y ) = ℓ 1 − 1 { x = c } − 1 ℓ 1 − y − 1 e_{1,c}(x,y)=\frac{\ell_1^{-\mathbb{1}\{x=c\}}-1}{\sqrt{\ell_1^{-y}-1}} e 1 , c ( x , y ) = ℓ 1 − y − 1 ℓ 1 − 1 { x = c } − 1
( Π 1 , c f ) ( x , y ) = E μ [ f e 1 , c ∣ X 2 = y ] e 1 , c ( x , y ) = f ( c , y − ( P 1 f ) ( y ) ℓ 1 − y − 1 ⋅ − 1 ℓ 1 − y − 1 = − D 1 f ( c , y ) ℓ 1 − y − 1 . (4) \begin{aligned}
(\Pi_{1,c}f)(x,y)=\mathbb{E}_{\mu}[fe_{1,c}\mid X_2=y]e_{1,c}(x,y) \\
&=\frac{f(c,y-(P_1f)(y)}{\sqrt{\ell_1^{-y}-1}}\cdot\frac{-1}{\sqrt{\ell_1^{-y}-1}}
=-\frac{D_1f(c,y)}{\ell_1^{-y}-1}. \tag*{(4)}
\end{aligned} ( Π 1 , c f ) ( x , y ) = E μ [ f e 1 , c ∣ X 2 = y ] e 1 , c ( x , y ) = ℓ 1 − y − 1 f ( c , y − ( P 1 f ) ( y ) ⋅ ℓ 1 − y − 1 − 1 = − ℓ 1 − y − 1 D 1 f ( c , y ) . (4) Furthermore, by definition if c = y c=y c = y c = x c=x c = x Π 1 , c f ( x , c ) = 0 \Pi_{1,c}f(x,c)=0 Π 1 , c f ( x , c ) = 0 Π 2 , c f ( c , y ) = 0 \Pi_{2,c}f(c,y)=0 Π 2 , c f ( c , y ) = 0
Fact 2.2. For any i i i h ∈ L 2 ( μ ) h\in L^2(\mu) h ∈ L 2 ( μ ) x \mathbf{x} x
∑ c ∈ L i ( Π i , c h ) ( x ) = ( 1 + 1 ℓ i − x N H ( i ) − 1 ) ( D i h ) ( x ) . \sum_{c\in\mathcal{L}_i}(\Pi_{i,c}h)(\mathbf{x})
=\left(1+\frac{1}{\ell_i^{-x_{N_H(i)}}-1}\right)(D_i h)(\mathbf{x}). c ∈ L i ∑ ( Π i , c h ) ( x ) = ( 1 + ℓ i − x N H ( i ) − 1 1 ) ( D i h ) ( x ) . If H H H ℓ i − x N H ( i ) = ℓ i H \ell_i^{-x_{N_H(i)}}=\ell_i^H ℓ i − x N H ( i ) = ℓ i H ∑ c ∈ L i Π i , c = ℓ i ℓ i − 1 D i \sum_{c\in\mathcal{L}_i}\Pi_{i,c}=\frac{\ell_i}{\ell_i-1}D_i ∑ c ∈ L i Π i , c = ℓ i − 1 ℓ i D i
Proof. We fix x − i \mathbf{x}_{-i} x − i c ′ ∈ L i − x N H ( i ) c'\in\mathcal{L}_i^{-x_{N_H(i)}} c ′ ∈ L i − x N H ( i )
( ∑ c ∈ L i Π i , c ) e i , c ′ = ∑ c ∈ L i E μ [ e i , c ( X ) e i , c ′ ( X ) ∣ X − i = x − i ] e i , c = e i , c ′ − ∑ c ∈ L i , c ≠ c ′ e i , c ℓ i − x N H ( i ) − 1 = ( 1 + 1 ℓ i − x N H ( i ) − 1 ) e i , c ′ . \begin{aligned}
\left(\sum_{c\in\mathcal{L}_i}\Pi_{i,c}\right)e_{i,c'}
=\sum_{c\in\mathcal{L}_i}\mathbb{E}_{\mu}[e_{i,c}(X)e_{i,c'}(X)\mid X_{-i}=x_{-i}]e_{i,c} \\
&=e_{i,c'}-\frac{\sum_{c\in\mathcal{L}_i,c\ne c'}e_{i,c}}{\ell_i^{-x_{N_H(i)}}-1} \\
&=\left(1+\frac{1}{\ell_i^{-x_{N_H(i)}}-1}\right)e_{i,c'}.
\end{aligned} ( c ∈ L i ∑ Π i , c ) e i , c ′ = c ∈ L i ∑ E μ [ e i , c ( X ) e i , c ′ ( X ) ∣ X − i = x − i ] e i , c = e i , c ′ − ℓ i − x N H ( i ) − 1 ∑ c ∈ L i , c = c ′ e i , c = ( 1 + ℓ i − x N H ( i ) − 1 1 ) e i , c ′ . Since the vectors e i , c ′ e_{i,c'} e i , c ′ 1 \mathbf{1} 1 Π i , c \Pi_{i,c} Π i , c D i D_i D i 1 \mathbf{1} 1
Proof of Theorem 1.7
In this section we prove Theorem 1.7. As we said in the introduction, the proof is based on a careful averaging argument over cones.
Proof of Theorem 1.7 assuming Theorem 1.6. We assume that γ < 1 \gamma< 1 γ < 1 p : E ( G ) → [ 1 − κ / 2 , 1 ] \mathbf{p}: E(G) \to[1-\kappa/2,1] p : E ( G ) → [ 1 − κ /2 , 1 ] e = u v e=uv e = uv
p u v + κ 2 Δ ∑ w ∈ N G ( u ) ∩ N G ( v ) p w u p w v = 1 , (5) p_{uv}+\frac{\kappa}{2\Delta}\sum_{w\in N_G(u)\cap N_G(v)}p_{wu}p_{wv}=1, \tag*{(5)} p uv + 2Δ κ w ∈ N G ( u ) ∩ N G ( v ) ∑ p w u p w v = 1 , (5) where κ \kappa κ κ / 2 < 1 \kappa/2<1 κ /2 < 1 p \mathbf{p} p p u v = p v u p_{uv}=p_{vu} p uv = p v u p \mathbf{p} p v v v H v : = G [ { v } ∪ H v ′ ] H_v:=G[\{v\}\cup H'_v] H v := G [{ v } ∪ H v ′ ] u ∈ N ( v ) u\in N(v) u ∈ N ( v ) H v ′ H'_v H v ′ p u v p_{uv} p uv
By Theorem 1.6 with t = γ t=\gamma t = γ C ′ > 0 C'>0 C ′ > 0 f : Ω → R f:\Omega\to\mathbb{R} f : Ω → R
1 2 ∑ v [ 2 ⟨ D v f , D H v ′ f ⟩ μ + γ ∥ D v f ∥ μ 2 + κ Δ ∥ D H v ′ f ∥ μ 2 + C ′ Δ γ s 3 ⟨ f , D H v ′ f ⟩ ] ≥ 0 , (6) \frac{1}{2}\sum_v\left[2\langle D_vf,D_{H'_v}f\rangle_\mu+\gamma\lVert D_vf\rVert_\mu^2+\frac{\kappa}{\Delta}\lVert D_{H'_v}f\rVert_\mu^2+\frac{C'\Delta}{\gamma s^3}\langle f,D_{H'_v}f\rangle\right]\geq0, \tag*{(6)} 2 1 v ∑ [ 2 ⟨ D v f , D H v ′ f ⟩ μ + γ ∥ D v f ∥ μ 2 + Δ κ ∥ D H v ′ f ∥ μ 2 + γ s 3 C ′ Δ ⟨ f , D H v ′ f ⟩ ] ≥ 0 , (6) where we write κ = Δ β Δ γ ( s − 1 ) \kappa=\frac{\Delta\beta_\Delta}{\gamma(s-1)} κ = γ ( s − 1 ) Δ β Δ 0 ≤ κ ≤ γ < 1 0\leq\kappa\leq\gamma<1 0 ≤ κ ≤ γ < 1
Since D v 2 = D v D_v^2=D_v D v 2 = D v D v D_v D v
γ 2 + 1 2 ( κ Δ + C ′ Δ γ s 3 ) ∑ u ∈ N G ( v ) p u v ≤ γ + κ + C ′ Δ 2 γ s 3 2 ≤ γ , (7) \frac{\gamma}{2}+\frac{1}{2}\left(\frac{\kappa}{\Delta}+\frac{C'\Delta}{\gamma s^3}\right)\sum_{u\in N_G(v)}p_{uv}\leq\frac{\gamma+\kappa+\frac{C'\Delta^2}{\gamma s^3}}{2}\leq\gamma, \tag*{(7)} 2 γ + 2 1 ( Δ κ + γ s 3 C ′ Δ ) u ∈ N G ( v ) ∑ p uv ≤ 2 γ + κ + γ s 3 C ′ Δ 2 ≤ γ , (7) where the final inequality follows by choosing for instance C ≥ C ′ + 2 C\geq C'+2 C ≥ C ′ + 2
For an edge u v uv uv ⟨ D u f , D v f ⟩ \langle D_uf,D_vf\rangle ⟨ D u f , D v f ⟩
( p u v + p v u ) + κ Δ ∑ w ∈ N G ( u ) ∩ N G ( v ) p w u p w v = ( 5 ) , p u v = p v u 2. (8) (p_{uv}+p_{vu})+\frac{\kappa}{\Delta}\sum_{w\in N_G(u)\cap N_G(v)}p_{wu}p_{wv}\underset{(5),\,p_{uv}=p_{vu}}{=}2. \tag*{(8)} ( p uv + p v u ) + Δ κ w ∈ N G ( u ) ∩ N G ( v ) ∑ p w u p w v ( 5 ) , p uv = p v u = 2. (8) For non-edges u v uv uv D u D_u D u D v D_v D v f : Ω → R f:\Omega\to\mathbb{R} f : Ω → R ⟨ D u f , D v f ⟩ ≥ 0 \langle D_uf,D_vf\rangle\geq0 ⟨ D u f , D v f ⟩ ≥ 0 ⟨ D u f , D v f ⟩ \langle D_uf,D_vf\rangle ⟨ D u f , D v f ⟩
κ Δ ∑ w ∈ N G ( u ) ∩ N G ( v ) p w u p w v ∈ [ 0 , κ ] ⊆ [ 0 , 2 ] , (9) \frac{\kappa}{\Delta}\sum_{w\in N_G(u)\cap N_G(v)}p_{wu}p_{wv}\in[0,\kappa]\subseteq[0,2], \tag*{(9)} Δ κ w ∈ N G ( u ) ∩ N G ( v ) ∑ p w u p w v ∈ [ 0 , κ ] ⊆ [ 0 , 2 ] , (9) where we use the fact that p u w ∈ [ 0 , 1 ] p_{uw}\in[0,1] p u w ∈ [ 0 , 1 ] w ∈ N G ( u ) w\in N_G(u) w ∈ N G ( u ) ∣ N G ( u ) ∩ N G ( v ) ∣ ≤ Δ \lvert N_G(u)\cap N_G(v)\rvert\leq\Delta ∣ N G ( u ) ∩ N G ( v )∣ ≤ Δ
Consequently, (6) in turn implies that for any f : Ω → R f:\Omega\to\mathbb{R} f : Ω → R
⟨ f , ( D 2 − ( 1 − γ ) D ) f ⟩ μ = γ ∑ v ∥ D v f ∥ 2 + 2 ∑ u ≠ v unordered ⟨ D u f , D v f ⟩ μ ≥ 0. \left\langle f,\left(D^2-(1-\gamma)D\right)f\right\rangle_\mu=\gamma\sum_v\lVert D_vf\rVert^2+2\sum_{\substack{u\ne v\\\text{unordered}}}\langle D_uf,D_vf\rangle_\mu\geq0. ⟨ f , ( D 2 − ( 1 − γ ) D ) f ⟩ μ = γ v ∑ ∥ D v f ∥ 2 + 2 u = v unordered ∑ ⟨ D u f , D v f ⟩ μ ≥ 0. Finally, we show that there exists p \mathbf{p} p T : [ 1 − κ / 2 , 1 ] E ( G ) → [ 1 − κ / 2 , 1 ] E ( G ) T:[1-\kappa/2,1]^{E(G)}\to[1-\kappa/2,1]^{E(G)} T : [ 1 − κ /2 , 1 ] E ( G ) → [ 1 − κ /2 , 1 ] E ( G ) p \mathbf{p} p
( T p ) u v : = 1 − κ 2 Δ ∑ w ∈ N G ( u ) ∩ N G ( v ) p w u p w v ∈ [ 1 − κ / 2 , 1 ] , ∀ u v ∈ E ( G ) . (T\mathbf{p})_{uv}:=1-\frac{\kappa}{2\Delta}\sum_{w\in N_G(u)\cap N_G(v)}p_{wu}p_{wv}\in[1-\kappa/2,1],\qquad\forall uv\in E(G). ( T p ) uv := 1 − 2Δ κ w ∈ N G ( u ) ∩ N G ( v ) ∑ p w u p w v ∈ [ 1 − κ /2 , 1 ] , ∀ uv ∈ E ( G ) . where we used that u , v u,v u , v Δ \Delta Δ [ 1 − κ / 2 , 1 ] E ( G ) [1-\kappa/2,1]^{E(G)} [ 1 − κ /2 , 1 ] E ( G ) p ∈ [ 1 − κ / 2 , 1 ] E ( G ) p\in[1-\kappa/2,1]^{E(G)} p ∈ [ 1 − κ /2 , 1 ] E ( G )
Finally, to deduce the spectral gap of Glauber dynamics when q > α Δ q>\alpha\Delta q > α Δ α > α ∗ \alpha>\alpha^* α > α ∗ s = ( α − 1 ) Δ s=(\alpha-1)\Delta s = ( α − 1 ) Δ
γ 2 = 1 − ( 1 − 1 ( α − 1 ) Δ ) Δ α − 1 + C ( α − 1 ) 3 Δ ⟶ Δ → ∞ 1 − e − 1 / ( α − 1 ) α − 1 < 1. \gamma^2=\frac{1-\left(1-\frac{1}{(\alpha-1)\Delta}\right)^\Delta}{\alpha-1}+\frac{C}{(\alpha-1)^3\Delta}\mathrel{\longrightarrow}_{\Delta\to\infty}\frac{1-e^{-1/(\alpha-1)}}{\alpha-1}<1. γ 2 = α − 1 1 − ( 1 − ( α − 1 ) Δ 1 ) Δ + ( α − 1 ) 3 Δ C ⟶ Δ → ∞ α − 1 1 − e − 1/ ( α − 1 ) < 1. The final inequality follows because 1 − e − 1 / x 1-e^{-1/x} 1 − e − 1/ x x > 0 x>0 x > 0 α ∗ − 1 \alpha^*-1 α ∗ − 1 x = α ∗ − 1 x=\alpha^*-1 x = α ∗ − 1 Δ \Delta Δ 1 − γ ≥ c α > 0 1-\gamma\ge c_\alpha>0 1 − γ ≥ c α > 0 ≥ c α n \ge\frac{c_\alpha}{n} ≥ n c α
Pairwise Local Inequalities
The following is the main statement of this section. We prove it using Lemmas 4.2 and 4.3 proven below.
Lemma 4.1. If ℓ i ≥ s + deg H ( i ) \ell_i\ge s+\deg_H(i) ℓ i ≥ s + deg H ( i ) i ∈ H i\in H i ∈ H s ≥ 5 s\ge5 s ≥ 5 h ∈ L 2 ( μ H ) h\in L^2(\mu_H) h ∈ L 2 ( μ H )
∑ c ∥ ∑ i ∈ H Π i , c h ∥ μ H 2 ≤ ( 1 + 1 s − 1 ) ∥ D h ∥ μ H 2 + O ( 1 ) s 2 ∑ i ∈ H deg H ( i ) ∥ D i h ∥ μ H 2 . \sum_c\left\|\sum_{i\in H}\Pi_{i,c}h\right\|_{\mu_H}^2\le\left(1+\frac{1}{s-1}\right)\|Dh\|_{\mu_H}^2+\frac{O(1)}{s^2}\sum_{i\in H}\deg_H(i)\|D_i h\|_{\mu_H}^2. c ∑ i ∈ H ∑ Π i , c h μ H 2 ≤ ( 1 + s − 1 1 ) ∥ D h ∥ μ H 2 + s 2 O ( 1 ) i ∈ H ∑ deg H ( i ) ∥ D i h ∥ μ H 2 . Proof. Since each Π i , c H \Pi^H_{i,c} Π i , c H
∑ c ∥ Π i , c h ∥ μ H 2 = ⟨ h , ∑ c Π i , c h ⟩ μ H ≤ ∑ ℓ i ≥ s ( 1 + 1 s − 1 ) ∥ D i h ∥ μ H 2 . \sum_c\|\Pi_{i,c}h\|_{\mu_H}^2=\left\langle h,\sum_c\Pi_{i,c}h\right\rangle_{\mu_H}\le\sum_{\ell_i\ge s}\left(1+\frac{1}{s-1}\right)\|D_i h\|_{\mu_H}^2. c ∑ ∥ Π i , c h ∥ μ H 2 = ⟨ h , c ∑ Π i , c h ⟩ μ H ≤ ℓ i ≥ s ∑ ( 1 + s − 1 1 ) ∥ D i h ∥ μ H 2 . Fix distinct nonadjacent vertices i , j ∈ H i,j\in H i , j ∈ H s s s
∑ c ⟨ Π i , c h , Π j , c h ⟩ μ H ≤ L e m m a 4.2 ( 1 + 1 s − 1 ) ⟨ D i h , D j h ⟩ μ H . \sum_c\langle\Pi_{i,c}h,\Pi_{j,c}h\rangle_{\mu_H}\le_{\mathrm{Lemma\ 4.2}}\left(1+\frac{1}{s-1}\right)\langle D_i h,D_j h\rangle_{\mu_H}. c ∑ ⟨ Π i , c h , Π j , c h ⟩ μ H ≤ Lemma 4.2 ( 1 + s − 1 1 ) ⟨ D i h , D j h ⟩ μ H . Similarly for adjacent vertices i , j ∈ H i,j\in H i , j ∈ H s + 1 s+1 s + 1
∑ c ⟨ Π i , c h , Π j , c h ⟩ μ H ≤ L e m m a 4.3 ⟨ D i h , D j h ⟩ μ H + O ( 1 ) s 2 ( ∥ D i h ∥ μ H 2 + ∥ D j h ∥ μ H 2 ) \sum_c\langle\Pi_{i,c}h,\Pi_{j,c}h\rangle_{\mu_H}\le_{\mathrm{Lemma\ 4.3}}\langle D_i h,D_j h\rangle_{\mu_H}+\frac{O(1)}{s^2}\left(\|D_i h\|_{\mu_H}^2+\|D_j h\|_{\mu_H}^2\right) c ∑ ⟨ Π i , c h , Π j , c h ⟩ μ H ≤ Lemma 4.3 ⟨ D i h , D j h ⟩ μ H + s 2 O ( 1 ) ( ∥ D i h ∥ μ H 2 + ∥ D j h ∥ μ H 2 ) ≤ L e m m a 1.4 ( 1 + 1 s − 1 ) ⟨ D i h , D j h ⟩ μ H + O ( 1 ) s 2 ( ∥ D i h ∥ μ H 2 + ∥ D j h ∥ μ H 2 ) . \le_{\mathrm{Lemma\ 1.4}}\left(1+\frac{1}{s-1}\right)\langle D_i h,D_j h\rangle_{\mu_H}+\frac{O(1)}{s^2}\left(\|D_i h\|_{\mu_H}^2+\|D_j h\|_{\mu_H}^2\right). ≤ Lemma 1.4 ( 1 + s − 1 1 ) ⟨ D i h , D j h ⟩ μ H + s 2 O ( 1 ) ( ∥ D i h ∥ μ H 2 + ∥ D j h ∥ μ H 2 ) . Summing all these proves the lemma. □
Lemma 4.2. Given a graph of two isolated vertices labeled 1 1 1 2 2 2 s ≥ 2 s\ge2 s ≥ 2 L 1 , L 2 L_1,L_2 L 1 , L 2 ℓ 1 , ℓ 2 ≥ s \ell_1,\ell_2\ge s ℓ 1 , ℓ 2 ≥ s f ∈ L 2 ( μ ) f\in L^2(\mu) f ∈ L 2 ( μ )
∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ ≤ ( 1 + 1 s − 1 ) ⟨ D 1 f , D 2 f ⟩ μ . \sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu\le\left(1+\frac{1}{s-1}\right)\langle D_1f,D_2f\rangle_\mu. c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ ≤ ( 1 + s − 1 1 ) ⟨ D 1 f , D 2 f ⟩ μ . Proof. The difference D 2 − Π 2 , c D_2-\Pi_{2,c} D 2 − Π 2 , c Π 2 , c \Pi_{2,c} Π 2 , c e 2 , c e_{2,c} e 2 , c P 2 e 2 , c = 0 P_2e_{2,c}=0 P 2 e 2 , c = 0 D 1 − Π 1 , c D_1-\Pi_{1,c} D 1 − Π 1 , c
Furthermore, D 1 D 2 ≥ 0 D_1D_2\ge0 D 1 D 2 ≥ 0 Π 1 , c ( D 2 − Π 2 , c ) ≥ 0 \Pi_{1,c}(D_2-\Pi_{2,c})\ge0 Π 1 , c ( D 2 − Π 2 , c ) ≥ 0 Π 2 , c ( D 1 − Π 1 , c ) ≥ 0 \Pi_{2,c}(D_1-\Pi_{1,c})\ge0 Π 2 , c ( D 1 − Π 1 , c ) ≥ 0
( 1 + 1 s − 1 ) D 1 D 2 − ∑ c Π 1 , c Π 2 , c = ( 1 + 1 s − 1 − ℓ 1 2 ( ℓ 1 − 1 ) − ℓ 2 2 ( ℓ 2 − 1 ) ) D 1 D 2 + 1 2 ∑ c ( Π 1 , c ( D 2 − Π 2 , c ) + Π 2 , c ( D 1 − Π 1 , c ) ) = ( 1 s − 1 − 1 2 ( ℓ 1 − 1 ) − 1 2 ( ℓ 2 − 1 ) ) D 1 D 2 + 1 2 ∑ c ( Π 1 , c ( D 2 − Π 2 , c ) + Π 2 , c ( D 1 − Π 1 , c ) ) ≥ μ 0. \begin{aligned}
\left(1+\frac{1}{s-1}\right)D_1D_2-\sum_c\Pi_{1,c}\Pi_{2,c}
&=\left(1+\frac{1}{s-1}-\frac{\ell_1}{2(\ell_1-1)}-\frac{\ell_2}{2(\ell_2-1)}\right)D_1D_2\\
&\quad+\frac{1}{2}\sum_c\left(\Pi_{1,c}(D_2-\Pi_{2,c})+\Pi_{2,c}(D_1-\Pi_{1,c})\right)\\
&=\left(\frac{1}{s-1}-\frac{1}{2(\ell_1-1)}-\frac{1}{2(\ell_2-1)}\right)D_1D_2\\
&\quad+\frac{1}{2}\sum_c\left(\Pi_{1,c}(D_2-\Pi_{2,c})+\Pi_{2,c}(D_1-\Pi_{1,c})\right)\ge_\mu0.
\end{aligned} ( 1 + s − 1 1 ) D 1 D 2 − c ∑ Π 1 , c Π 2 , c = ( 1 + s − 1 1 − 2 ( ℓ 1 − 1 ) ℓ 1 − 2 ( ℓ 2 − 1 ) ℓ 2 ) D 1 D 2 + 2 1 c ∑ ( Π 1 , c ( D 2 − Π 2 , c ) + Π 2 , c ( D 1 − Π 1 , c ) ) = ( s − 1 1 − 2 ( ℓ 1 − 1 ) 1 − 2 ( ℓ 2 − 1 ) 1 ) D 1 D 2 + 2 1 c ∑ ( Π 1 , c ( D 2 − Π 2 , c ) + Π 2 , c ( D 1 − Π 1 , c ) ) ≥ μ 0. In the first equality we are using the fact that, in this subgraph with two disconnected vertices, Fact 2.2 gives ∑ c Π 1 , c = ℓ 1 ℓ 1 − 1 D 1 \sum_c\Pi_{1,c}=\frac{\ell_1}{\ell_1-1}D_1 ∑ c Π 1 , c = ℓ 1 − 1 ℓ 1 D 1
Lemma 4.3. Given a graph consisting of an edge between vertices 1 and 2. Suppose s ≥ 5 s\ge5 s ≥ 5 L 1 , L 2 \mathcal{L}_1,\mathcal{L}_2 L 1 , L 2 ℓ 1 , ℓ 2 ≥ s + 1 \ell_1,\ell_2\ge s+1 ℓ 1 , ℓ 2 ≥ s + 1 f ∈ L 2 ( μ ) f\in L^2(\mu) f ∈ L 2 ( μ )
∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ ≤ ⟨ D 1 f , D 2 f ⟩ μ + O ( 1 ) s 2 ( ∥ D 1 f ∥ μ 2 + ∥ D 2 f ∥ μ 2 ) . \sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu\le\langle D_1f,D_2f\rangle_\mu+\frac{O(1)}{s^2}\left(\|D_1f\|_\mu^2+\|D_2f\|_\mu^2\right). c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ ≤ ⟨ D 1 f , D 2 f ⟩ μ + s 2 O ( 1 ) ( ∥ D 1 f ∥ μ 2 + ∥ D 2 f ∥ μ 2 ) . Proof of Lemma 4.3. We define S \mathcal{S} S Ω \Omega Ω f 0 + f 1 ( X 1 ) + f 2 ( X 2 ) f_0+f_1(X_1)+f_2(X_2) f 0 + f 1 ( X 1 ) + f 2 ( X 2 ) f 0 ∈ R f_0\in\mathbb{R} f 0 ∈ R f i : L i → R f_i:\mathcal{L}_i\to\mathbb{R} f i : L i → R
f = f S + f S ⊥ , where f S ∈ S and f S ⊥ ⊥ L 2 ( μ ) S . f=f_{\mathcal{S}}+f_{\mathcal{S}}^\perp,\qquad\text{where }f_{\mathcal{S}}\in\mathcal{S}\text{ and }f_{\mathcal{S}}^\perp\perp_{L^2(\mu)}\mathcal{S}. f = f S + f S ⊥ , where f S ∈ S and f S ⊥ ⊥ L 2 ( μ ) S . Here, for any ( x 1 , x 2 ) ∈ Ω (x_1,x_2)\in\Omega ( x 1 , x 2 ) ∈ Ω
f S ( x 1 , x 2 ) = f 0 + f 1 ( x 1 ) + f 2 ( x 2 ) , where ∑ c ∈ L 1 f 1 ( c ) = ∑ c ∈ L 2 f 2 ( c ) = 0. (10) f_{\mathcal{S}}(x_1,x_2)=f_0+f_1(x_1)+f_2(x_2),\qquad\text{where }\sum_{c\in\mathcal{L}_1}f_1(c)=\sum_{c\in\mathcal{L}_2}f_2(c)=0. \tag*{(10)} f S ( x 1 , x 2 ) = f 0 + f 1 ( x 1 ) + f 2 ( x 2 ) , where c ∈ L 1 ∑ f 1 ( c ) = c ∈ L 2 ∑ f 2 ( c ) = 0. (10) We define an operator P ‾ 1 \overline{P}_1 P 1 L 2 ( μ ) → R L 2 L^2(\mu)\to\mathbb{R}^{\mathcal{L}_2} L 2 ( μ ) → R L 2 P ‾ 1 g ( c ) = E μ [ g ( X 1 , X 2 ) ∣ X 2 = c ] \overline{P}_1g(c)=\mathbb{E}_\mu[g(X_1,X_2)\mid X_2=c] P 1 g ( c ) = E μ [ g ( X 1 , X 2 ) ∣ X 2 = c ] P ‾ 2 \overline{P}_2 P 2
We claim that
∣ ∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 D 1 f ) ( c ) ⋅ ( P ‾ 1 D 2 f ) ( c ) ∣ ≤ O ( 1 ) s 2 ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ . (11) \left|\sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}(\overline{P}_2D_1f)(c)\cdot(\overline{P}_1D_2f)(c)\right|\le\frac{O(1)}{s^2}\|D_1f\|_\mu\|D_2f\|_\mu. \tag*{(11)} c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ⋅ ( P 1 D 2 f ) ( c ) ≤ s 2 O ( 1 ) ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ . (11) and
∣ ⟨ D 1 f S , D 2 f S ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 D 1 f ) ( c ) ⋅ ( P ‾ 1 D 2 f ) ( c ) ∣ ≤ O ( 1 ) s 2 ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ . (12) \left|\langle D_1f_{\mathcal{S}},D_2f_{\mathcal{S}}\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}(\overline{P}_2D_1f)(c)\cdot(\overline{P}_1D_2f)(c)\right|\le\frac{O(1)}{s^2}\|D_1f_{\mathcal{S}}\|_\mu\|D_2f_{\mathcal{S}}\|_\mu. \tag*{(12)} ⟨ D 1 f S , D 2 f S ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ⋅ ( P 1 D 2 f ) ( c ) ≤ s 2 O ( 1 ) ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ . (12) Assuming (11) and (12), we now complete the proof. Since S \mathcal{S} S X 1 X_1 X 1 x ∈ L 1 x\in\mathcal{L}_1 x ∈ L 1
( P ‾ 2 f S ⊥ ) ( x ) = 1 ℓ 2 − x ∑ y ∈ L 2 ∖ { x } f S ⊥ ( x , y ) = ∣ Ω ∣ ℓ 2 − x ⟨ f S ⊥ , 1 { X 1 = x } ⟩ μ = 0. (13) (\overline{P}_2f_{\mathcal{S}}^\perp)(x)=\frac{1}{\ell_2-x}\sum_{y\in\mathcal{L}_2\setminus\{x\}}f_{\mathcal{S}}^\perp(x,y)=\frac{|\Omega|}{\ell_2-x}\left\langle f_{\mathcal{S}}^\perp,\mathbb{1}_{\{X_1=x\}}\right\rangle_\mu=0. \tag*{(13)} ( P 2 f S ⊥ ) ( x ) = ℓ 2 − x 1 y ∈ L 2 ∖ { x } ∑ f S ⊥ ( x , y ) = ℓ 2 − x ∣Ω∣ ⟨ f S ⊥ , 1 { X 1 = x } ⟩ μ = 0. (13) Similarly, we have P 1 f S ⊥ = 0 P_1f_S^\perp=0 P 1 f S ⊥ = 0 D 1 f S ⊥ = D 2 f S ⊥ = f S ⊥ D_1f_S^\perp=D_2f_S^\perp=f_S^\perp D 1 f S ⊥ = D 2 f S ⊥ = f S ⊥
⟨ D 1 f , D 2 f ⟩ μ = ⟨ D 1 f S , D 2 f S ⟩ μ + ∥ f S ⊥ ∥ μ 2 . (14) \langle D_1f,D_2f\rangle_\mu=\langle D_1f_S,D_2f_S\rangle_\mu+\lVert f_S^\perp\rVert_\mu^2. \tag*{(14)} ⟨ D 1 f , D 2 f ⟩ μ = ⟨ D 1 f S , D 2 f S ⟩ μ + ∥ f S ⊥ ∥ μ 2 . (14) With this decomposition, it follows that
∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − ⟨ D 1 f , D 2 f ⟩ μ = ( ∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 ‾ D 1 f ) ( c ) ⋅ ( P 1 ‾ D 2 f ) ( c ) ) − ∥ f S ⊥ ∥ μ 2 − ( ⟨ D 1 f S , D 2 f S ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 ‾ D 1 f ) ( c ) ⋅ ( P 1 ‾ D 2 f ) ( c ) ) ≤ O ( 1 ) s 2 ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ + O ( 1 ) s 2 ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ − ∥ f S ⊥ ∥ μ 2 ≤ O ( 1 ) s 2 ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ . (15) \begin{aligned}
\sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu-\langle D_1f,D_2f\rangle_\mu
={}&\left(\sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P_2}D_1f)(c)\cdot(\overline{P_1}D_2f)(c)\right)-\lVert f_S^\perp\rVert_\mu^2\\
&-\left(\langle D_1f_S,D_2f_S\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P_2}D_1f)(c)\cdot(\overline{P_1}D_2f)(c)\right)\\
&\leq\frac{O(1)}{s^2}\lVert D_1f\rVert_\mu\lVert D_2f\rVert_\mu+\frac{O(1)}{s^2}\lVert D_1f_S\rVert_\mu\lVert D_2f_S\rVert_\mu-\lVert f_S^\perp\rVert_\mu^2\\
&\leq\frac{O(1)}{s^2}\lVert D_1f\rVert_\mu\lVert D_2f\rVert_\mu. \tag*{(15)}
\end{aligned} c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − ⟨ D 1 f , D 2 f ⟩ μ = ( c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ⋅ ( P 1 D 2 f ) ( c ) ) − ∥ f S ⊥ ∥ μ 2 − ( ⟨ D 1 f S , D 2 f S ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ⋅ ( P 1 D 2 f ) ( c ) ) ≤ s 2 O ( 1 ) ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ + s 2 O ( 1 ) ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ − ∥ f S ⊥ ∥ μ 2 ≤ s 2 O ( 1 ) ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ . (15) Proof of (11) . First, we note that
∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ∑ ( x , y ) ∈ Ω ( Π 1 , c f ) ( x , y ) ⋅ ( Π 2 , c f ) ( x , y ) = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 x ∈ L 1 , y ∈ L 2 x , y , c d i s t i n c t D 1 f ( c , y ) D 2 f ( x , c ) ( ℓ 1 y − 1 ) ( ℓ 2 x − 1 ) . \sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu=\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}\sum_{(x,y)\in\Omega}(\Pi_{1,c}f)(x,y)\cdot(\Pi_{2,c}f)(x,y)=\frac{1}{|\Omega|}\sum_{\substack{c\in L_1\cap L_2\\x\in L_1,\ y\in L_2\\x,y,c\ \mathrm{distinct}}}\frac{D_1f(c,y)D_2f(x,c)}{(\ell_1^y-1)(\ell_2^x-1)}. c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ = ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( x , y ) ∈ Ω ∑ ( Π 1 , c f ) ( x , y ) ⋅ ( Π 2 , c f ) ( x , y ) = ∣Ω∣ 1 c ∈ L 1 ∩ L 2 x ∈ L 1 , y ∈ L 2 x , y , c distinct ∑ ( ℓ 1 y − 1 ) ( ℓ 2 x − 1 ) D 1 f ( c , y ) D 2 f ( x , c ) . where the second identity uses that Π 1 , c f ( x , c ) = Π 2 , c f ( c , y ) = 0 \Pi_{1,c}f(x,c)=\Pi_{2,c}f(c,y)=0 Π 1 , c f ( x , c ) = Π 2 , c f ( c , y ) = 0
Having this we prove (11). For c ∈ L 1 ∩ L 2 c\in L_1\cap L_2 c ∈ L 1 ∩ L 2
( P 2 ‾ D 1 f ) ( c ) = 1 ℓ 2 − 1 ∑ y ∈ L 2 ∖ { c } D 1 f ( c , y ) and ( P 1 ‾ D 2 f ) ( c ) = 1 ℓ 1 − 1 ∑ x ∈ L 1 ∖ { c } D 2 f ( x , c ) . (\overline{P_2}D_1f)(c)=\frac{1}{\ell_2-1}\sum_{y\in L_2\setminus\{c\}}D_1f(c,y)\quad\text{and}\quad(\overline{P_1}D_2f)(c)=\frac{1}{\ell_1-1}\sum_{x\in L_1\setminus\{c\}}D_2f(x,c). ( P 2 D 1 f ) ( c ) = ℓ 2 − 1 1 y ∈ L 2 ∖ { c } ∑ D 1 f ( c , y ) and ( P 1 D 2 f ) ( c ) = ℓ 1 − 1 1 x ∈ L 1 ∖ { c } ∑ D 2 f ( x , c ) . Let Ω 1 , Ω 2 ⊂ Ω \Omega_1,\Omega_2\subset\Omega Ω 1 , Ω 2 ⊂ Ω ( x , y ) (x,y) ( x , y ) x ∈ L 1 ∩ L 2 x\in L_1\cap L_2 x ∈ L 1 ∩ L 2 y ∈ L 1 ∩ L 2 y\in L_1\cap L_2 y ∈ L 1 ∩ L 2 g 1 ∈ R Ω 1 g_1\in\mathbb{R}^{\Omega_1} g 1 ∈ R Ω 1 D 1 f D_1f D 1 f g 2 ∈ R Ω 2 g_2\in\mathbb{R}^{\Omega_2} g 2 ∈ R Ω 2 D 2 f D_2f D 2 f
∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 ‾ D 1 f ) ( c ) ⋅ ( P 1 ‾ D 2 f ) ( c ) = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ∑ x ∈ L 1 − c , y ∈ L 2 − c g 1 ( c , y ) g 2 ( x , c ) ⋅ ( 1 { x ≠ y } ( ℓ 1 y − 1 ) ( ℓ 2 x − 1 ) − 1 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ) ≤ ∑ c ∈ L 1 ∩ L 2 ∥ M c ∥ ∣ Ω ∣ ⋅ ∥ g 1 c ∥ ∥ g 2 c ∥ . (16) \begin{aligned}
\sum_c\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P_2}D_1f)(c)\cdot(\overline{P_1}D_2f)(c)
={}&\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}\sum_{\substack{x\in L_1^{-c},\ y\in L_2^{-c}}}g_1(c,y)g_2(x,c)\\
&\qquad\cdot\left(\frac{\mathbb{1}\{x\ne y\}}{(\ell_1^y-1)(\ell_2^x-1)}-\frac{1}{(\ell_1-1)(\ell_2-1)}\right)\\
\leq{}&\sum_{c\in L_1\cap L_2}\frac{\lVert M^c\rVert}{|\Omega|}\cdot\lVert g_1^c\rVert\lVert g_2^c\rVert. \tag*{(16)}
\end{aligned} c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ⋅ ( P 1 D 2 f ) ( c ) = ≤ ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ x ∈ L 1 − c , y ∈ L 2 − c ∑ g 1 ( c , y ) g 2 ( x , c ) ⋅ ( ( ℓ 1 y − 1 ) ( ℓ 2 x − 1 ) 1 { x = y } − ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 ) c ∈ L 1 ∩ L 2 ∑ ∣Ω∣ ∥ M c ∥ ⋅ ∥ g 1 c ∥ ∥ g 2 c ∥ . (16) where the norms are the Euclidean ℓ 2 \ell_2 ℓ 2 g 1 c , g 2 c g_1^c,g_2^c g 1 c , g 2 c g 1 , g 2 g_1,g_2 g 1 , g 2 c c c c ∈ L 1 ∩ L 2 c\in L_1\cap L_2 c ∈ L 1 ∩ L 2 M c ∈ R L 2 − c × L 1 − c M^c\in\mathbb{R}^{L_2^{-c}\times L_1^{-c}} M c ∈ R L 2 − c × L 1 − c
( M c ) y , x = 1 { x ≠ y } ( ℓ 1 y − 1 ) ( ℓ 2 x − 1 ) − 1 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) . (M^c)_{y,x}=\frac{\mathbb{1}\{x\ne y\}}{(\ell_1^y-1)(\ell_2^x-1)}-\frac{1}{(\ell_1-1)(\ell_2-1)}. ( M c ) y , x = ( ℓ 1 y − 1 ) ( ℓ 2 x − 1 ) 1 { x = y } − ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 . Fix c ∈ L 1 ∩ L 2 c \in\mathcal{L}_1 \cap\mathcal{L}_2 c ∈ L 1 ∩ L 2 ∥ M c ∥ ≤ ∥ M c ∥ ∞ ∥ M c ∥ 1 \lVert M^c\rVert\le\sqrt{\lVert M^c\rVert_\infty\lVert M^c\rVert_1} ∥ M c ∥ ≤ ∥ M c ∥ ∞ ∥ M c ∥ 1 ∥ M c ∥ 1 = max y ∈ L 2 − c ∑ x ∈ L 1 − c ∣ M y , x c ∣ \lVert M^c\rVert_1=\max_{y\in\mathcal{L}_2^{-c}}\sum_{x\in\mathcal{L}_1^{-c}}|M^c_{y,x}| ∥ M c ∥ 1 = max y ∈ L 2 − c ∑ x ∈ L 1 − c ∣ M y , x c ∣
For y ∈ L 2 − c y\in\mathcal{L}_2^{-c} y ∈ L 2 − c
∑ x ∈ L 1 − c ∣ M y , x c ∣ = ∑ x ∈ L 1 − c − y ( 1 ( ℓ 1 y − 1 ) ( ℓ 2 − x − 1 ) − 1 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ) + 1 { y ∈ L 1 } ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ≤ O ( 1 ) s 2 . \sum_{x\in\mathcal{L}_1^{-c}}|M^c_{y,x}|=\sum_{x\in\mathcal{L}_1^{-c-y}}\left(\frac{1}{(\ell_1^y-1)(\ell_2^{-x}-1)}-\frac{1}{(\ell_1-1)(\ell_2-1)}\right)+\frac{\mathbb{1}\{y\in\mathcal{L}_1\}}{(\ell_1-1)(\ell_2-1)}\le\frac{O(1)}{s^2}. x ∈ L 1 − c ∑ ∣ M y , x c ∣ = x ∈ L 1 − c − y ∑ ( ( ℓ 1 y − 1 ) ( ℓ 2 − x − 1 ) 1 − ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 ) + ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 { y ∈ L 1 } ≤ s 2 O ( 1 ) . where the inequality uses for x ≠ y x\ne y x = y 0 ≤ M y , x c ≤ s ℓ 1 − 1 ( 1 ( s − 1 ) 2 − 1 s 2 ) ≤ O ( 1 ) ( ℓ 1 − 1 ) s 2 0\le M^c_{y,x}\le\frac{s}{\ell_1-1}\left(\frac{1}{(s-1)^2}-\frac{1}{s^2}\right)\le\frac{O(1)}{(\ell_1-1)s^2} 0 ≤ M y , x c ≤ ℓ 1 − 1 s ( ( s − 1 ) 2 1 − s 2 1 ) ≤ ( ℓ 1 − 1 ) s 2 O ( 1 ) ∥ M c ∥ ∞ ≤ O ( 1 ) s 2 \lVert M^c\rVert_\infty\le\frac{O(1)}{s^2} ∥ M c ∥ ∞ ≤ s 2 O ( 1 ) ∥ M c ∥ ≤ O ( 1 ) s 2 \lVert M^c\rVert\le\frac{O(1)}{s^2} ∥ M c ∥ ≤ s 2 O ( 1 )
Consequently, we have
∣ ∑ c ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 D 1 f ‾ ) ( c ) ( P 1 D 2 f ‾ ) ( c ) ∣ ≤ ∑ c ∈ L 1 ∩ L 2 ∥ M c ∥ ∣ Ω ∣ ∥ g 1 c ∥ ∥ g 2 c ∥ \left|\sum_{c}\langle\Pi_{1,c}f,\Pi_{2,c}f\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}(\overline{P_2D_1f})(c)(\overline{P_1D_2f})(c)\right|
\le\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}\frac{\lVert M^c\rVert}{|\Omega|}\lVert g_1^c\rVert\lVert g_2^c\rVert c ∑ ⟨ Π 1 , c f , Π 2 , c f ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ( P 1 D 2 f ) ( c ) ≤ c ∈ L 1 ∩ L 2 ∑ ∣Ω∣ ∥ M c ∥ ∥ g 1 c ∥ ∥ g 2 c ∥ ≤ Cauchy-Schwarz O ( 1 ) ∥ g 1 ∥ ∥ g 2 ∥ ∣ Ω ∣ s 2 ≤ O ( 1 ) s 2 ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ . \underset{\text{Cauchy-Schwarz}}{\le}\frac{O(1)\lVert g_1\rVert\lVert g_2\rVert}{|\Omega|s^2}\le\frac{O(1)}{s^2}\lVert D_1f\rVert_\mu\lVert D_2f\rVert_\mu. Cauchy-Schwarz ≤ ∣Ω∣ s 2 O ( 1 ) ∥ g 1 ∥ ∥ g 2 ∥ ≤ s 2 O ( 1 ) ∥ D 1 f ∥ μ ∥ D 2 f ∥ μ . This proves (11).
Proof of (12) We first claim that
1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 D 1 f ‾ ) ( c ) ( P 1 D 2 f ‾ ) ( c ) − ⟨ D 1 f S , D 2 f S ⟩ μ = ⟨ P 1 f 1 , P 2 f 2 ⟩ μ + 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 P 1 f 1 ‾ ) ( c ) ( P 1 P 2 f 2 ‾ ) ( c ) . (17) \frac{1}{|\Omega|}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}(\overline{P_2D_1f})(c)(\overline{P_1D_2f})(c)-\langle D_1f_S,D_2f_S\rangle_\mu=\langle P_1f_1,P_2f_2\rangle_\mu+\frac{1}{|\Omega|}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}(\overline{P_2P_1f_1})(c)(\overline{P_1P_2f_2})(c). \tag*{(17)} ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ( P 1 D 2 f ) ( c ) − ⟨ D 1 f S , D 2 f S ⟩ μ = ⟨ P 1 f 1 , P 2 f 2 ⟩ μ + ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 P 1 f 1 ) ( c ) ( P 1 P 2 f 2 ) ( c ) . (17) Having this, and using P μ [ X 1 = c ] = ℓ 2 − 1 ∣ Ω ∣ \mathbb{P}_\mu[X_1=c]=\frac{\ell_2-1}{|\Omega|} P μ [ X 1 = c ] = ∣Ω∣ ℓ 2 − 1
∣ ⟨ D 1 f S , D 2 f S ⟩ μ − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P 2 D 1 f ‾ ) ( c ) ( P 1 D 2 f ‾ ) ( c ) ∣ \left|\langle D_1f_S,D_2f_S\rangle_\mu-\frac{1}{|\Omega|}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}(\overline{P_2D_1f})(c)(\overline{P_1D_2f})(c)\right| ⟨ D 1 f S , D 2 f S ⟩ μ − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ( P 1 D 2 f ) ( c ) ≤ Triangle inequality ∣ ⟨ P 1 f 1 , P 2 f 2 ⟩ μ + 1 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ∑ c ∈ L 1 ∩ L 2 P μ [ X 1 = c ] ( P 2 P 1 f 1 ‾ ) ( c ) P μ [ X 2 = c ] ( P 1 P 2 f 2 ‾ ) ( c ) ∣ \underset{\text{Triangle inequality}}{\le}\left|\langle P_1f_1,P_2f_2\rangle_\mu+\frac{1}{\sqrt{(\ell_1-1)(\ell_2-1)}}\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}\sqrt{\mathbb{P}_\mu[X_1=c](\overline{P_2P_1f_1})(c)}\sqrt{\mathbb{P}_\mu[X_2=c](\overline{P_1P_2f_2})(c)}\right| Triangle inequality ≤ ⟨ P 1 f 1 , P 2 f 2 ⟩ μ + ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 c ∈ L 1 ∩ L 2 ∑ P μ [ X 1 = c ] ( P 2 P 1 f 1 ) ( c ) P μ [ X 2 = c ] ( P 1 P 2 f 2 ) ( c ) ≤ Cauchy-Schwarz ∥ P 1 f 1 ∥ μ ∥ P 2 f 2 ∥ μ + 1 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ( ∑ c ∈ L 1 ∩ L 2 P μ [ X 1 = c ] ( P 2 P 1 f 1 ‾ ) ( c ) 2 ) 1 / 2 ⋅ ( ∑ c ∈ L 1 ∩ L 2 P μ [ X 2 = c ] ( P 1 P 2 f 2 ‾ ) ( c ) 2 ) 1 / 2 ≤ ∥ P 1 f 1 ∥ μ ∥ P 2 f 2 ∥ μ + ∥ P 2 P 1 f 1 ∥ μ ∥ P 1 P 2 f 2 ∥ μ ≤ O ( 1 ) ⋅ ∥ P 1 f 1 ∥ μ ∥ P 2 f 2 ∥ μ \begin{aligned}
\underset{\text{Cauchy-Schwarz}}{\le}\lVert P_1f_1\rVert_\mu\lVert P_2f_2\rVert_\mu+\frac{1}{\sqrt{(\ell_1-1)(\ell_2-1)}}\left(\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}\mathbb{P}_\mu[X_1=c](\overline{P_2P_1f_1})(c)^2\right)^{1/2} \\
&\cdot\left(\sum_{c\in\mathcal{L}_1\cap\mathcal{L}_2}\mathbb{P}_\mu[X_2=c](\overline{P_1P_2f_2})(c)^2\right)^{1/2} \\
&\le\lVert P_1f_1\rVert_\mu\lVert P_2f_2\rVert_\mu+\lVert P_2P_1f_1\rVert_\mu\lVert P_1P_2f_2\rVert_\mu\le O(1)\cdot\lVert P_1f_1\rVert_\mu\lVert P_2f_2\rVert_\mu
\end{aligned} Cauchy-Schwarz ≤ ∥ P 1 f 1 ∥ μ ∥ P 2 f 2 ∥ μ + ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) 1 ( c ∈ L 1 ∩ L 2 ∑ P μ [ X 1 = c ] ( P 2 P 1 f 1 ) ( c ) 2 ) 1/2 ⋅ ( c ∈ L 1 ∩ L 2 ∑ P μ [ X 2 = c ] ( P 1 P 2 f 2 ) ( c ) 2 ) 1/2 ≤ ∥ P 1 f 1 ∥ μ ∥ P 2 f 2 ∥ μ + ∥ P 2 P 1 f 1 ∥ μ ∥ P 1 P 2 f 2 ∥ μ ≤ O ( 1 ) ⋅ ∥ P 1 f 1 ∥ μ ∥ P 2 f 2 ∥ μ ≤ Claim 4.4 , ∥ D 2 f S ∥ μ = ∥ D 2 f 2 ∥ μ O ( 1 ) ⋅ ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) − 1 ≤ O ( 1 ) s 2 ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ . \underset{\text{Claim 4.4},\ \lVert D_2f_S\rVert_\mu=\lVert D_2f_2\rVert_\mu}{\le}\frac{O(1)\cdot\lVert D_1f_S\rVert_\mu\lVert D_2f_S\rVert_\mu}{(\ell_1-1)(\ell_2-1)-1}\le\frac{O(1)}{s^2}\lVert D_1f_S\rVert_\mu\lVert D_2f_S\rVert_\mu. Claim 4.4 , ∥ D 2 f S ∥ μ = ∥ D 2 f 2 ∥ μ ≤ ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) − 1 O ( 1 ) ⋅ ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ ≤ s 2 O ( 1 ) ∥ D 1 f S ∥ μ ∥ D 2 f S ∥ μ . where we used that P 2 P 1 f P_2P_1f P 2 P 1 f P 2 P 1 f ‾ \overline{P_2P_1f} P 2 P 1 f L 2 ( μ ) L^2(\mu) L 2 ( μ )
It remains to prove (16). First, note that
⟨ D 1 f S , D 2 f S ⟩ μ = ⟨ f 1 , f 2 ⟩ μ − ⟨ f 1 , P 1 f 2 ⟩ μ − ⟨ P 2 f 1 , f 2 ⟩ μ + ⟨ P 1 f 1 , P 2 f 2 ⟩ μ = ⟨ f 1 , f 2 ⟩ μ + ⟨ P 1 f 1 , P 2 f 2 ⟩ μ = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 f 1 ( c ) f 2 ( c ) + ⟨ P 1 f 1 , P 2 f 2 ⟩ μ . (18) \begin{aligned}
\langle D_1f_S,D_2f_S\rangle_\mu=\langle f_1,f_2\rangle_\mu-\langle f_1,P_1f_2\rangle_\mu-\langle P_2f_1,f_2\rangle_\mu+\langle P_1f_1,P_2f_2\rangle_\mu\\
&=\langle f_1,f_2\rangle_\mu+\langle P_1f_1,P_2f_2\rangle_\mu\\
&=\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}f_1(c)f_2(c)+\langle P_1f_1,P_2f_2\rangle_\mu. \tag*{(18)}
\end{aligned} ⟨ D 1 f S , D 2 f S ⟩ μ = ⟨ f 1 , f 2 ⟩ μ − ⟨ f 1 , P 1 f 2 ⟩ μ − ⟨ P 2 f 1 , f 2 ⟩ μ + ⟨ P 1 f 1 , P 2 f 2 ⟩ μ = ⟨ f 1 , f 2 ⟩ μ + ⟨ P 1 f 1 , P 2 f 2 ⟩ μ = ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ f 1 ( c ) f 2 ( c ) + ⟨ P 1 f 1 , P 2 f 2 ⟩ μ . (18) Next, we note that
D 1 f = D 1 f S + D 1 f S ⊥ = f 1 − P 1 f 1 + f S ⊥ . (19) D_1f=D_1f_S+D_1f_S^\perp=f_1-P_1f_1+f_S^\perp. \tag*{(19)} D 1 f = D 1 f S + D 1 f S ⊥ = f 1 − P 1 f 1 + f S ⊥ . (19) which in turn shows that P ‾ 2 D 1 f = P ‾ 2 f 1 − P ‾ 2 P 1 f 1 + P ‾ 2 f S ⊥ = f 1 − P ‾ 2 P 1 f 1 \overline{P}_2D_1f=\overline{P}_2f_1-\overline{P}_2P_1f_1+\overline{P}_2f_S^\perp=f_1-\overline{P}_2P_1f_1 P 2 D 1 f = P 2 f 1 − P 2 P 1 f 1 + P 2 f S ⊥ = f 1 − P 2 P 1 f 1 P ‾ 1 D 2 f = f 2 − P ‾ 1 P 2 f 2 \overline{P}_1D_2f=f_2-\overline{P}_1P_2f_2 P 1 D 2 f = f 2 − P 1 P 2 f 2
Consequently, we have
1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 D 1 f ) ( c ) ⋅ ( P ‾ 1 D 2 f ) ( c ) = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 f 1 ( c ) f 2 ( c ) − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 f 1 ( c ) ⋅ ( P ‾ 1 P 2 f 2 ) ( c ) \begin{aligned}
\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P}_2D_1f)(c)\cdot(\overline{P}_1D_2f)(c) \\
&=\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}f_1(c)f_2(c)-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}f_1(c)\cdot(\overline{P}_1P_2f_2)(c)
\end{aligned} ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 D 1 f ) ( c ) ⋅ ( P 1 D 2 f ) ( c ) = ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ f 1 ( c ) f 2 ( c ) − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ f 1 ( c ) ⋅ ( P 1 P 2 f 2 ) ( c ) − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 P 1 f 1 ) ( c ) ⋅ f 2 ( c ) + 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 P 1 f 1 ) ( c ) ⋅ ( P ‾ 1 P 2 f 2 ) ( c ) = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 f 1 ( c ) f 2 ( c ) + ⟨ f 1 , P 1 P 2 f 2 ⟩ μ + ⟨ P 2 P 1 f 1 , f 2 ⟩ μ + 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 P 1 f 1 ) ( c ) ⋅ ( P ‾ 1 P 2 f 2 ) ( c ) = 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 f 1 ( c ) f 2 ( c ) + 2 ⟨ P 1 f 1 , P 2 f 2 ⟩ μ + 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 ( P ‾ 2 P 1 f 1 ) ( c ) ⋅ ( P ‾ 1 P 2 f 2 ) ( c ) . (20) \begin{aligned}
-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P}_2P_1f_1)(c)\cdot f_2(c)+\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P}_2P_1f_1)(c)\cdot(\overline{P}_1P_2f_2)(c) \\
&=\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}f_1(c)f_2(c)+\langle f_1,P_1P_2f_2\rangle_\mu+\langle P_2P_1f_1,f_2\rangle_\mu+\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P}_2P_1f_1)(c)\cdot(\overline{P}_1P_2f_2)(c) \\
&=\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}f_1(c)f_2(c)+2\langle P_1f_1,P_2f_2\rangle_\mu+\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}(\overline{P}_2P_1f_1)(c)\cdot(\overline{P}_1P_2f_2)(c). \tag*{(20)}
\end{aligned} − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 P 1 f 1 ) ( c ) ⋅ f 2 ( c ) + ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 P 1 f 1 ) ( c ) ⋅ ( P 1 P 2 f 2 ) ( c ) = ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ f 1 ( c ) f 2 ( c ) + ⟨ f 1 , P 1 P 2 f 2 ⟩ μ + ⟨ P 2 P 1 f 1 , f 2 ⟩ μ + ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 P 1 f 1 ) ( c ) ⋅ ( P 1 P 2 f 2 ) ( c ) = ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ f 1 ( c ) f 2 ( c ) + 2 ⟨ P 1 f 1 , P 2 f 2 ⟩ μ + ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ ( P 2 P 1 f 1 ) ( c ) ⋅ ( P 1 P 2 f 2 ) ( c ) . (20) where in the second equality we use (10) and that P ‾ 1 P 2 f 2 \overline{P}_1P_2f_2 P 1 P 2 f 2 L 2 ( μ ) L^2(\mu) L 2 ( μ ) P 1 P 2 f 2 P_1P_2f_2 P 1 P 2 f 2
Claim 4.4. For i ∈ { 1 , 2 } i\in\{1,2\} i ∈ { 1 , 2 }
∥ P i f i ∥ μ ≤ ∥ D i f i ∥ μ ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) − 1 . \|P_if_i\|_\mu\le\frac{\|D_if_i\|_\mu}{\sqrt{(\ell_1-1)(\ell_2-1)-1}}. ∥ P i f i ∥ μ ≤ ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) − 1 ∥ D i f i ∥ μ . Proof. We first relate ∥ P 1 f 1 ∥ μ \|P_1f_1\|_\mu ∥ P 1 f 1 ∥ μ ∥ f 1 ∥ μ \|f_1\|_\mu ∥ f 1 ∥ μ ∑ c ∈ L 1 f 1 ( c ) = 0 \sum_{c\in L_1}f_1(c)=0 ∑ c ∈ L 1 f 1 ( c ) = 0
P 1 f 1 ( c ) = { − f 1 ( c ) ℓ 1 − 1 , c ∈ L 1 ∩ L 2 , 0 , c ∈ L 2 ∖ L 1 , (21) P_1f_1(c)=
\begin{cases}
-\dfrac{f_1(c)}{\ell_1-1}, & c\in L_1\cap L_2,\\
0, & c\in L_2\setminus L_1,
\end{cases} \tag*{(21)} P 1 f 1 ( c ) = ⎩ ⎨ ⎧ − ℓ 1 − 1 f 1 ( c ) , 0 , c ∈ L 1 ∩ L 2 , c ∈ L 2 ∖ L 1 , (21) As such, we may write
∥ P 1 f 1 ∥ μ 2 = 1 ∣ Ω ∣ ( ℓ 1 − 1 ) ∑ c ∈ L 1 ∩ L 2 f 1 ( c ) 2 ≤ ∥ f 1 ∥ μ 2 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) . \|P_1f_1\|_\mu^2=\frac{1}{|\Omega|(\ell_1-1)}\sum_{c\in L_1\cap L_2}f_1(c)^2\le\frac{\|f_1\|_\mu^2}{(\ell_1-1)(\ell_2-1)}. ∥ P 1 f 1 ∥ μ 2 = ∣Ω∣ ( ℓ 1 − 1 ) 1 c ∈ L 1 ∩ L 2 ∑ f 1 ( c ) 2 ≤ ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ∥ f 1 ∥ μ 2 . where for the inequality we use P μ [ X 1 = c ] = ℓ 2 − 1 ∣ Ω ∣ \mathbb{P}_\mu[X_1=c]=\frac{\ell_2-1}{|\Omega|} P μ [ X 1 = c ] = ∣Ω∣ ℓ 2 − 1 c ∈ L 1 ∩ L 2 c\in L_1\cap L_2 c ∈ L 1 ∩ L 2
( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ∥ P 1 f 1 ∥ μ 2 ≤ ∥ f 1 ∥ μ 2 = P y t h a g o r a s ∥ D 1 f 1 ∥ μ 2 + ∥ P 1 f 1 ∥ μ 2 (\ell_1-1)(\ell_2-1)\lVert P_1f_1\rVert_\mu^2 \le\lVert f_1\rVert_\mu^2 \mathrel{=}_{\mathrm{Pythagoras}} \lVert D_1f_1\rVert_\mu^2+\lVert P_1f_1\rVert_\mu^2 ( ℓ 1 − 1 ) ( ℓ 2 − 1 ) ∥ P 1 f 1 ∥ μ 2 ≤ ∥ f 1 ∥ μ 2 = Pythagoras ∥ D 1 f 1 ∥ μ 2 + ∥ P 1 f 1 ∥ μ 2 which rearranges to the desired.
Claim 4.5. Let g 1 , g 2 ∈ L 2 ( μ ) g_1,g_2 \in L^2(\mu) g 1 , g 2 ∈ L 2 ( μ ) g 1 g_1 g 1 x 1 x_1 x 1 g 2 g_2 g 2 x 2 x_2 x 2 ∑ c ∈ L 1 g 1 ( c , ⋅ ) = 0 \sum_{c\in L_1}g_1(c,\cdot)=0 ∑ c ∈ L 1 g 1 ( c , ⋅ ) = 0
⟨ g 1 , g 2 ⟩ μ = − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 g 1 ( c , ⋅ ) g 2 ( ⋅ , c ) . \langle g_1,g_2\rangle_\mu=-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}g_1(c,\cdot)g_2(\cdot,c). ⟨ g 1 , g 2 ⟩ μ = − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ g 1 ( c , ⋅ ) g 2 ( ⋅ , c ) . The same conclusion would also hold if we instead only had ∑ c ∈ L 2 g 2 ( ⋅ , c ) = 0 \sum_{c\in L_2}g_2(\cdot,c)=0 ∑ c ∈ L 2 g 2 ( ⋅ , c ) = 0 g 1 ∈ R L 1 g_1\in\mathbb{R}^{L_1} g 1 ∈ R L 1 g 2 ∈ R L 2 g_2\in\mathbb{R}^{L_2} g 2 ∈ R L 2 g 1 ( x 1 , x 2 ) = g 1 ( x 1 ) g_1(x_1,x_2)=g_1(x_1) g 1 ( x 1 , x 2 ) = g 1 ( x 1 ) ( x 1 , x 2 ) ∈ Ω (x_1,x_2)\in\Omega ( x 1 , x 2 ) ∈ Ω
Proof. We may write
⟨ g 1 , g 2 ⟩ μ = 1 ∣ Ω ∣ [ ( ∑ x ∈ L 1 g 1 ( x , ⋅ ) ) ( ∑ y ∈ L 2 g 2 ( ⋅ , y ) ) − ∑ c ∈ L 1 ∩ L 2 g 1 ( c , ⋅ ) g 2 ( ⋅ , c ) ] = − 1 ∣ Ω ∣ ∑ c ∈ L 1 ∩ L 2 g 1 ( c , ⋅ ) g 2 ( ⋅ , c ) . \begin{aligned}
\langle g_1,g_2\rangle_\mu
&=\frac{1}{|\Omega|}\left[\left(\sum_{x\in L_1}g_1(x,\cdot)\right)\left(\sum_{y\in L_2}g_2(\cdot,y)\right)-\sum_{c\in L_1\cap L_2}g_1(c,\cdot)g_2(\cdot,c)\right]\\
&=-\frac{1}{|\Omega|}\sum_{c\in L_1\cap L_2}g_1(c,\cdot)g_2(\cdot,c).
\end{aligned} ⟨ g 1 , g 2 ⟩ μ = ∣Ω∣ 1 ( x ∈ L 1 ∑ g 1 ( x , ⋅ ) ) y ∈ L 2 ∑ g 2 ( ⋅ , y ) − c ∈ L 1 ∩ L 2 ∑ g 1 ( c , ⋅ ) g 2 ( ⋅ , c ) = − ∣Ω∣ 1 c ∈ L 1 ∩ L 2 ∑ g 1 ( c , ⋅ ) g 2 ( ⋅ , c ) . This completes the proof of Lemma 4.3.
Local Inequalities on Subgraphs under a Disallowed Color
In this section, we extend the machinery of the previous section to subgraphs H ⊂ G H\subset G H ⊂ G G ∖ H G\setminus H G ∖ H c c c H H H H H H cone ). Specifically, we will apply these inequalities to the leaves of such a cone.
First, we introduce some notation. We define the set of proper colorings avoiding c c c
Ω H − c = { x ∈ ∏ i ∈ H L i − c : x i ≠ x j for every i j ∈ E ( H ) } . \Omega_H^{-c}=\left\{\mathbf{x}\in\prod_{i\in H}L_i^{-c}:x_i\ne x_j\text{ for every }ij\in E(H)\right\}. Ω H − c = { x ∈ i ∈ H ∏ L i − c : x i = x j for every ij ∈ E ( H ) } . We define μ H − c \mu_H^{-c} μ H − c ( Ω H − c ) (\Omega_H^{-c}) ( Ω H − c ) L 2 ( μ H − c ) L^2(\mu_H^{-c}) L 2 ( μ H − c ) Ω H − c \Omega_H^{-c} Ω H − c P i H P_i^H P i H D i H D_i^H D i H Π i , c H \Pi_{i,c}^H Π i , c H L 2 ( μ H ) L^2(\mu_H) L 2 ( μ H ) D = ∑ i ∈ H D i H D=\sum_{i\in H}D_i^H D = ∑ i ∈ H D i H x i → a x^{i\to a} x i → a x x x i i i a a a
Fact 5.1. For every h ∈ L 2 ( μ H ) h\in L^2(\mu_H) h ∈ L 2 ( μ H ) c c c x ∈ Ω H − c x\in\Omega_H^{-c} x ∈ Ω H − c i ∈ H i\in H i ∈ H
E a ∼ L i − c − x N H ( i ) [ h ( x i → a ) ] − E a ∼ L i − c − x N H ( i ) [ h ( x i → a ) ] = ( Π i , c H h ) ( x ) . \mathbb{E}_{a\sim L_i^{-c-x^{N_H(i)}}}\left[h(x^{i\to a})\right]-\mathbb{E}_{a\sim L_i^{-c-x^{N_H(i)}}}\left[h(x^{i\to a})\right]=(\Pi_{i,c}^Hh)(x). E a ∼ L i − c − x N H ( i ) [ h ( x i → a ) ] − E a ∼ L i − c − x N H ( i ) [ h ( x i → a ) ] = ( Π i , c H h ) ( x ) . Proof. If c ∉ L i c \notin\mathcal{L}_i c ∈ / L i
E a ∼ L i − c − x N H ( i ) h ( x i → a ) − E a ∼ L i − x N H ( i ) h ( x i → a ) = − h ( x i → c ) − 1 ℓ i − x N H ( i ) ∑ a ∈ L i ℓ i − x N H ( i ) h ( x i → a ) ℓ i − x N H ( i ) − 1 = e i , c ( x ) ⋅ h ( x i → c ) − 1 ℓ i − x N H ( i ) ∑ a ∈ L i ℓ i − x N H ( i ) h ( x i → a ) ℓ i − x N H ( i ) − 1 = e i , c ( x ) ⋅ 1 ℓ i − x N H ( i ) ∑ a ∈ L i e i , c ( x i → a ) h ( x i → a ) = Π i , c h ( x ) . \begin{aligned}
\mathbb{E}_{a\sim\mathcal{L}_i^{-c-x_{N_H(i)}}} h(x^{i\to a})-\mathbb{E}_{a\sim\mathcal{L}_i^{-x_{N_H(i)}}} h(x^{i\to a})
=-\frac{h(x^{i\to c})-\frac{1}{\ell_i^{-x_{N_H(i)}}}\sum_{a\in\mathcal{L}_i} \ell_i^{-x_{N_H(i)}}h(x^{i\to a})}{\ell_i^{-x_{N_H(i)}}-1} \\
&=e_{i,c}(\mathbf{x})\cdot\frac{h(x^{i\to c})-\frac{1}{\ell_i^{-x_{N_H(i)}}}\sum_{a\in\mathcal{L}_i}\ell_i^{-x_{N_H(i)}}h(x^{i\to a})}{\sqrt{\ell_i^{-x_{N_H(i)}}-1}} \\
&=e_{i,c}(\mathbf{x})\cdot\frac{1}{\ell_i^{-x_{N_H(i)}}}\sum_{a\in\mathcal{L}_i}e_{i,c}(x^{i\to a})h(x^{i\to a}) \\
&=\Pi_{i,c}h(\mathbf{x}).
\end{aligned} E a ∼ L i − c − x N H ( i ) h ( x i → a ) − E a ∼ L i − x N H ( i ) h ( x i → a ) = − ℓ i − x N H ( i ) − 1 h ( x i → c ) − ℓ i − x N H ( i ) 1 ∑ a ∈ L i ℓ i − x N H ( i ) h ( x i → a ) = e i , c ( x ) ⋅ ℓ i − x N H ( i ) − 1 h ( x i → c ) − ℓ i − x N H ( i ) 1 ∑ a ∈ L i ℓ i − x N H ( i ) h ( x i → a ) = e i , c ( x ) ⋅ ℓ i − x N H ( i ) 1 a ∈ L i ∑ e i , c ( x i → a ) h ( x i → a ) = Π i , c h ( x ) . Lemma 5.2. For every h ∈ L 2 ( μ ) h\in L^2(\mu) h ∈ L 2 ( μ ) c ∈ ⋃ i ∈ V ( H ) L i c\in\bigcup_{i\in V(H)}\mathcal{L}_i c ∈ ⋃ i ∈ V ( H ) L i ℓ i ≥ s + deg H ( i ) \ell_i\ge s+\deg_H(i) ℓ i ≥ s + deg H ( i ) i ∈ H i\in H i ∈ H
E μ [ 1 { c ∉ X } ( ∑ i Π i , c h ( X ) ) 2 ] ≤ ( 1 − p ∗ 2 ) ∥ ∑ i Π i , c h ∥ μ 2 ≤ β ∣ H ∣ ∥ ∑ i Π i , c h ∥ μ 2 . \mathbb{E}_{\mu}\left[\mathbb{1}_{\{c\notin X\}}\left(\sum_i\Pi_{i,c}h(X)\right)^2\right]\le(1-p_*^2)\left\|\sum_i\Pi_{i,c}h\right\|_\mu^2\le\beta^{|H|}\left\|\sum_i\Pi_{i,c}h\right\|_\mu^2. E μ 1 { c ∈ / X } ( i ∑ Π i , c h ( X ) ) 2 ≤ ( 1 − p ∗ 2 ) i ∑ Π i , c h μ 2 ≤ β ∣ H ∣ i ∑ Π i , c h μ 2 . where p ∗ : = ( s − 1 s ) ∣ H ∣ p_*:=\left(\frac{s-1}{s}\right)^{|H|} p ∗ := ( s s − 1 ) ∣ H ∣
The main observation is to rule out the event that ∑ i Π i , c h ( x ) \sum_i\Pi_{i,c}h(\mathbf{x}) ∑ i Π i , c h ( x ) x \mathbf{x} x c ∉ X c\notin X c ∈ / X μ \mu μ Π i , c h ( x ) \Pi_{i,c}h(\mathbf{x}) Π i , c h ( x ) c ∉ X c\notin X c ∈ / X p ∗ p_* p ∗
Proof. We rewrite μ \mu μ c c c
We define Ω − c = { x ∈ Ω H : c ∉ x } \Omega^{-c}=\{\mathbf{x}\in\Omega_H:c\notin\mathbf{x}\} Ω − c = { x ∈ Ω H : c ∈ / x } p − c = P μ [ c ∉ X ] > 0 p_{-c}=\mathbb{P}_{\mu}[c\notin X]>0 p − c = P μ [ c ∈ / X ] > 0 μ − c = μ ( ⋅ ∣ c ∉ X ) \mu^{-c}=\mu(\mathord\cdot\mid c\notin X) μ − c = μ ( ⋅ ∣ c ∈ / X ) x ∈ Ω − c \mathbf{x}\in\Omega^{-c} x ∈ Ω − c
ν c , x ( y ) = ∏ i ∈ H [ 1 { y i = x i } ( 1 − p i , c ( x − i ) ) + 1 { y i = c } p i , c ( x − i ) ] , (22) \nu_{c,\mathbf{x}}(\mathbf{y})=\prod_{i\in H}\left[\mathbb{1}_{\{y_i=x_i\}}(1-p_{i,c}(\mathbf{x}_{-i}))+\mathbb{1}_{\{y_i=c\}}p_{i,c}(\mathbf{x}_{-i})\right], \tag*{(22)} ν c , x ( y ) = i ∈ H ∏ [ 1 { y i = x i } ( 1 − p i , c ( x − i )) + 1 { y i = c } p i , c ( x − i ) ] , (22) and we define π c , x = ν c , x ( ⋅ ∣ Y ∈ Ω H ) \pi_{c,\mathbf{x}}=\nu_{c,\mathbf{x}}(\mathord\cdot\mid Y\in\Omega_H) π c , x = ν c , x ( ⋅ ∣ Y ∈ Ω H ) x ∈ Ω H \mathbf{x}\in\Omega_H x ∈ Ω H c ∉ Y c\notin Y c ∈ / Y Y = x Y=\mathbf{x} Y = x
p − c ( x ) : = P π c , x ( c ∉ Y ) = ν c , x ( x ) ν c , x ( Ω H ) ≥ ∏ i ∈ H ( 1 − p i , c ( x − i ) ) ≥ ( s − 1 s ) ∣ H ∣ = p ∗ . (23) p_{-c}(\mathbf{x}):=\mathbb{P}_{\pi_{c,\mathbf{x}}}(c\notin Y)=\frac{\nu_{c,\mathbf{x}}(\mathbf{x})}{\nu_{c,\mathbf{x}}(\Omega_H)}
\ge\prod_{i\in H}(1-p_{i,c}(\mathbf{x}_{-i}))\ge\left(\frac{s-1}{s}\right)^{|H|}=p_*. \tag*{(23)} p − c ( x ) := P π c , x ( c ∈ / Y ) = ν c , x ( Ω H ) ν c , x ( x ) ≥ i ∈ H ∏ ( 1 − p i , c ( x − i )) ≥ ( s s − 1 ) ∣ H ∣ = p ∗ . (23) We claim that, for every function f : Ω H → R f:\Omega_H\to\mathbb{R} f : Ω H → R
E μ [ f ( Y ) ] = p − c E X ∼ μ − c [ 1 p − c ( X ) E Y ∼ π c , X [ f ( Y ) ] ] . (24) \mathbb{E}_{\mu}[f(Y)]=p_{-c}\mathbb{E}_{X\sim\mu^{-c}}\left[\frac{1}{p_{-c}(X)}\mathbb{E}_{Y\sim\pi_{c,X}}[f(Y)]\right]. \tag*{(24)} E μ [ f ( Y )] = p − c E X ∼ μ − c [ p − c ( X ) 1 E Y ∼ π c , X [ f ( Y )] ] . (24) For y ∈ Ω H \mathbf{y}\in\Omega_H y ∈ Ω H I y : = { i ∈ H : y i = c } I_{\mathbf{y}}:=\{i\in H:y_i=c\} I y := { i ∈ H : y i = c } y \mathbf{y} y I y I_{\mathbf{y}} I y H H H ν y \nu_{\mathbf{y}} ν y X \mathbf{X} X X i X_i X i L i − y N H ( i ) ∖ { c } \mathcal{L}_i^{-y_{N_H(i)}}\setminus\{c\} L i − y N H ( i ) ∖ { c } i ∈ I y i\in I_y i ∈ I y X i = y i X_i=y_i X i = y i i ∉ I y i\notin I_y i ∈ / I y x \mathbf{x} x i ∈ I y i\in I_y i ∈ I y x N H ( i ) = y N H ( i ) x_{N_H(i)}=y_{N_H(i)} x N H ( i ) = y N H ( i )
ν y ( x ) = ∏ i ∈ I y 1 ℓ i − y N H ( i ) − 1 = ν c , x ( y ) ν c , x ( x ) = π c , x ( y ) p − c ( x ) . \nu_y(\mathbf{x})=\prod_{i\in I_y}\frac{1}{\ell_i^{-y_{N_H(i)}}-1}=\frac{\nu_{c,\mathbf{x}}(\mathbf{y})}{\nu_{c,\mathbf{x}}(\mathbf{x})}=\frac{\pi_{c,\mathbf{x}}(\mathbf{y})}{p_{-c}(\mathbf{x})}. ν y ( x ) = i ∈ I y ∏ ℓ i − y N H ( i ) − 1 1 = ν c , x ( x ) ν c , x ( y ) = p − c ( x ) π c , x ( y ) . For x ∈ Ω − c \mathbf{x}\in\Omega^{-c} x ∈ Ω − c ν y \nu_y ν y ν y ( x ) \nu_y(\mathbf{x}) ν y ( x ) π c , x ( y ) \pi_{c,\mathbf{x}}(\mathbf{y}) π c , x ( y ) y ∈ Ω H \mathbf{y}\in\Omega_H y ∈ Ω H
p − c E X ∼ μ − c [ π c , X ( y ) p − c ( X ) ] = 1 ∣ Ω H ∣ ∑ x ∈ Ω − c ν y ( x ) = 1 ∣ Ω H ∣ = μ ( y ) , p_{-c}\mathbb{E}_{\mathbf{X}\sim\mu_{-c}}\left[\frac{\pi_{c,\mathbf{X}}(\mathbf{y})}{p_{-c}(\mathbf{X})}\right]=\frac{1}{|\Omega_H|}\sum_{\mathbf{x}\in\Omega^{-c}}\nu_y(\mathbf{x})=\frac{1}{|\Omega_H|}=\mu(\mathbf{y}), p − c E X ∼ μ − c [ p − c ( X ) π c , X ( y ) ] = ∣ Ω H ∣ 1 x ∈ Ω − c ∑ ν y ( x ) = ∣ Ω H ∣ 1 = μ ( y ) , where we used p − c = ∣ Ω − c ∣ ∣ Ω H ∣ p_{-c}=\frac{|\Omega^{-c}|}{|\Omega_H|} p − c = ∣ Ω H ∣ ∣ Ω − c ∣
Since Y = X \mathbf{Y}=\mathbf{X} Y = X c ∉ Y c\notin Y c ∈ / Y g c ( x ) = ∑ i Π i , c h ( x ) g_c(\mathbf{x})=\sum_i\Pi_{i,c}h(\mathbf{x}) g c ( x ) = ∑ i Π i , c h ( x )
E Y ∼ μ [ I { c ∉ Y } g c ( Y ) 2 ] = p − c E X ∼ μ − c [ g c ( X ) 2 ] = p − c E X ∼ μ − c [ 1 p − c ( X ) 2 ( E π c , X [ I { c ∉ Y } g c ( Y ) ] ) 2 ] = ∀ i : E π c , X [ Π i , c h ∣ Y − i ] = 0 p − c E X ∼ μ − c [ 1 p − c ( X ) 2 ( E π c , X [ ( I { c ∉ Y } − p − c ( X ) ) g c ( Y ) ] ) 2 ] ≤ Cauchy–Schwarz p − c E X ∼ μ − c [ 1 − p − c ( X ) p − c ( X ) E π c , X [ g c ( Y ) 2 ] ] ≤ ( 21 ) ( 1 − p ∗ ) p − c E X ∼ μ − c [ 1 p − c ( X ) E π c , X [ g c ( Y ) 2 ] ] = ( 22 ) ( 1 − p ∗ ) E μ [ g c ( X ) 2 ] . \begin{aligned}
\mathbb{E}_{\mathbf{Y}\sim\mu}\left[\mathbb{I}\{c\notin Y\}g_c(\mathbf{Y})^2\right]
&=p_{-c}\mathbb{E}_{\mathbf{X}\sim\mu_{-c}}\left[g_c(\mathbf{X})^2\right]\\
&=p_{-c}\mathbb{E}_{\mathbf{X}\sim\mu_{-c}}\left[\frac{1}{p_{-c}(\mathbf{X})^2}\left(\mathbb{E}_{\pi_{c,\mathbf{X}}}\left[\mathbb{I}\{c\notin Y\}g_c(\mathbf{Y})\right]\right)^2\right]\\
&\underset{\forall i:\mathbb{E}_{\pi_{c,\mathbf{X}}}[\Pi_{i,c}h\mid Y_{-i}]=0}{=}
p_{-c}\mathbb{E}_{\mathbf{X}\sim\mu_{-c}}\left[\frac{1}{p_{-c}(\mathbf{X})^2}\left(\mathbb{E}_{\pi_{c,\mathbf{X}}}\left[(\mathbb{I}\{c\notin Y\}-p_{-c}(\mathbf{X}))g_c(\mathbf{Y})\right]\right)^2\right]\\
&\underset{\text{Cauchy--Schwarz}}{\leq}
p_{-c}\mathbb{E}_{\mathbf{X}\sim\mu_{-c}}\left[\frac{1-p_{-c}(\mathbf{X})}{p_{-c}(\mathbf{X})}\mathbb{E}_{\pi_{c,\mathbf{X}}}\left[g_c(\mathbf{Y})^2\right]\right]\\
&\underset{(21)}{\leq}
(1-p^*)p_{-c}\mathbb{E}_{\mathbf{X}\sim\mu_{-c}}\left[\frac{1}{p_{-c}(\mathbf{X})}\mathbb{E}_{\pi_{c,\mathbf{X}}}\left[g_c(\mathbf{Y})^2\right]\right]\\
&\underset{(22)}{=}(1-p^*)\mathbb{E}_{\mu}\left[g_c(\mathbf{X})^2\right].
\end{aligned} E Y ∼ μ [ I { c ∈ / Y } g c ( Y ) 2 ] = p − c E X ∼ μ − c [ g c ( X ) 2 ] = p − c E X ∼ μ − c [ p − c ( X ) 2 1 ( E π c , X [ I { c ∈ / Y } g c ( Y ) ] ) 2 ] ∀ i : E π c , X [ Π i , c h ∣ Y − i ] = 0 = p − c E X ∼ μ − c [ p − c ( X ) 2 1 ( E π c , X [ ( I { c ∈ / Y } − p − c ( X )) g c ( Y ) ] ) 2 ] Cauchy–Schwarz ≤ p − c E X ∼ μ − c [ p − c ( X ) 1 − p − c ( X ) E π c , X [ g c ( Y ) 2 ] ] ( 21 ) ≤ ( 1 − p ∗ ) p − c E X ∼ μ − c [ p − c ( X ) 1 E π c , X [ g c ( Y ) 2 ] ] ( 22 ) = ( 1 − p ∗ ) E μ [ g c ( X ) 2 ] . Local Inequalities on Cones
In this section we prove Theorem 1.6. Before doing that we set up some notation.
Let H = { v } ∪ H ′ H=\{v\}\cup H' H = { v } ∪ H ′ v v v
Ω H ′ : = { x H ′ : x ∈ Ω } and Ω H ′ − c : = { x ∈ Ω H ′ : c ∉ x } . \Omega_{H'}:=\{\mathbf{x}_{H'}:\mathbf{x}\in\Omega\}\qquad\text{and}\qquad\Omega_{H'}^{-c}:=\{\mathbf{x}\in\Omega_{H'}:c\notin\mathbf{x}\}. Ω H ′ := { x H ′ : x ∈ Ω } and Ω H ′ − c := { x ∈ Ω H ′ : c ∈ / x } . We will often abuse notation and identify a leaf function h : Ω H ′ → R h:\Omega_{H'}\to\mathbb{R} h : Ω H ′ → R ( c , x ) ↦ h ( x ) (c,\mathbf{x})\mapsto h(\mathbf{x}) ( c , x ) ↦ h ( x ) Ω \Omega Ω x − i x_{-i} x − i h i ( a ) = h ( x − i , a ) h_i(a)=h(x_{-i},a) h i ( a ) = h ( x − i , a )
Let μ H ′ − v \mu_{H'}^{-v} μ H ′ − v ∏ i L i \prod_i\mathcal{L}_i ∏ i L i H H H u i u_i u i v v v H H H x \mathbf{x} x ℓ v − x \ell_v^{-\mathbf{x}} ℓ v − x μ H ′ − v \mu_{H'}^{-v} μ H ′ − v c ∈ L v − x c\in\mathcal{L}_v^{-\mathbf{x}} c ∈ L v − x
We further define the operators D − v , H ′ D^{-v,H'} D − v , H ′ Π i , c − v , H ′ \Pi_{i,c}^{-v,H'} Π i , c − v , H ′ L 2 ( μ H ′ − v ) L^2(\mu_{H'}^{-v}) L 2 ( μ H ′ − v )
Throughout the section, unless otherwise specified, we write D u = D u H D_u = D_u^H D u = D u H P u = P u H P_u = P_u^H P u = P u H u ∈ H u \in H u ∈ H D H ′ = ∑ i ∈ H ′ D i D_{H'} = \sum_{i\in H'} D_i D H ′ = ∑ i ∈ H ′ D i H H H h : Ω H → R h : \Omega_H \to\mathbb{R} h : Ω H → R v v v h h h D H ′ h D_{H'}h D H ′ h
Theorem 1.6 (Main Technical Theorem). For any t > 0 t > 0 t > 0 H = { v } ∪ H ′ H = \{v\} \cup H' H = { v } ∪ H ′ v v v H ′ H' H ′ ∣ H ′ ∣ = d |H'| = d ∣ H ′ ∣ = d s ≥ 5 s \ge5 s ≥ 5 ∣ L i ∣ ≥ s + deg H ( i ) |\mathcal{L}_i| \ge s + \deg_H(i) ∣ L i ∣ ≥ s + deg H ( i ) i ∈ H i \in H i ∈ H
2 ⟨ D v f , D H ′ f ⟩ μ + t ∥ D v f ∥ μ 2 + β d t ( s − 1 ) ∥ D H ′ f ∥ μ 2 + O ( Δ t s 3 ) ⟨ f , D H ′ f ⟩ μ ≥ 0. 2\langle D_v f,D_{H'}f\rangle_\mu+ t\|D_v f\|_\mu^2 + \frac{\beta_d}{t(s-1)}\|D_{H'}f\|_\mu^2 + O\left(\frac{\Delta}{ts^3}\right)\langle f,D_{H'}f\rangle_\mu\ge0. 2 ⟨ D v f , D H ′ f ⟩ μ + t ∥ D v f ∥ μ 2 + t ( s − 1 ) β d ∥ D H ′ f ∥ μ 2 + O ( t s 3 Δ ) ⟨ f , D H ′ f ⟩ μ ≥ 0. where D H ′ = ∑ i ∈ H ′ D i D_{H'} = \sum_{i\in H'} D_i D H ′ = ∑ i ∈ H ′ D i β d = 1 − ( s − 1 s ) d \beta_d = 1 - \left(\frac{s-1}{s}\right)^d β d = 1 − ( s s − 1 ) d
Proof of Theorem 1.6. In the first step we “decouple” the action of leaf update D H ′ D_{H'} D H ′ h ∗ h^* h ∗
h ∗ : = arg min h l e a f f u n c t i o n ⟨ f − h , D H ′ ( f − h ) ⟩ μ = arg min h l e a f f u n c t i o n ∑ i ∈ H ′ ∥ D i ( f − h ) ∥ μ 2 . (25) h^* := \underset{h\ \mathrm{leaf\ function}}{\arg\min}\ \langle f-h,D_{H'}(f-h)\rangle_\mu
= \underset{h\ \mathrm{leaf\ function}}{\arg\min}\ \sum_{i\in H'}\|D_i(f-h)\|_\mu^2. \tag*{(25)} h ∗ := h leaf function arg min ⟨ f − h , D H ′ ( f − h ) ⟩ μ = h leaf function arg min i ∈ H ′ ∑ ∥ D i ( f − h ) ∥ μ 2 . (25) Letting g = f − h ∗ g=f-h^* g = f − h ∗ D H ′ g D_{H'}g D H ′ g
P v D H ′ g = 0. (26) P_vD_{H'}g=0. \tag*{(26)} P v D H ′ g = 0. (26) Having this, it follows that
P v D H ′ h ∗ = P v D H ′ f and ⟨ h ∗ , D H ′ g ⟩ μ h ∗ l e a f f u n c t i o n = ⟨ P v h ∗ , D H ′ g ⟩ = 0 , (27) P_vD_{H'}h^*=P_vD_{H'}f
\quad\text{and}\quad
\underset{h^*\ \mathrm{leaf\ function}}{\langle h^*,D_{H'}g\rangle_\mu}
=\langle P_vh^*,D_{H'}g\rangle=0, \tag*{(27)} P v D H ′ h ∗ = P v D H ′ f and h ∗ leaf function ⟨ h ∗ , D H ′ g ⟩ μ = ⟨ P v h ∗ , D H ′ g ⟩ = 0 , (27) and consequently
⟨ f , D H ′ f ⟩ μ = ⟨ h ∗ , D H ′ h ∗ ⟩ μ + ⟨ g , D H ′ g ⟩ μ ≥ ⟨ h ∗ , D H ′ h ∗ ⟩ μ . \langle f,D_{H'}f\rangle_\mu
=\langle h^*,D_{H'}h^*\rangle_\mu+\langle g,D_{H'}g\rangle_\mu
\ge\langle h^*,D_{H'}h^*\rangle_\mu. ⟨ f , D H ′ f ⟩ μ = ⟨ h ∗ , D H ′ h ∗ ⟩ μ + ⟨ g , D H ′ g ⟩ μ ≥ ⟨ h ∗ , D H ′ h ∗ ⟩ μ . Having decoupled g , h ∗ g,h^* g , h ∗
2 ⟨ D v f , D H ′ f ⟩ μ = D v 2 = D v D v i s s e l f - a d j o i n t 2 ⟨ D v f , D v D H ′ h ∗ ⟩ μ + 2 ⟨ g , D v D H ′ g ⟩ μ = 2 ⟨ D v f , D v D H ′ h ∗ ⟩ μ + 2 ⟨ g , D H ′ g ⟩ μ . (28) \begin{aligned}
2\langle D_vf,D_{H'}f\rangle_\mu
\underset{\substack{D_v^2=D_v\\D_v\ \mathrm{is\ self\text{-}adjoint}}}{=}
2\langle D_vf,D_vD_{H'}h^*\rangle_\mu+2\langle g,D_vD_{H'}g\rangle_\mu\\
&=2\langle D_vf,D_vD_{H'}h^*\rangle_\mu+2\langle g,D_{H'}g\rangle_\mu. \tag*{(28)}
\end{aligned} 2 ⟨ D v f , D H ′ f ⟩ μ D v 2 = D v D v is self - adjoint = 2 ⟨ D v f , D v D H ′ h ∗ ⟩ μ + 2 ⟨ g , D v D H ′ g ⟩ μ = 2 ⟨ D v f , D v D H ′ h ∗ ⟩ μ + 2 ⟨ g , D H ′ g ⟩ μ . (28) Since D H ′ D_{H'} D H ′ μ \mu μ ⟨ D v f , D v D H ′ h ∗ ⟩ μ \langle D_vf,D_vD_{H'}h^*\rangle_\mu ⟨ D v f , D v D H ′ h ∗ ⟩ μ α : = β d s − 1 \alpha:=\frac{\beta_d}{s-1} α := s − 1 β d f f f
2 ( 1 − α ) ⋅ ⟨ D v f , D H ′ f ⟩ μ ≥ 2 ⟨ D v f , ( 1 − α ) D v D H ′ h ∗ ⟩ μ ≥ − ( 1 − α ) ( t ∥ D v f ∥ μ 2 + 1 t ∥ D v D H ′ h ∗ ∥ μ 2 ) , 2(1-\alpha)\cdot\langle D_vf,D_{H'}f\rangle_\mu
\ge2\langle D_vf,(1-\alpha)D_vD_{H'}h^*\rangle_\mu
\ge-(1-\alpha)\left(t\|D_vf\|_\mu^2+\frac{1}{t}\|D_vD_{H'}h^*\|_\mu^2\right), 2 ( 1 − α ) ⋅ ⟨ D v f , D H ′ f ⟩ μ ≥ 2 ⟨ D v f , ( 1 − α ) D v D H ′ h ∗ ⟩ μ ≥ − ( 1 − α ) ( t ∥ D v f ∥ μ 2 + t 1 ∥ D v D H ′ h ∗ ∥ μ 2 ) , where the second inequality uses the fact that, for any two vectors x , y \mathbf{x},\mathbf{y} x , y 2 ⟨ x , y ⟩ ≥ − t ∥ x ∥ 2 − ∥ y ∥ 2 t 2\langle\mathbf{x},\mathbf{y}\rangle\ge-t\|\mathbf{x}\|^2-\frac{\|\mathbf{y}\|^2}{t} 2 ⟨ x , y ⟩ ≥ − t ∥ x ∥ 2 − t ∥ y ∥ 2 ∥ D v D H ′ h ∗ ∥ μ 2 \|D_vD_{H'}h^*\|_\mu^2 ∥ D v D H ′ h ∗ ∥ μ 2 D H ′ h ∗ D_{H'}h^* D H ′ h ∗ D v D H ′ h ∗ = 0 D_vD_{H'}h^*=0 D v D H ′ h ∗ = 0 Proposition 6.1 (below) it is not really too far from being a leaf function.
≥ − ( 1 − α ) t ∥ D v f ∥ μ 2 − α t ∥ P v D H ′ h ∗ ∥ μ 2 − O ( Δ t s 3 ) ⟨ h ∗ , D H ′ h ∗ ⟩ μ ≥ − ( 1 − α ) t ∥ D v f ∥ μ 2 − α t ∥ P v D H ′ f ∥ μ 2 − O ( Δ t s 3 ) ⟨ f , D H ′ f ⟩ μ \begin{aligned}
\ge-(1-\alpha)t\lVert D_vf\rVert_\mu^2-\frac{\alpha}{t}\lVert P_vD_{H'}h^*\rVert_\mu^2-O\left(\frac{\Delta}{t s^3}\right)\langle h^*,D_{H'}h^*\rangle_\mu\\
&\ge-(1-\alpha)t\lVert D_vf\rVert_\mu^2-\frac{\alpha}{t}\lVert P_vD_{H'}f\rVert_\mu^2-O\left(\frac{\Delta}{t s^3}\right)\langle f,D_{H'}f\rangle_\mu
\end{aligned} ≥ − ( 1 − α ) t ∥ D v f ∥ μ 2 − t α ∥ P v D H ′ h ∗ ∥ μ 2 − O ( t s 3 Δ ) ⟨ h ∗ , D H ′ h ∗ ⟩ μ ≥ − ( 1 − α ) t ∥ D v f ∥ μ 2 − t α ∥ P v D H ′ f ∥ μ 2 − O ( t s 3 Δ ) ⟨ f , D H ′ f ⟩ μ On the other hand, by another AM-GM on ⟨ D v f , D v D H ′ f ⟩ μ \langle D_vf,D_vD_{H'}f\rangle_\mu ⟨ D v f , D v D H ′ f ⟩ μ
2 α ⟨ D v f , D v D H ′ f ⟩ ≥ − α t ∥ D v f ∥ μ 2 − α t ∥ D v D H ′ f ∥ μ 2 2\alpha\langle D_vf,D_vD_{H'}f\rangle\ge-\alpha t\lVert D_vf\rVert_\mu^2-\frac{\alpha}{t}\lVert D_vD_{H'}f\rVert_\mu^2 2 α ⟨ D v f , D v D H ′ f ⟩ ≥ − α t ∥ D v f ∥ μ 2 − t α ∥ D v D H ′ f ∥ μ 2 Summing up the above two inequalities proves the theorem.
It remains to prove (24). Let ε ∈ R \varepsilon\in\mathbb{R} ε ∈ R ℓ \ell ℓ h ∗ h^* h ∗
0 = d d ε ⟨ f − h ∗ − ε ℓ , D H ′ ( f − h ∗ − ε ℓ ) ⟩ μ ∣ ε = 0 = − 2 ⟨ ℓ , D H ′ ( f − h ∗ ) ⟩ μ = − 2 ⟨ ℓ , D H ′ g ⟩ μ . 0=\left.\frac{d}{d\varepsilon}\langle f-h^*-\varepsilon\ell,D_{H'}(f-h^*-\varepsilon\ell)\rangle_\mu\right|_{\varepsilon=0}=-2\langle\ell,D_{H'}(f-h^*)\rangle_\mu=-2\langle\ell,D_{H'}g\rangle_\mu. 0 = d ε d ⟨ f − h ∗ − ε ℓ , D H ′ ( f − h ∗ − ε ℓ ) ⟩ μ ε = 0 = − 2 ⟨ ℓ , D H ′ ( f − h ∗ ) ⟩ μ = − 2 ⟨ ℓ , D H ′ g ⟩ μ . This shows that D H ′ g D_{H'}g D H ′ g h h h
⟨ ( I − D v ) h , D H ′ g ⟩ μ = ⟨ h , ( I − D v ) D H ′ g ⟩ μ = 0. \langle(I-D_v)h,D_{H'}g\rangle_\mu=\langle h,(I-D_v)D_{H'}g\rangle_\mu=0. ⟨( I − D v ) h , D H ′ g ⟩ μ = ⟨ h , ( I − D v ) D H ′ g ⟩ μ = 0. Since the choice of h h h ( I − D v ) D H ′ g = 0 (I-D_v)D_{H'}g=0 ( I − D v ) D H ′ g = 0
The main statement we needed in the above proof is the following proposition which we will prove in the rest of this section. It says that for any leaf function h h h D h Dh D h D h Dh D h D v D h = 0 D_vDh=0 D v D h = 0
Proposition 6.1. Let H = { v } ∪ H ′ H=\{v\}\cup H' H = { v } ∪ H ′ u ∈ H u\in H u ∈ H ℓ u ≥ s + deg H ( u ) \ell_u\ge s+\deg_H(u) ℓ u ≥ s + deg H ( u ) s ≥ 5 s\ge5 s ≥ 5 h h h
( 1 − β d s − 1 ) ∥ D v D H ′ h ∥ μ 2 ≤ β d s − 1 ∥ P v D H ′ h ∥ μ 2 + O ( Δ s 3 ) ⟨ h , D H ′ h ⟩ μ , \left(1-\frac{\beta_d}{s-1}\right)\lVert D_vD_{H'}h\rVert_\mu^2\le\frac{\beta_d}{s-1}\lVert P_vD_{H'}h\rVert_\mu^2+O\left(\frac{\Delta}{s^3}\right)\langle h,D_{H'}h\rangle_\mu, ( 1 − s − 1 β d ) ∥ D v D H ′ h ∥ μ 2 ≤ s − 1 β d ∥ P v D H ′ h ∥ μ 2 + O ( s 3 Δ ) ⟨ h , D H ′ h ⟩ μ , where d = ∣ H ′ ∣ d=|H'| d = ∣ H ′ ∣
We first construct a leaf function approximating D H ′ h D_{H'}h D H ′ h
Lemma 6.2 (D H ′ h D_{H'}h D H ′ h H = { v } ∪ H ′ H=\{v\}\cup H' H = { v } ∪ H ′ u ∈ H u\in H u ∈ H ℓ u ≥ s + deg H ( u ) \ell_u\ge s+\deg_H(u) ℓ u ≥ s + deg H ( u ) s ≥ 5 s\ge5 s ≥ 5 h h h h ′ h' h ′
∥ h ′ − D H ′ h ∥ μ 2 ≤ β d s − 1 ∥ h ′ ∥ μ 2 + O ( 1 s 3 ) ∑ i ∈ H ′ deg H ′ ( i ) ∥ D i h ∥ μ 2 , \lVert h'-D_{H'}h\rVert_\mu^2\le\frac{\beta_d}{s-1}\lVert h'\rVert_\mu^2+O\left(\frac{1}{s^3}\right)\sum_{i\in H'}\deg_{H'}(i)\lVert D_ih\rVert_\mu^2, ∥ h ′ − D H ′ h ∥ μ 2 ≤ s − 1 β d ∥ h ′ ∥ μ 2 + O ( s 3 1 ) i ∈ H ′ ∑ deg H ′ ( i ) ∥ D i h ∥ μ 2 , where d = ∣ H ′ ∣ d=|H'| d = ∣ H ′ ∣
Assuming Lemma 6.2, we prove Proposition 6.1.
Proof of Proposition 6.1. We let h ′ h' h ′ D v h ′ = 0 D_vh'=0 D v h ′ = 0 D v D_v D v
∥ D v D H ′ h ′ ∥ μ 2 = ∥ D v ( D H ′ h ′ − ( 1 − β d s − 1 ) h ′ ) ∥ μ 2 ≤ ∥ D H ′ h ′ − ( 1 − β d s − 1 ) h ′ ∥ μ 2 = β d s − 1 ∥ D H ′ h ′ ∥ μ 2 + ( 1 − β d s − 1 ) [ ∥ D H ′ h ′ − h ′ ∥ μ 2 − β d s − 1 ∥ h ′ ∥ μ 2 ] ≤ β d s − 1 ∥ D H ′ h ′ ∥ μ 2 + O ( 1 s 3 ) ∑ i ∈ H ′ deg H ′ ( i ) ∥ D i h ′ ∥ μ 2 . \begin{aligned}
\|D_vD_{H'}h'\|_{\mu}^{2}
&= \left\|D_v\left(D_{H'}h'-\left(1-\frac{\beta_d}{s-1}\right)h'\right)\right\|_{\mu}^{2}\\
&\le\left\|D_{H'}h'-\left(1-\frac{\beta_d}{s-1}\right)h'\right\|_{\mu}^{2}\\
&= \frac{\beta_d}{s-1}\|D_{H'}h'\|_{\mu}^{2}
+\left(1-\frac{\beta_d}{s-1}\right)\left[\|D_{H'}h'-h'\|_{\mu}^{2}-\frac{\beta_d}{s-1}\|h'\|_{\mu}^{2}\right]\\
&\le\frac{\beta_d}{s-1}\|D_{H'}h'\|_{\mu}^{2}
+O\left(\frac{1}{s^{3}}\right)\sum_{i\in H'}\deg_{H'}(i)\|D_ih'\|_{\mu}^{2}.
\end{aligned} ∥ D v D H ′ h ′ ∥ μ 2 = D v ( D H ′ h ′ − ( 1 − s − 1 β d ) h ′ ) μ 2 ≤ D H ′ h ′ − ( 1 − s − 1 β d ) h ′ μ 2 = s − 1 β d ∥ D H ′ h ′ ∥ μ 2 + ( 1 − s − 1 β d ) [ ∥ D H ′ h ′ − h ′ ∥ μ 2 − s − 1 β d ∥ h ′ ∥ μ 2 ] ≤ s − 1 β d ∥ D H ′ h ′ ∥ μ 2 + O ( s 3 1 ) i ∈ H ′ ∑ deg H ′ ( i ) ∥ D i h ′ ∥ μ 2 . Finally, each D i D_i D i D H ′ = ∑ i ∈ H ′ D i D_{H'}=\sum_{i\in H'}D_i D H ′ = ∑ i ∈ H ′ D i
∑ i ∈ H ′ deg H ′ ( i ) ∥ D i h ′ ∥ μ 2 ≤ Δ ∑ i ∈ H ′ ∥ D i h ′ ∥ μ 2 = Δ ⟨ h ′ , D H ′ h ′ ⟩ μ . \sum_{i\in H'}\deg_{H'}(i)\|D_ih'\|_{\mu}^{2}
\le\Delta\sum_{i\in H'}\|D_ih'\|_{\mu}^{2}
=\Delta\langle h',D_{H'}h'\rangle_{\mu}. i ∈ H ′ ∑ deg H ′ ( i ) ∥ D i h ′ ∥ μ 2 ≤ Δ i ∈ H ′ ∑ ∥ D i h ′ ∥ μ 2 = Δ ⟨ h ′ , D H ′ h ′ ⟩ μ . Consequently,
∥ D v D H ′ h ′ ∥ μ 2 ≤ β d s − 1 ∥ D H ′ h ′ ∥ μ 2 + O ( Δ s 3 ) ⟨ h ′ , D H ′ h ′ ⟩ μ = β d s − 1 ( ∥ D v D H ′ h ′ ∥ μ 2 + ∥ P v D H ′ h ′ ∥ μ 2 ) + O ( Δ s 3 ) ⟨ h ′ , D H ′ h ′ ⟩ μ . \begin{aligned}
\|D_vD_{H'}h'\|_{\mu}^{2}
\le\frac{\beta_d}{s-1}\|D_{H'}h'\|_{\mu}^{2}
+O\left(\frac{\Delta}{s^{3}}\right)\langle h',D_{H'}h'\rangle_{\mu} \\
&= \frac{\beta_d}{s-1}\left(\|D_vD_{H'}h'\|_{\mu}^{2}
+\|P_vD_{H'}h'\|_{\mu}^{2}\right)
+O\left(\frac{\Delta}{s^{3}}\right)\langle h',D_{H'}h'\rangle_{\mu}.
\end{aligned} ∥ D v D H ′ h ′ ∥ μ 2 ≤ s − 1 β d ∥ D H ′ h ′ ∥ μ 2 + O ( s 3 Δ ) ⟨ h ′ , D H ′ h ′ ⟩ μ = s − 1 β d ( ∥ D v D H ′ h ′ ∥ μ 2 + ∥ P v D H ′ h ′ ∥ μ 2 ) + O ( s 3 Δ ) ⟨ h ′ , D H ′ h ′ ⟩ μ . Rearranging proves the desired inequality.
Next, before proving Lemma 6.2, we compare ∥ D i − v , H ′ h ′ ∥ μ H ′ − v 2 \|D_i^{-v,H'}h'\|_{\mu_{H'}^{-v}}^{2} ∥ D i − v , H ′ h ′ ∥ μ H ′ − v 2 ∥ D i h ′ ∥ μ 2 \|D_ih'\|_{\mu}^{2} ∥ D i h ′ ∥ μ 2
Claim 6.3. If ℓ v ≥ s + ∣ H ′ ∣ \ell_v\ge s+|H'| ℓ v ≥ s + ∣ H ′ ∣ h h h i ∈ H ′ i\in H' i ∈ H ′
∣ Ω H ′ ∣ ∣ Ω ∣ ∥ D i − v , H ′ h ∥ μ H ′ − v 2 ≤ 1 s − 1 ⋅ ∥ D i h ∥ μ 2 . \frac{|\Omega_{H'}|}{|\Omega|}\|D_i^{-v,H'}h\|_{\mu_{H'}^{-v}}^{2}
\le\frac{1}{s-1}\cdot\|D_ih\|_{\mu}^{2}. ∣Ω∣ ∣ Ω H ′ ∣ ∥ D i − v , H ′ h ∥ μ H ′ − v 2 ≤ s − 1 1 ⋅ ∥ D i h ∥ μ 2 . Proof. Fix i i i x − i \mathbf{x}_{-i} x − i
∑ c ∈ L v − x − i ∑ a ∈ L i − x N H ′ ( i ) ( D i h ) ( c , x − i , a ) 2 = ∑ c ∈ L v − x − i 1 2 ℓ i − x N H ′ ( i ) ∑ a , b ∈ L i − x N H ′ ( i ) ( h ( x i → a ) − h ( x i → b ) ) 2 ≥ 1 2 ∑ a , b ∈ L i − x N H ′ ( i ) ( h ( x i → a ) − h ( x i → b ) ) 2 ∑ c ∈ L v − x − i 1 ℓ i − x − i , − a , − b , x − i ≥ s − 1 2 ℓ i − x N H ′ ( i ) ∑ a , b ∈ L i − x N H ′ ( i ) ( h ( x i → a ) − h ( x i → b ) ) 2 = ( s − 1 ) ∑ a ∈ L i − x N H ′ ( i ) ( D i − v , H ′ h ) ( x − i , a ) 2 . \begin{aligned}
\sum_{c\in\mathcal{L}_v^{-\mathbf{x}_{-i}}}\sum_{a\in\mathcal{L}_i^{-\mathbf{x}_{N H'(i)}}}(D_ih)(c,\mathbf{x}_{-i},a)^2
&=\sum_{c\in\mathcal{L}_v^{-\mathbf{x}_{-i}}}\frac{1}{2\ell_i^{-\mathbf{x}_{N H'(i)}}}
\sum_{a,b\in\mathcal{L}_i^{-\mathbf{x}_{N H'(i)}}}
\left(h(\mathbf{x}^{i\to a})-h(\mathbf{x}^{i\to b})\right)^2\\
&\ge\frac{1}{2}\sum_{a,b\in\mathcal{L}_i^{-\mathbf{x}_{N H'(i)}}}
\left(h(\mathbf{x}^{i\to a})-h(\mathbf{x}^{i\to b})\right)^2
\sum_{c\in\mathcal{L}_v^{-\mathbf{x}_{-i}}}
\frac{1}{\ell_i^{-\mathbf{x}_{-i},-a,-b,\mathbf{x}_{-i}}}\\
&\ge\frac{s-1}{2\ell_i^{-\mathbf{x}_{N H'(i)}}}
\sum_{a,b\in\mathcal{L}_i^{-\mathbf{x}_{N H'(i)}}}
\left(h(\mathbf{x}^{i\to a})-h(\mathbf{x}^{i\to b})\right)^2\\
&=(s-1)\sum_{a\in\mathcal{L}_i^{-\mathbf{x}_{N H'(i)}}}
(D_i^{-v,H'}h)(\mathbf{x}_{-i},a)^2.
\end{aligned} c ∈ L v − x − i ∑ a ∈ L i − x N H ′ ( i ) ∑ ( D i h ) ( c , x − i , a ) 2 = c ∈ L v − x − i ∑ 2 ℓ i − x N H ′ ( i ) 1 a , b ∈ L i − x N H ′ ( i ) ∑ ( h ( x i → a ) − h ( x i → b ) ) 2 ≥ 2 1 a , b ∈ L i − x N H ′ ( i ) ∑ ( h ( x i → a ) − h ( x i → b ) ) 2 c ∈ L v − x − i ∑ ℓ i − x − i , − a , − b , x − i 1 ≥ 2 ℓ i − x N H ′ ( i ) s − 1 a , b ∈ L i − x N H ′ ( i ) ∑ ( h ( x i → a ) − h ( x i → b ) ) 2 = ( s − 1 ) a ∈ L i − x N H ′ ( i ) ∑ ( D i − v , H ′ h ) ( x − i , a ) 2 . In the expression on the LHS we use the vector ( c , x − i , a ) (c,\mathbf{x}_{-i},a) ( c , x − i , a ) v v v c c c i i i a a a x − i \mathbf{x}_{-i} x − i x − i \mathbf{x}_{-i} x − i
∣ Ω ∣ ∥ D i h ∥ μ 2 ≥ ( s − 1 ) ∣ Ω H ′ ∣ ∥ D i − v , H ′ h ∥ μ H ′ − v 2 |\Omega|\lVert D_i h\rVert_{\mu}^{2} \ge(s-1)|\Omega_{H'}|\lVert D_i^{-v,H'}h\rVert_{\mu_{H'}^{-v}}^{2} ∣Ω∣ ∥ D i h ∥ μ 2 ≥ ( s − 1 ) ∣ Ω H ′ ∣ ∥ D i − v , H ′ h ∥ μ H ′ − v 2 Rearranging proves the desired claim.
Proof of Lemma 6.2. We claim that h ′ : = ∑ i ∈ H ′ D i − v , H ′ h h' := \sum_{i\in H'}D_i^{-v,H'}h h ′ := ∑ i ∈ H ′ D i − v , H ′ h ( c , x ) ∈ Ω (c,\mathbf{x})\in\Omega ( c , x ) ∈ Ω
h ′ ( x ) − ( D H ′ h ) ( c , x ) = ∑ i ∈ H ′ ( ( D i − v , H ′ − D i ) h ) ( c , x ) = Fact 5.1 { ∑ i ∈ H ′ ( Π i , c − v , H ′ h ) ( x ) c ∉ x 0 otherwise. (29) h'(\mathbf{x})-(D_{H'}h)(c,\mathbf{x})=\sum_{i\in H'}\left((D_i^{-v,H'}-D_i)h\right)(c,\mathbf{x}) \underset{\text{Fact 5.1}}{=} \begin{cases}\sum_{i\in H'}(\Pi_{i,c}^{-v,H'}h)(\mathbf{x}) & c\notin\mathbf{x}\\ 0 & \text{otherwise.}\end{cases} \tag*{(29)} h ′ ( x ) − ( D H ′ h ) ( c , x ) = i ∈ H ′ ∑ ( ( D i − v , H ′ − D i ) h ) ( c , x ) Fact 5.1 = { ∑ i ∈ H ′ ( Π i , c − v , H ′ h ) ( x ) 0 c ∈ / x otherwise. (29) Note that in the last identity we use that if c ∉ x c\notin\mathbf{x} c ∈ / x D i h ( c , x ) D_i h(c,\mathbf{x}) D i h ( c , x ) D i − v , H ′ D_i^{-v,H'} D i − v , H ′
The lists on H ′ H' H ′ ℓ i ≥ s + 1 + deg H ′ ( i ) \ell_i\ge s+1+\deg_{H'}(i) ℓ i ≥ s + 1 + deg H ′ ( i )
∥ h ′ − D H ′ h ∥ μ 2 = 1 ( 25 ) ∣ Ω ∣ ∑ c ∈ L v ∑ x ∈ Ω H ′ ( ∑ i ∈ H ′ ( Π i , c − v , H ′ h ) ( x ) ) 2 = ∣ Ω H ′ ∣ ∣ Ω ∣ ∑ c ∈ L v E μ H ′ − v [ 1 { c ∉ X } ( ∑ i ∈ H ′ ( Π i , c − v , H ′ h ) ( X ) ) 2 ] ≤ Lemma 5.2 β d ∣ Ω H ′ ∣ ∣ Ω ∣ ∑ c ∈ L v ∥ ∑ i ∈ H ′ Π i , c − v , H ′ h ∥ μ H ′ − v 2 ≤ β d ∣ Ω H ′ ∣ ∣ Ω ∣ ∑ c ∥ ∑ i ∈ H ′ Π i , c − v , H ′ h ∥ μ H ′ − v 2 ≤ Lemma 4.1 β d ∣ Ω H ′ ∣ ∣ Ω ∣ ( s s − 1 ∥ D H ′ − v , H ′ h ∥ μ H ′ − v 2 + O ( 1 ) s 2 ∑ i ∈ H ′ deg H ′ ( i ) ∥ D i − v , H ′ h ∥ μ H ′ − v 2 ) = β d ∣ Ω H ′ ∣ ∣ Ω ∣ ( s s − 1 ∥ h ′ ∥ μ H ′ − v 2 + O ( 1 ) s 2 ∑ i ∈ H ′ deg H ′ ( i ) ∥ D i − v , H ′ h ∥ μ H ′ − v 2 ) . (30) \begin{aligned}
\lVert h'-D_{H'}h\rVert_{\mu}^{2}
&=\frac{1}{(25)|\Omega|}\sum_{c\in L_v}\sum_{\mathbf{x}\in\Omega_{H'}}\left(\sum_{i\in H'}(\Pi_{i,c}^{-v,H'}h)(\mathbf{x})\right)^2\\
&=\frac{|\Omega_{H'}|}{|\Omega|}\sum_{c\in L_v}\mathbb{E}_{\mu_{H'}^{-v}}\left[\mathbb{1}_{\{c\notin\mathbf{X}\}}\left(\sum_{i\in H'}(\Pi_{i,c}^{-v,H'}h)(\mathbf{X})\right)^2\right]\\
&\underset{\text{Lemma 5.2}}{\le}\frac{\beta_d|\Omega_{H'}|}{|\Omega|}\sum_{c\in L_v}\left\lVert\sum_{i\in H'}\Pi_{i,c}^{-v,H'}h\right\rVert_{\mu_{H'}^{-v}}^2\\
&\le\frac{\beta_d|\Omega_{H'}|}{|\Omega|}\sum_c\left\lVert\sum_{i\in H'}\Pi_{i,c}^{-v,H'}h\right\rVert_{\mu_{H'}^{-v}}^2\\
&\underset{\text{Lemma 4.1}}{\le}\frac{\beta_d|\Omega_{H'}|}{|\Omega|}\left(\frac{s}{s-1}\lVert D_{H'}^{-v,H'}h\rVert_{\mu_{H'}^{-v}}^2+\frac{O(1)}{s^2}\sum_{i\in H'}\deg_{H'}(i)\lVert D_i^{-v,H'}h\rVert_{\mu_{H'}^{-v}}^2\right)\\
&=\frac{\beta_d|\Omega_{H'}|}{|\Omega|}\left(\frac{s}{s-1}\lVert h'\rVert_{\mu_{H'}^{-v}}^2+\frac{O(1)}{s^2}\sum_{i\in H'}\deg_{H'}(i)\lVert D_i^{-v,H'}h\rVert_{\mu_{H'}^{-v}}^2\right). \tag*{(30)}
\end{aligned} ∥ h ′ − D H ′ h ∥ μ 2 = ( 25 ) ∣Ω∣ 1 c ∈ L v ∑ x ∈ Ω H ′ ∑ ( i ∈ H ′ ∑ ( Π i , c − v , H ′ h ) ( x ) ) 2 = ∣Ω∣ ∣ Ω H ′ ∣ c ∈ L v ∑ E μ H ′ − v 1 { c ∈ / X } ( i ∈ H ′ ∑ ( Π i , c − v , H ′ h ) ( X ) ) 2 Lemma 5.2 ≤ ∣Ω∣ β d ∣ Ω H ′ ∣ c ∈ L v ∑ i ∈ H ′ ∑ Π i , c − v , H ′ h μ H ′ − v 2 ≤ ∣Ω∣ β d ∣ Ω H ′ ∣ c ∑ i ∈ H ′ ∑ Π i , c − v , H ′ h μ H ′ − v 2 Lemma 4.1 ≤ ∣Ω∣ β d ∣ Ω H ′ ∣ ( s − 1 s ∥ D H ′ − v , H ′ h ∥ μ H ′ − v 2 + s 2 O ( 1 ) i ∈ H ′ ∑ deg H ′ ( i ) ∥ D i − v , H ′ h ∥ μ H ′ − v 2 ) = ∣Ω∣ β d ∣ Ω H ′ ∣ ( s − 1 s ∥ h ′ ∥ μ H ′ − v 2 + s 2 O ( 1 ) i ∈ H ′ ∑ deg H ′ ( i ) ∥ D i − v , H ′ h ∥ μ H ′ − v 2 ) . (30) where in the last inequality we apply Lemma 4.1 to Π i , c − v , H ′ \Pi_{i,c}^{-v,H'} Π i , c − v , H ′ Π i , c H ′ \Pi_{i,c}^{H'} Π i , c H ′
To simplify the above, we observe that every leaf coloring has at least s s s
∣ Ω ∣ ∥ h ′ ∥ μ 2 = ∑ x ∈ Ω H ′ ℓ v − x ∣ h ′ ( x ) ∣ 2 ≥ ℓ v ≥ s + ∣ H ′ ∣ s ∣ Ω H ′ ∣ ∥ h ′ ∥ μ H ′ − v 2 . (31) |\Omega|\lVert h'\rVert_{\mu}^{2}=\sum_{\mathbf{x}\in\Omega_{H'}}\ell_v^{- \mathbf{x}}\lvert h'(\mathbf{x})\rvert^2\underset{\ell_v\ge s+|H'|}{\ge}s|\Omega_{H'}|\lVert h'\rVert_{\mu_{H'}^{-v}}^2. \tag*{(31)} ∣Ω∣ ∥ h ′ ∥ μ 2 = x ∈ Ω H ′ ∑ ℓ v − x ∣ h ′ ( x ) ∣ 2 ℓ v ≥ s + ∣ H ′ ∣ ≥ s ∣ Ω H ′ ∣ ∥ h ′ ∥ μ H ′ − v 2 . (31) Consequently, continuing from (26) we obtain
∥ h ′ − D H ′ h ∥ μ 2 ≤ Claim 6.3, (27) β d s − 1 ∥ h ′ ∥ μ 2 + O ( β d ) s 2 ( s − 1 ) ∑ i ∈ H ′ deg H ′ ( i ) ∥ D i h ∥ μ 2 . \lVert h'-D_{H'}h\rVert_{\mu}^{2}\underset{\text{Claim 6.3, (27)}}{\le}\frac{\beta_d}{s-1}\lVert h'\rVert_{\mu}^{2}+\frac{O(\beta_d)}{s^2(s-1)}\sum_{i\in H'}\deg_{H'}(i)\lVert D_i h\rVert_{\mu}^{2}. ∥ h ′ − D H ′ h ∥ μ 2 Claim 6.3, (27) ≤ s − 1 β d ∥ h ′ ∥ μ 2 + s 2 ( s − 1 ) O ( β d ) i ∈ H ′ ∑ deg H ′ ( i ) ∥ D i h ∥ μ 2 . This proves Lemma 6.2.
Analyzing Graphs “far” From Bipartite
In this section, we let Q = ⋃ i ∈ G L i Q = \bigcup_{i\in G} \mathcal{L}_i Q = ⋃ i ∈ G L i
( ∇ i , c f ) ( x ) = { f ( x ) − f ( x i → c ) if c ∈ L i − x i − x N ( i ) , 0 otherwise , (\nabla_{i,c}f)(\mathbf{x}) =
\begin{cases}
f(\mathbf{x}) - f(\mathbf{x}^{i\to c}) & \text{if } c \in\mathcal{L}_i^{-x_i-x_{N(i)}}, \\
0 & \text{otherwise},
\end{cases} ( ∇ i , c f ) ( x ) = { f ( x ) − f ( x i → c ) 0 if c ∈ L i − x i − x N ( i ) , otherwise , and write ∇ i = ( ∇ i , c ) c ∈ Q \nabla_i = (\nabla_{i,c})_{c\in Q} ∇ i = ( ∇ i , c ) c ∈ Q f ∈ L 2 ( μ ) f \in L^2(\mu) f ∈ L 2 ( μ ) ∇ i , c f ∈ L 2 ( μ ) \nabla_{i,c}f \in L^2(\mu) ∇ i , c f ∈ L 2 ( μ )
⟨ ∇ i f , ∇ j g ⟩ Q ⊗ μ : = ∑ c ∈ Q ⟨ ∇ i , c f , ∇ j , c g ⟩ μ . \langle\nabla_i f, \nabla_j g\rangle_{Q\otimes\mu} := \sum_{c\in Q} \langle\nabla_{i,c}f, \nabla_{j,c}g\rangle_\mu. ⟨ ∇ i f , ∇ j g ⟩ Q ⊗ μ := c ∈ Q ∑ ⟨ ∇ i , c f , ∇ j , c g ⟩ μ . We define “unweighted” Laplacian operators
D ‾ i f ( x ) : = ℓ i − x N ( i ) D i f ( x ) = ∑ c ∈ L i − x N ( i ) ∇ i , c f ( x ) , and D ‾ = ∑ i ∈ G D ‾ i . (32) \overline{D}_i f(\mathbf{x}) := \ell_i^{-x_{N(i)}}D_i f(\mathbf{x}) = \sum_{c\in\mathcal{L}_i^{-x_{N(i)}}} \nabla_{i,c}f(\mathbf{x}), \qquad\text{and} \qquad\overline{D} = \sum_{i\in G}\overline{D}_i. \tag*{(32)} D i f ( x ) := ℓ i − x N ( i ) D i f ( x ) = c ∈ L i − x N ( i ) ∑ ∇ i , c f ( x ) , and D = i ∈ G ∑ D i . (32) We now show that, like D i D_i D i P i P_i P i D ‾ i \overline{D}_i D i
⟨ f , D ‾ i g ⟩ μ = E x ∼ μ [ ∑ c ∈ L i − x N G ( i ) f ( x ) ( g ( x ) − g ( x i → c ) ) ] = 1 2 E x ∼ μ [ ∑ c ∈ L i − x N G ( i ) ( f ( x ) − f ( x i → c ) ) ( g ( x ) − g ( x i → c ) ) ] = 1 2 ⟨ ∇ i f , ∇ i g ⟩ Q ⊗ μ = ⟨ D ‾ i f , g ⟩ μ . \begin{aligned}
\langle f,\overline{D}_i g\rangle_\mu
&= \mathbb{E}_{\mathbf{x}\sim\mu}\left[\sum_{c\in\mathcal{L}_i^{-x_{N_G(i)}}} f(\mathbf{x})\left(g(\mathbf{x})-g(\mathbf{x}^{i\to c})\right)\right] \\
&= \frac{1}{2}\mathbb{E}_{\mathbf{x}\sim\mu}\left[\sum_{c\in\mathcal{L}_i^{-x_{N_G(i)}}}\left(f(\mathbf{x})-f(\mathbf{x}^{i\to c})\right)\left(g(\mathbf{x})-g(\mathbf{x}^{i\to c})\right)\right] \\
&= \frac{1}{2}\langle\nabla_i f,\nabla_i g\rangle_{Q\otimes\mu}
= \langle\overline{D}_i f,g\rangle_\mu.
\end{aligned} ⟨ f , D i g ⟩ μ = E x ∼ μ c ∈ L i − x N G ( i ) ∑ f ( x ) ( g ( x ) − g ( x i → c ) ) = 2 1 E x ∼ μ c ∈ L i − x N G ( i ) ∑ ( f ( x ) − f ( x i → c ) ) ( g ( x ) − g ( x i → c ) ) = 2 1 ⟨ ∇ i f , ∇ i g ⟩ Q ⊗ μ = ⟨ D i f , g ⟩ μ . The same equality shows that ⟨ f , D ‾ i f ⟩ μ = 1 2 ∥ ∇ i f ∥ Q ⊗ μ 2 ≥ 0 \langle f,\overline{D}_i f\rangle_\mu= \frac{1}{2}\|\nabla_i f\|^2_{Q\otimes\mu} \ge0 ⟨ f , D i f ⟩ μ = 2 1 ∥ ∇ i f ∥ Q ⊗ μ 2 ≥ 0
∥ D ‾ i f ∥ μ 2 = E μ [ ( ℓ i − x N ( i ) ) 2 ( D i f ) 2 ] ≥ s ⋅ E μ [ ℓ i − x N ( i ) ( D i f ) 2 ] = s ⟨ f , D ‾ i f ⟩ μ . (33) \|\overline{D}_i f\|_\mu^2 = \mathbb{E}_\mu\left[\left(\ell_i^{-x_{N(i)}}\right)^2(D_i f)^2\right] \ge s\cdot\mathbb{E}_\mu\left[\ell_i^{-x_{N(i)}}(D_i f)^2\right] = s\langle f,\overline{D}_i f\rangle_\mu. \tag*{(33)} ∥ D i f ∥ μ 2 = E μ [ ( ℓ i − x N ( i ) ) 2 ( D i f ) 2 ] ≥ s ⋅ E μ [ ℓ i − x N ( i ) ( D i f ) 2 ] = s ⟨ f , D i f ⟩ μ . (33) where the inequality uses that ℓ i − x N ( i ) ≥ s \ell_i^{-x_{N(i)}} \ge s ℓ i − x N ( i ) ≥ s Lemma 1.4 . In particular, analogous to the machinery of Matrix trickledown [2 Proposition IV.4] , instead of lower-bounding ⟨ D ‾ i f , D ‾ j f ⟩ μ \langle\overline{D}_i f,\overline{D}_j f\rangle_\mu ⟨ D i f , D j f ⟩ μ 1 / s 1/s 1/ s ∥ D ‾ i f ∥ μ , ∥ D ‾ j f ∥ μ \|\overline{D}_i f\|_\mu,\|\overline{D}_j f\|_\mu ∥ D i f ∥ μ , ∥ D j f ∥ μ
Lemma 7.1. For a pair of vertices i , j i,j i , j
⟨ D ‾ i f , D ‾ j f ⟩ μ ≥ { ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ , { i , j } ∈ E , 0 , otherwise . \langle\overline{D}_i f,\overline{D}_j f\rangle_\mu\ge
\begin{cases}
\langle\nabla_i f,\nabla_j f\rangle_{Q\otimes\mu}, & \{i,j\}\in E, \\
0, & \text{otherwise}.
\end{cases} ⟨ D i f , D j f ⟩ μ ≥ { ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ , 0 , { i , j } ∈ E , otherwise . This lemma immediately gives our main theorem of the section.
Theorem 1.5. If for every vertex i i i ∣ L i ∣ ≥ s + deg ( i ) |\mathcal{L}_i| \ge s + \deg(i) ∣ L i ∣ ≥ s + deg ( i ) s > 2 ∣ λ min ( A G ) ∣ s > 2|\lambda_{\min}(A_G)| s > 2∣ λ m i n ( A G ) ∣ Δ \Delta Δ O ( n 2 ) O(n^2) O ( n 2 )
Proof. Let λ = ∣ λ min ( A G ) ∣ \lambda= |\lambda_{\min}(A_G)| λ = ∣ λ m i n ( A G ) ∣
∥ D ‾ f ∥ μ 2 ≥ s ∑ i ⟨ f , D ‾ i f ⟩ μ + ∑ i ≠ j i , j ∈ G ( A G ) i j ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ ≥ ( s − 2 λ ) ∑ i ⟨ f , D ‾ i f ⟩ μ + λ ∑ i ∥ ∇ i f ∥ Q ⊗ μ 2 + ∑ i ≠ j i , j ∈ G ( A G ) i j ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ = ( s − 2 λ ) ∑ i ⟨ f , D ‾ i f ⟩ μ + ∑ i , j ∈ G ( A G + λ I ) i j ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ ≥ ( s − 2 λ ) ∑ i ⟨ f , D ‾ i f ⟩ μ (34) \begin{aligned}
\|\overline{D}f\|_{\mu}^{2} \ge s\sum_{i}\langle f,\overline{D}_i f\rangle_{\mu}+\sum_{\substack{i\ne j\\i,j\in G}}(A_G)_{ij}\langle\nabla_i f,\nabla_j f\rangle_{Q\otimes\mu} \\
&\ge(s-2\lambda)\sum_i\langle f,\overline{D}_i f\rangle_{\mu}+\lambda\sum_i\|\nabla_i f\|_{Q\otimes\mu}^{2}+\sum_{\substack{i\ne j\\i,j\in G}}(A_G)_{ij}\langle\nabla_i f,\nabla_j f\rangle_{Q\otimes\mu} \\
&= (s-2\lambda)\sum_i\langle f,\overline{D}_i f\rangle_{\mu}+\sum_{i,j\in G}(A_G+\lambda I)_{ij}\langle\nabla_i f,\nabla_j f\rangle_{Q\otimes\mu}\ge(s-2\lambda)\sum_i\langle f,\overline{D}_i f\rangle_{\mu} \tag*{(34)}
\end{aligned} ∥ D f ∥ μ 2 ≥ s i ∑ ⟨ f , D i f ⟩ μ + i = j i , j ∈ G ∑ ( A G ) ij ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ ≥ ( s − 2 λ ) i ∑ ⟨ f , D i f ⟩ μ + λ i ∑ ∥ ∇ i f ∥ Q ⊗ μ 2 + i = j i , j ∈ G ∑ ( A G ) ij ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ = ( s − 2 λ ) i ∑ ⟨ f , D i f ⟩ μ + i , j ∈ G ∑ ( A G + λ I ) ij ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ ≥ ( s − 2 λ ) i ∑ ⟨ f , D i f ⟩ μ (34) where in the last inequality we use Lemma 2.1 and also that A G + λ I A_G+\lambda I A G + λ I ( s − 2 λ ) / ( n ⋅ max i ℓ i ) (s-2\lambda)/(n\cdot\max_i\ell_i) ( s − 2 λ ) / ( n ⋅ max i ℓ i )
It remains to prove Lemma 7.1 which we do in the rest of this section.
Proof of Lemma 7.1. If { i , j } ∉ E \{i,j\}\notin E { i , j } ∈ / E D ‾ i \overline{D}_i D i D ‾ j \overline{D}_j D j ⟨ D ‾ i f , D ‾ j f ⟩ μ ≥ 0 \langle\overline{D}_i f,\overline{D}_j f\rangle_{\mu}\ge0 ⟨ D i f , D j f ⟩ μ ≥ 0
Suppose now that { i , j } ∈ E \{i,j\}\in E { i , j } ∈ E G G G i , j i,j i , j μ { i , j } \mu_{\{i,j\}} μ { i , j } Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } i , j i,j i , j L i { i , j } , L j { i , j } \mathcal{L}^{\{i,j\}}_i,\mathcal{L}^{\{i,j\}}_j L i { i , j } , L j { i , j }
Now, we note that
⟨ D ‾ i f , D ‾ j f ⟩ μ = ⟨ ∑ c ∈ L i ∇ i , c f , ∑ c ∈ L j ∇ j , c f ⟩ μ = ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ + 1 4 E x ∼ μ ∑ c i , c j ( □ c i , c j f ( x i , x j ) ) 2 , (35) \langle\overline{D}_i f,\overline{D}_j f\rangle_{\mu}
=\left\langle\sum_{c\in\mathcal{L}_i}\nabla_{i,c}f,\sum_{c\in\mathcal{L}_j}\nabla_{j,c}f\right\rangle_{\mu}
=\langle\nabla_i f,\nabla_j f\rangle_{Q\otimes\mu}+\frac{1}{4}\mathbb{E}_{x\sim\mu}\sum_{c_i,c_j}\left(\Box_{c_i,c_j}f(x_i,x_j)\right)^2, \tag*{(35)} ⟨ D i f , D j f ⟩ μ = ⟨ c ∈ L i ∑ ∇ i , c f , c ∈ L j ∑ ∇ j , c f ⟩ μ = ⟨ ∇ i f , ∇ j f ⟩ Q ⊗ μ + 4 1 E x ∼ μ c i , c j ∑ ( □ c i , c j f ( x i , x j ) ) 2 , (35) where the inner-sum in the last expression is over all pairs of colors c i ∈ L i − x i − x j c_i\in\mathcal{L}^{-x_i-x_j}_i c i ∈ L i − x i − x j c j ∈ L j − x i − x j c_j\in\mathcal{L}^{-x_i-x_j}_j c j ∈ L j − x i − x j c i ≠ c j c_i\ne c_j c i = c j □ c i , c j f ( x i , x j ) = f ( c i , c j ) − f ( c i , x j ) − f ( x i , c j ) + f ( x i , x j ) \Box_{c_i,c_j}f(x_i,x_j)=f(c_i,c_j)-f(c_i,x_j)-f(x_i,c_j)+f(x_i,x_j) □ c i , c j f ( x i , x j ) = f ( c i , c j ) − f ( c i , x j ) − f ( x i , c j ) + f ( x i , x j ) ( x i , x j , c i , c j ) (x_i,x_j,c_i,c_j) ( x i , x j , c i , c j )
x = f ( x i , x j ) , y = f ( c i , x j ) , z = f ( x i , c j ) and w = f ( c i , c j ) . x=f(x_i,x_j),\qquad y=f(c_i,x_j),\qquad z=f(x_i,c_j)\qquad\text{and}\qquad w=f(c_i,c_j). x = f ( x i , x j ) , y = f ( c i , x j ) , z = f ( x i , c j ) and w = f ( c i , c j ) . The four associated terms in the expanded sum are
( x − y ) ( x − z ) + ( y − x ) ( y − w ) + ( z − w ) ( z − x ) + ( w − z ) ( w − y ) = ( w − y − z + x ) 2 = ( □ c i , c j f ( x i , x j ) ) 2 . (x-y)(x-z)+(y-x)(y-w)+(z-w)(z-x)+(w-z)(w-y)=(w-y-z+x)^2=\left(\Box_{c_i,c_j}f(x_i,x_j)\right)^2. ( x − y ) ( x − z ) + ( y − x ) ( y − w ) + ( z − w ) ( z − x ) + ( w − z ) ( w − y ) = ( w − y − z + x ) 2 = ( □ c i , c j f ( x i , x j ) ) 2 . Each such term is counted four times.
