Unions and self-loops #
Two regular multigraphs G and H on the same vertices, of degrees |D| and |E|, superpose
to a multigraph G.union H of degree |D| + |E|, whose edges at a vertex are those of G
followed by those of H. One step of its random walk is a step of G with probability
|D| / (|D| + |E|) and a step of H otherwise, so its walk operator is the weighted average of
theirs (walk_union_apply) and its spectral expansion is at most the weighted average of
theirs (spectralExpansion_union_le).
The simplest such H is loops V E, with a self-loop at every vertex for each label i : E and no
other edge, whose walk operator is the identity as soon as there is a label (walk_loops); with a
single label, loops V Unit is the multigraph whose tensor products with H are disjoint copies of
H. Superposing loops V E adds self-loops to G (addLoops). A few of them, as Dinur's
preprocessing adds Dinur, Section 3.1, close at most the proportion
|E| / (|D| + |E|) of the gap between the spectral expansion and 1
(spectralExpansion_addLoops_le). As many self-loops as edges at each
vertex give the lazy graph Cslib.RotationMap.lazy, whose walk stays put half of the time.
Renaming the edge labels along an equivalence (relabel) changes neither the walk operator nor
the spectral expansion; it lets constructions with structured label types, such as D ⊕ D,
present their results with labels Fin d.
Main definitions #
Cslib.RotationMap.relabel: the same multigraph with its edge labels renamed.Cslib.RotationMap.union: the superposition of two regular multigraphs on the same vertices.Cslib.RotationMap.loops: a self-loop at every vertex for each label.Cslib.RotationMap.addLoops: a regular multigraph with self-loops added at every vertex.
Main results #
Cslib.RotationMap.spectralExpansion_relabel: relabelling preserves the spectral expansion.Cslib.RotationMap.walk_union_apply,Cslib.RotationMap.spectralExpansion_union_le: the walk operator and the spectral expansion of a union.Cslib.RotationMap.walk_loops: the walk operator of the self-loops is the identity.Cslib.RotationMap.walk_addLoops_apply,Cslib.RotationMap.spectralExpansion_addLoops_le: the same for adding self-loops.
References #
The same multigraph with its edge labels renamed along e : D ≃ E: the e i-th edge at a
vertex of G.relabel e is its i-th edge in G.
Instances For
Relabelling the edges does not change the spectral expansion.
The union of two regular multigraphs G and H on the same vertices: the multigraph whose
edges at a vertex are those of G, labelled by Sum.inl, followed by those of H, labelled by
Sum.inr. Its degree is the sum of their degrees.
Instances For
The neighbors of a vertex in a union along the edges of the first multigraph.
The neighbors of a vertex in a union along the edges of the second multigraph.
The walk operator of a union is the average of the walk operators of the two multigraphs, weighted by their degrees.
The spectral expansion of a union is at most the average of the spectral expansions of the two multigraphs, weighted by their degrees.
The multigraph on V with a self-loop at every vertex for each label i : E, and no other
edge: its rotation map is the identity.
Instances For
G with a self-loop added at every vertex for each label i : E: the union of G with
loops V E.
Instances For
The walk operator of G with |E| self-loops added at every vertex stays put with
probability |E| / (|D| + |E|) and otherwise takes a step of the walk on G.
Adding self-loops to a multigraph of degree |D|, |E| at every vertex, gives spectral
expansion at most (|D| λ(G) + |E|) / (|D| + |E|).