Documentation

Averaging.OpportunisticClustered

Averaging whenever you meet: clustered regular graphs and the first-moment criteria #

An (n, d, b)-clustered regular graph (Definition 2.2 of arXiv:1703.05045, v3) is d-regular with two communities Vโ‚, Vโ‚‚ of size n/2, every node having exactly b neighbours in the other community. Then the cut vector ฯ‡ = ๐Ÿ™_{Vโ‚} - ๐Ÿ™_{Vโ‚‚} is an eigenvector of the normalized Laplacian ๐“› = L/d with eigenvalue ฮปโ‚‚ = 2b/d, and of Wฬ„ = I - ๐“›/n with eigenvalue 1 - ฮปโ‚‚/n (Section 4.1). The state splits as x = x_โˆฅ + y + z (equation (7)) along ๐Ÿ™, along ฯ‡, and orthogonally to both.

The third eigenvalue ฮปโ‚ƒ of ๐“› enters only through the bound zแต€๐“›z โ‰ฅ ฮปโ‚ƒ โ€–zโ€–ยฒ for z โŸ‚ ๐Ÿ™, ฯ‡ (ThirdEigenvalueLB). With these, the first-moment decomposition (Lemma B.1) is exact, the set of bad nodes of Definition B.1 is empty, and Lemmas B.3 (monotonicity) and B.4 (sign) hold for every node: this is Theorem 3.1 on clustered regular graphs.

structure Averaging.Opportunistic.IsClusteredRegular {V : Type u_1} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (Vโ‚ : Finset V) (d b : โ„•) :

Definition 2.2: G is an (n, d, b)-clustered regular graph with communities Vโ‚ and Vโ‚‚ = Vโ‚แถœ, where n is the number of nodes: |Vโ‚| = |Vโ‚‚| = n/2, every node has degree d, every node has exactly b neighbours in the other community, and 0 < b, 2b < d < n.

