Documentation

Dynamics.GraphRounds

Graph-indexed rounds #

Round types for dynamics on a finite simple graph G, to be averaged with avg, iterated with expList and turned into kernels with Kernel.ofStep.

Uniform averages over the neighbours of v are written avg (fun u : G.neighborSet v => g u), equal to (∑ u ∈ G.neighborFinset v, g u) / G.degree v (avg_neighborSet).

@[reducible, inline]
abbrev Dynamics.NeighborRound {V : Type u_1} (G : SimpleGraph V) :
Type u_1

A synchronous round on G: every vertex v picks a neighbour r v. Under the uniform distribution the picks are independent and uniform among the neighbours.

Equations
Instances For
    @[reducible, inline]
    abbrev Dynamics.EdgeRound {V : Type u_1} (G : SimpleGraph V) :
    Type u_1

    A sequential step on G: one oriented edge (d.fst, d.snd) of G is activated. Under the uniform distribution this is a uniform edge with a uniform orientation.

    Equations
    Instances For
      def Dynamics.oneWayStep {V : Type u_1} [DecidableEq V] {G : SimpleGraph V} {S : Type u_2} (δ : S → S → S) (s : V → S) (d : EdgeRound G) :
      V → S

      One step of a one-way pairwise protocol with transition rule δ on the activated oriented edge d: the responder d.snd takes δ (s d.snd) (s d.fst) against the initiator d.fst, and every other vertex keeps its state.

      Equations
      Instances For

        Uniform neighbours and synchronous rounds: every vertex samples a neighbour #

        theorem Dynamics.avg_neighborSet {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (v : V) (g : V → ℝ) :
        (avg fun (u : ↑(G.neighborSet v)) => g ↑u) = (∑ u ∈ G.neighborFinset v, g u) / ↑(G.degree v)

        The uniform average over the neighbours of v is their sum divided by the degree.

        theorem Dynamics.nonempty_neighborSet {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : ∀ (v : V), 0 < G.degree v) (v : V) :

        With no isolated vertex, every neighbour set is nonempty.

        theorem Dynamics.neighborRound_nonempty {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (hd : ∀ (v : V), 0 < G.degree v) :

        Synchronous rounds exist as soon as no vertex is isolated.

        The number of synchronous rounds is the product of the degrees.

        theorem Dynamics.avg_neighborRound_prod {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (f : V → V → ℝ) :
        (avg fun (r : NeighborRound G) => ∏ v : V, f v ↑(r v)) = ∏ v : V, avg fun (u : ↑(G.neighborSet v)) => f v ↑u

        Independence: in a uniform synchronous round the vertices sample their neighbours independently, so averages of products over the vertices factor.

        theorem Dynamics.avg_neighborRound_eval {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (v : V), 0 < G.degree v) (v : V) (g : V → ℝ) :
        (avg fun (r : NeighborRound G) => g ↑(r v)) = avg fun (u : ↑(G.neighborSet v)) => g ↑u

        Marginal: in a uniform synchronous round each vertex samples a uniform neighbour.

        theorem Dynamics.avg_neighborRound_mul {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (v : V), 0 < G.degree v) {v w : V} (hvw : v ≠ w) (g h : V → ℝ) :
        (avg fun (r : NeighborRound G) => g ↑(r v) * h ↑(r w)) = (avg fun (u : ↑(G.neighborSet v)) => g ↑u) * avg fun (u : ↑(G.neighborSet w)) => h ↑u

        Pairwise independence: in a uniform synchronous round two distinct vertices sample their neighbours independently.

        theorem Dynamics.avg_neighborRound_sum {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (v : V), 0 < G.degree v) (f : V → V → ℝ) :
        (avg fun (r : NeighborRound G) => ∑ v : V, f v ↑(r v)) = ∑ v : V, avg fun (u : ↑(G.neighborSet v)) => f v ↑u

        Linearity over the vertices: the average of a sum of one-vertex observables is the sum of their neighbour averages.

        theorem Dynamics.avg_vertex_neighborRound {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (hd : ∀ (v : V), 0 < G.degree v) (F : V → V → ℝ) :
        (avg fun (p : V × NeighborRound G) => F p.1 ↑(p.2 p.1)) = avg fun (v : V) => avg fun (u : ↑(G.neighborSet v)) => F v ↑u

        Random vertex, then random neighbour: a uniform vertex v together with a uniform synchronous round r realizes the sequential step "a uniform vertex v and a uniform neighbour r v of v" (the death–Birth scheduler), so V × NeighborRound G is its round type.

        Sequential rounds: one uniformly random oriented edge per step #

        theorem Dynamics.edgeRound_nonempty {V : Type u_1} (G : SimpleGraph V) {u v : V} (h : G.Adj u v) :

        Sequential steps exist as soon as G has an edge.

        def Dynamics.dartEquiv {V : Type u_1} (G : SimpleGraph V) :
        G.Dart ≃ { p : V × V // G.Adj p.1 p.2 }

        The darts of G are the adjacent ordered pairs.

        Equations
        Instances For
          theorem Dynamics.walk_sum_darts {V : Type u_1} {G : SimpleGraph V} (ψ : V → ℝ) {u v : V} (p : G.Walk u v) :
          (List.map (fun (d : G.Dart) => ψ d.toProd.1 - ψ d.toProd.2) p.darts).sum = ψ u - ψ v

          Differences along a walk telescope.

          theorem Dynamics.sum_dart {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (f : V → V → ℝ) :
          ∑ d : G.Dart, f d.toProd.1 d.toProd.2 = ∑ a : V, ∑ b : V, if G.Adj a b then f a b else 0

          A sum over the darts of G is a sum over the adjacent ordered pairs.

          theorem Dynamics.avg_edgeRound_symm {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (F : V → V → ℝ) :
          (avg fun (d : EdgeRound G) => F d.toProd.2 d.toProd.1) = avg fun (d : EdgeRound G) => F d.toProd.1 d.toProd.2

          Uniform orientation: averages are invariant under reversing the activated edge.

          theorem Dynamics.sum_darts_sq_le {V : Type u_1} [Fintype V] {G : SimpleGraph V} [DecidableRel G.Adj] [DecidableEq V] (ψ : V → ℝ) (S : Finset G.Dart) :
          ∑ d ∈ S, (ψ d.toProd.1 - ψ d.toProd.2) ^ 2 ≤ ∑ i : V, ∑ j : V, if G.Adj i j then (ψ i - ψ j) ^ 2 else 0

          Squared differences over distinct darts are bounded by the Dirichlet energy ∑_{i ∼ j} (ψ i - ψ j)² (each edge counted in both orientations).

          theorem Dynamics.avg_edgeRound {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (F : V → V → ℝ) :
          (avg fun (d : EdgeRound G) => F d.toProd.1 d.toProd.2) = (∑ v : V, ∑ u ∈ G.neighborFinset v, F v u) / (2 * ↑G.edgeFinset.card)

          Uniform oriented edge: the average over the activated oriented edge is the sum over the adjacent ordered pairs divided by 2 |E|.

          theorem Dynamics.avg_edgeRound_edge {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (g : Sym2 V → ℝ) :
          (avg fun (d : EdgeRound G) => g (SimpleGraph.Dart.edge d)) = avg fun (e : ↑G.edgeSet) => g ↑e

          Uniform edge: the underlying edge of a uniform oriented edge is a uniform edge.

          theorem Dynamics.avg_edgeRound_fst {V : Type u_1} [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] [DecidableEq V] (g : V → ℝ) :
          (avg fun (d : EdgeRound G) => g d.toProd.1) = (∑ v : V, ↑(G.degree v) * g v) / (2 * ↑G.edgeFinset.card)

          Degree bias: the tail of a uniform oriented edge is v with probability deg v / 2 |E|.

          The complete graph: one uniformly random ordered pair of distinct vertices per step #

          def Dynamics.edgeRoundTopEquiv {V : Type u_1} :
          EdgeRound ⊤ ≃ { p : V × V // p.1 ≠ p.2 }

          On the complete graph, an oriented edge is an ordered pair of distinct vertices (the "random ordered pair" scheduler of population protocols).

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

            The complete graph on n vertices has n (n - 1) oriented edges: twice its n choose 2 edges.

            theorem Dynamics.sum_edgeRound_top {V : Type u_1} [Fintype V] [DecidableEq V] (F : V → V → ℝ) :
            ∑ d : EdgeRound ⊤, F d.toProd.1 d.toProd.2 = ∑ u : V, ∑ v : V, F u v - ∑ v : V, F v v

            On the complete graph, a sum over the oriented edges is the sum over all ordered pairs minus the diagonal.