Instances For
    def Averaging.Opportunistic.cutVec {V : Type u_1} [DecidableEq V] (Vโ‚ : Finset V) :
    V โ†’ โ„

    The cut vector ฯ‡ = ๐Ÿ™_{Vโ‚} - ๐Ÿ™_{Vโ‚‚}.

    Equations
    Instances For
      noncomputable def Averaging.Opportunistic.projOne {V : Type u_1} [Fintype V] (x : V โ†’ โ„) :
      V โ†’ โ„

      x_โˆฅ = Qโ‚ x, the projection of x on the constant vectors: every entry is the average ฮฑโ‚ = โŸจx, ๐Ÿ™โŸฉ/n of x.

      Equations
      Instances For
        noncomputable def Averaging.Opportunistic.projCut {V : Type u_1} [Fintype V] [DecidableEq V] (Vโ‚ : Finset V) (x : V โ†’ โ„) :
        V โ†’ โ„

        y = Qโ‚‚ x, the projection of x on the cut vector: (โŸจx, ฯ‡โŸฉ/n) ฯ‡.

        Equations
        Instances For
          noncomputable def Averaging.Opportunistic.projRest {V : Type u_1} [Fintype V] [DecidableEq V] (Vโ‚ : Finset V) (x : V โ†’ โ„) :
          V โ†’ โ„

          z = Q_{3โ‹ฏn} x = x - x_โˆฅ - y, the projection of x orthogonally to ๐Ÿ™ and ฯ‡.

          Equations
          Instances For

            ฮปโ‚ƒ โ‰ฅ lam3 for a d-regular graph with cut vector ฯ‡: the Rayleigh quotient of the normalized Laplacian ๐“› = L/d is at least lam3 on the vectors orthogonal to ๐Ÿ™ and ฯ‡. For a clustered regular graph with ฮปโ‚ƒ > 2b/d (so that ฯ‡ spans the second eigenspace), the largest such lam3 is the third eigenvalue ฮปโ‚ƒ of ๐“›.

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For

              Auxiliary lemmas #

              theorem Averaging.Opportunistic.cutVec_sq {V : Type u_1} [DecidableEq V] {Vโ‚ : Finset V} (v : V) :
              cutVec Vโ‚ v ^ 2 = 1
              theorem Averaging.Opportunistic.cutVec_mul_self {V : Type u_1} [DecidableEq V] {Vโ‚ : Finset V} (v : V) :
              cutVec Vโ‚ v * cutVec Vโ‚ v = 1
              theorem Averaging.Opportunistic.abs_cutVec {V : Type u_1} [DecidableEq V] {Vโ‚ : Finset V} (v : V) :
              |cutVec Vโ‚ v| = 1
              theorem Averaging.Opportunistic.IsClusteredRegular.degree_eq {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (v : V) :
              G.degree v = d
              theorem Averaging.Opportunistic.IsClusteredRegular.d_pos {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              0 < d
              theorem Averaging.Opportunistic.IsClusteredRegular.card_pos_real {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              0 < โ†‘(Fintype.card V)
              theorem Averaging.Opportunistic.IsClusteredRegular.two_mul_card_edgeFinset {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              2 * โ†‘G.edgeFinset.card = โ†‘(Fintype.card V) * โ†‘d
              theorem Averaging.Opportunistic.IsClusteredRegular.b_lt_d_real {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              2 * โ†‘b / โ†‘d < 1
              theorem Averaging.Opportunistic.IsClusteredRegular.two_div_card_lt {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              2 / โ†‘(Fintype.card V) < 2 * โ†‘b / โ†‘d
              theorem Averaging.Opportunistic.IsClusteredRegular.sum_cutVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              โˆ‘ v : V, cutVec Vโ‚ v = 0
              theorem Averaging.Opportunistic.IsClusteredRegular.card_same {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (v : V) :
              {u โˆˆ G.neighborFinset v | ยฌ(u โˆˆ Vโ‚ โ†” v โˆ‰ Vโ‚)}.card = d - b
              theorem Averaging.Opportunistic.IsClusteredRegular.lapMatrix_mulVec_cutVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              (SimpleGraph.lapMatrix โ„ G).mulVec (cutVec Vโ‚) = (2 * โ†‘b) โ€ข cutVec Vโ‚
              theorem Averaging.Opportunistic.IsClusteredRegular.card_mul_avg {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) :
              โ†‘(Fintype.card V) * Dynamics.avg x = โˆ‘ v : V, x v
              theorem Averaging.Opportunistic.IsClusteredRegular.sum_projRest {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) :
              โˆ‘ v : V, projRest Vโ‚ x v = 0
              theorem Averaging.Opportunistic.IsClusteredRegular.sum_cutVec_mul_projRest {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) :
              โˆ‘ v : V, cutVec Vโ‚ v * projRest Vโ‚ x v = 0
              theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_projRest_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) :
              โˆ‘ v : V, projRest Vโ‚ x v ^ 2 โ‰ค โˆ‘ v : V, x v ^ 2
              theorem Averaging.Opportunistic.IsClusteredRegular.dotProduct_lap_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (z : V โ†’ โ„) :
              z โฌแตฅ (SimpleGraph.lapMatrix โ„ G).mulVec z โ‰ค 2 * โ†‘d * โˆ‘ v : V, z v ^ 2
              theorem Averaging.Opportunistic.IsClusteredRegular.lam3_le_two {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) :
              lam3 โ‰ค 2
              theorem Averaging.Opportunistic.meanStepMatrix_mulVec_const {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] (c : โ„) :
              ((meanStepMatrix G).mulVec fun (x : V) => c) = fun (x : V) => c
              theorem Averaging.Opportunistic.meanStepMatrix_pow_mulVec_const {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] (t : โ„•) (c : โ„) :
              ((meanStepMatrix G ^ t).mulVec fun (x : V) => c) = fun (x : V) => c
              theorem Averaging.Opportunistic.sum_meanStepMatrix_mulVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] (z : V โ†’ โ„) :
              โˆ‘ v : V, (meanStepMatrix G).mulVec z v = โˆ‘ v : V, z v
              theorem Averaging.Opportunistic.sum_sq_eq_dotProduct {V : Type u_1} [Fintype V] (z : V โ†’ โ„) :
              โˆ‘ v : V, z v ^ 2 = z โฌแตฅ z
              theorem Averaging.Opportunistic.projOne_add {V : Type u_1} [Fintype V] [DecidableEq V] {Vโ‚ : Finset V} (x : V โ†’ โ„) (v : V) :
              x v = projOne x v + projCut Vโ‚ x v + projRest Vโ‚ x v
              theorem Averaging.Opportunistic.IsClusteredRegular.meanStepMatrix_mulVec_cutVec_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
              (meanStepMatrix G).mulVec (cutVec Vโ‚) = (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) โ€ข cutVec Vโ‚
              theorem Averaging.Opportunistic.IsClusteredRegular.meanStepMatrix_pow_mulVec_cutVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (t : โ„•) :
              (meanStepMatrix G ^ t).mulVec (cutVec Vโ‚) = (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t โ€ข cutVec Vโ‚
              theorem Averaging.Opportunistic.IsClusteredRegular.cutVec_dot_meanStepMatrix {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (z : V โ†’ โ„) :
              โˆ‘ v : V, cutVec Vโ‚ v * (meanStepMatrix G).mulVec z v = (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) * โˆ‘ v : V, cutVec Vโ‚ v * z v
              theorem Averaging.Opportunistic.IsClusteredRegular.meanStepMatrix_pow_mulVec_compl {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (z : V โ†’ โ„) (hz : โˆ‘ v : V, z v = 0) (hฯ‡ : โˆ‘ v : V, cutVec Vโ‚ v * z v = 0) (t : โ„•) :
              โˆ‘ v : V, (meanStepMatrix G ^ t).mulVec z v = 0 โˆง โˆ‘ v : V, cutVec Vโ‚ v * (meanStepMatrix G ^ t).mulVec z v = 0

              Wฬ„ maps the orthogonal complement of ๐Ÿ™ and ฯ‡ to itself.

              theorem Averaging.Opportunistic.IsClusteredRegular.beta_pos {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) :
              0 < 1 - lam3 / โ†‘(Fintype.card V)
              theorem Averaging.Opportunistic.IsClusteredRegular.half_le_beta {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) :
              1 / 2 โ‰ค 1 - lam3 / โ†‘(Fintype.card V)
              theorem Averaging.Opportunistic.IsClusteredRegular.dotProduct_meanStepMatrix_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (z : V โ†’ โ„) (hz : โˆ‘ v : V, z v = 0) (hฯ‡ : โˆ‘ v : V, cutVec Vโ‚ v * z v = 0) :
              z โฌแตฅ (meanStepMatrix G).mulVec z โ‰ค (1 - lam3 / โ†‘(Fintype.card V)) * โˆ‘ v : V, z v ^ 2

              The Rayleigh bounds of Wฬ„: at most ฮปฬ„โ‚ƒ = 1 - ฮปโ‚ƒ/n on the complement of ๐Ÿ™, ฯ‡, and at least -ฮปฬ„โ‚ƒ everywhere.

              theorem Averaging.Opportunistic.IsClusteredRegular.neg_le_dotProduct_meanStepMatrix {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (z : V โ†’ โ„) :
              -((1 - lam3 / โ†‘(Fintype.card V)) * โˆ‘ v : V, z v ^ 2) โ‰ค z โฌแตฅ (meanStepMatrix G).mulVec z
              theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_meanStepMatrix_mulVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (z : V โ†’ โ„) (hz : โˆ‘ v : V, z v = 0) (hฯ‡ : โˆ‘ v : V, cutVec Vโ‚ v * z v = 0) :
              โˆ‘ v : V, (meanStepMatrix G).mulVec z v ^ 2 โ‰ค (1 - lam3 / โ†‘(Fintype.card V)) ^ 2 * โˆ‘ v : V, z v ^ 2

              One step of the contraction of Lemma B.1, by polarization.

              theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_lap_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (z : V โ†’ โ„) :
              โˆ‘ v : V, (SimpleGraph.lapMatrix โ„ G).mulVec z v ^ 2 โ‰ค 4 * โ†‘d ^ 2 * โˆ‘ v : V, z v ^ 2
              theorem Averaging.Opportunistic.IsClusteredRegular.sum_sq_meanStepMatrix_pow_mulVec_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (z : V โ†’ โ„) (hz : โˆ‘ v : V, z v = 0) (hฯ‡ : โˆ‘ v : V, cutVec Vโ‚ v * z v = 0) (t : โ„•) :
              โˆ‘ v : V, (meanStepMatrix G ^ t).mulVec z v ^ 2 โ‰ค (1 - lam3 / โ†‘(Fintype.card V)) ^ (2 * t) * โˆ‘ v : V, z v ^ 2

              The iterated contraction of Lemma B.1.

              theorem Averaging.Opportunistic.IsClusteredRegular.expList_avgRun_decomp_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) (t : โ„•) (v : V) :
              (Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G x l v) = projOne x v + (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t * projCut Vโ‚ x v + (meanStepMatrix G ^ t).mulVec (projRest Vโ‚ x) v
              theorem Averaging.Opportunistic.sum_units_eq {V : Type u_1} [Fintype V] (ฯ„ : V โ†’ โ„คหฃ) :
              โˆ‘ v : V, โ†‘โ†‘(ฯ„ v) = โ†‘(Fintype.card V) - 2 * โ†‘{v : V | ฯ„ v = -1}.card

              The sum of n signs ยฑ1 has the parity of n.

              def Averaging.Opportunistic.cutUnit {V : Type u_1} [DecidableEq V] (Vโ‚ : Finset V) :
              V โ†’ โ„คหฃ

              The cut vector as a vector of units.

              Equations
              Instances For
                theorem Averaging.Opportunistic.cutVec_mul_signVec {V : Type u_1} [DecidableEq V] {Vโ‚ : Finset V} (ฯƒ : V โ†’ โ„คหฃ) (v : V) :
                cutVec Vโ‚ v * signVec ฯƒ v = signVec (cutUnit Vโ‚ * ฯƒ) v
                theorem Averaging.Opportunistic.two_le_abs_sum_cutVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (ฯƒ : V โ†’ โ„คหฃ) (h : โˆ‘ v : V, cutVec Vโ‚ v * signVec ฯƒ v โ‰  0) :
                2 โ‰ค |โˆ‘ v : V, cutVec Vโ‚ v * signVec ฯƒ v|
                theorem Averaging.Opportunistic.sq_le_sum_sq {V : Type u_1} [Fintype V] (f : V โ†’ โ„) (u : V) :
                f u ^ 2 โ‰ค โˆ‘ v : V, f v ^ 2
                theorem Averaging.Opportunistic.sum_sq_signVec {V : Type u_1} [Fintype V] (ฯƒ : V โ†’ โ„คหฃ) :
                โˆ‘ v : V, signVec ฯƒ v ^ 2 = โ†‘(Fintype.card V)
                theorem Averaging.Opportunistic.IsClusteredRegular.expList_projCut_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) (t : โ„•) (v : V) :
                (Dynamics.expList G.Dart t fun (l : List G.Dart) => projCut Vโ‚ (avgRun G x l) v) = (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t * projCut Vโ‚ x v
                theorem Averaging.Opportunistic.IsClusteredRegular.sign_criterion_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (ฯƒ : V โ†’ โ„คหฃ) (t : โ„•) (h1 : โ†‘(Fintype.card V) * (1 - lam3 / โ†‘(Fintype.card V)) ^ t โ‰ค |Dynamics.avg (signVec ฯƒ)|) (h2 : 2 * |Dynamics.avg (signVec ฯƒ)| < |Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w| * (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t) (u : V) :
                SignType.sign (Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G (signVec ฯƒ) l u) = SignType.sign ((Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w) * cutVec Vโ‚ u)
                theorem Averaging.Opportunistic.IsClusteredRegular.monotone_criterion_aux {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (ฯƒ : V โ†’ โ„คหฃ) (hฯƒ : (Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w) โ‰  0) (t : โ„•) (ht : โ†‘(Fintype.card V) ^ 3 * (1 - lam3 / โ†‘(Fintype.card V)) ^ t โ‰ค (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t) (u : V) :
                SignType.sign ((Dynamics.expList G.Dart (t - 1) fun (l : List G.Dart) => avgRun G (signVec ฯƒ) l u) - Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G (signVec ฯƒ) l u) = SignType.sign ((Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w) * cutVec Vโ‚ u)

                Main statements #

                theorem Averaging.Opportunistic.meanStepMatrix_mulVec_cutVec {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) :
                (meanStepMatrix G).mulVec (cutVec Vโ‚) = (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) โ€ข cutVec Vโ‚

                Section 4.1: on an (n, d, b)-clustered regular graph, Wฬ„ ฯ‡ = (1 - ฮปโ‚‚/n) ฯ‡ with ฮปโ‚‚ = 2b/d.

                theorem Averaging.Opportunistic.expList_projCut {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) (t : โ„•) (v : V) :
                (Dynamics.expList G.Dart t fun (l : List G.Dart) => projCut Vโ‚ (avgRun G x l) v) = (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t * projCut Vโ‚ x v

                Equation (12) with ฮด = 1/2: the expected component along ฯ‡ decays geometrically, E[yโฝแต—โพ] = (1 - ฮปโ‚‚/n)แต— yโฝโฐโพ.

                theorem Averaging.Opportunistic.expList_avgRun_decomp {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} (hG : IsClusteredRegular G Vโ‚ d b) (x : V โ†’ โ„) (t : โ„•) (v : V) :
                (Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G x l v) = projOne x v + (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t * projCut Vโ‚ x v + (meanStepMatrix G ^ t).mulVec (projRest Vโ‚ x) v

                Lemma B.1 (main decomposition) on a clustered regular graph: E[xโฝแต—โพ | xโฝโฐโพ = x] = x_โˆฅ + (1 - ฮปโ‚‚/n)แต— y + eโฝแต—โพ with eโฝแต—โพ = Wฬ„แต— z.

                theorem Averaging.Opportunistic.sum_sq_meanStepMatrix_pow_le {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (z : V โ†’ โ„) (hz : โˆ‘ v : V, z v = 0) (hฯ‡ : โˆ‘ v : V, cutVec Vโ‚ v * z v = 0) (t : โ„•) :
                โˆ‘ v : V, (meanStepMatrix G ^ t).mulVec z v ^ 2 โ‰ค (1 - lam3 / โ†‘(Fintype.card V)) ^ (2 * t) * โˆ‘ v : V, z v ^ 2

                The bound of Lemma B.1 on eโฝแต—โพ: on the vectors orthogonal to ๐Ÿ™ and ฯ‡, Wฬ„แต— contracts the norm by ฮปฬ„โ‚ƒแต—, where ฮปฬ„โ‚ƒ = 1 - ฮปโ‚ƒ/n is the third eigenvalue of Wฬ„.

                theorem Averaging.Opportunistic.monotone_criterion {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (ฯƒ : V โ†’ โ„คหฃ) (hฯƒ : (Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w) โ‰  0) (t : โ„•) (ht : โ†‘(Fintype.card V) ^ 3 * (1 - lam3 / โ†‘(Fintype.card V)) ^ t โ‰ค (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t) (u : V) :
                SignType.sign ((Dynamics.expList G.Dart (t - 1) fun (l : List G.Dart) => avgRun G (signVec ฯƒ) l u) - Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G (signVec ฯƒ) l u) = SignType.sign ((Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w) * cutVec Vโ‚ u)

                Lemma B.3 (monotonicity property) on a clustered regular graph, where no node is bad: for an initial vector x โˆˆ {-1, 1}โฟ with ฮฑโ‚‚ = โŸจx, ฯ‡โŸฉ/n โ‰  0 and every round t with t โ‰ฅ 3 log n / log (ฮปฬ„โ‚‚/ฮปฬ„โ‚ƒ) (that is, nยณ ฮปฬ„โ‚ƒแต— โ‰ค ฮปฬ„โ‚‚แต—, where ฮปฬ„โ‚‚ = 1 - ฮปโ‚‚/n and ฮปฬ„โ‚ƒ = 1 - ฮปโ‚ƒ/n), the expected value of every node u moves in the direction given by its community: sgn(E[xโฝแต—โปยนโพ_u] - E[xโฝแต—โพ_u]) = sgn(ฮฑโ‚‚ ฯ‡_u).

                theorem Averaging.Opportunistic.sign_criterion {V : Type u_1} [Fintype V] [DecidableEq V] {G : SimpleGraph V} [DecidableRel G.Adj] {Vโ‚ : Finset V} {d b : โ„•} {lam3 : โ„} (hG : IsClusteredRegular G Vโ‚ d b) (h3 : ThirdEigenvalueLB G Vโ‚ d lam3) (ฯƒ : V โ†’ โ„คหฃ) (t : โ„•) (h1 : โ†‘(Fintype.card V) * (1 - lam3 / โ†‘(Fintype.card V)) ^ t โ‰ค |Dynamics.avg (signVec ฯƒ)|) (h2 : 2 * |Dynamics.avg (signVec ฯƒ)| < |Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w| * (1 - 2 * โ†‘b / โ†‘d / โ†‘(Fintype.card V)) ^ t) (u : V) :
                SignType.sign (Dynamics.expList G.Dart t fun (l : List G.Dart) => avgRun G (signVec ฯƒ) l u) = SignType.sign ((Dynamics.avg fun (w : V) => cutVec Vโ‚ w * signVec ฯƒ w) * cutVec Vโ‚ u)

                Lemma B.4 (sign property) on a clustered regular graph, where no node is bad: for an initial vector x โˆˆ {-1, 1}โฟ with averages ฮฑโ‚ = โŸจx, ๐Ÿ™โŸฉ/n and ฮฑโ‚‚ = โŸจx, ฯ‡โŸฉ/n, and every round t in the window log (n/|ฮฑโ‚|) / log (1/ฮปฬ„โ‚ƒ) โ‰ค t (that is, n ฮปฬ„โ‚ƒแต— โ‰ค |ฮฑโ‚|) and 2|ฮฑโ‚| < |ฮฑโ‚‚| ฮปฬ„โ‚‚แต—, the sign of the expected value of every node u is sgn(ฮฑโ‚‚ ฯ‡_u).