Partial Shift Graph

partial_shift_graph_vertices(F::Field,K::SimplicialComplex, W::Union{WeylGroup, Vector{WeylGroupElem}};)
partial_shift_graph_vertices(F::Field,K::UniformHypergraph, W::Union{WeylGroup, Vector{WeylGroupElem}};)

Given a field F find the vertices of the partial shift graph starting from K and discoverable from elements in W. Returns a Vector{SimplicialCompplex} ordered lexicographically.

Examples

julia> K = simplicial_complex([[1, 2], [2, 3], [3, 4]])
Abstract simplicial complex of dimension 1 on 4 vertices

julia> shifts = partial_shift_graph_vertices(QQ, K, weyl_group(:A, 3))
6-element Vector{SimplicialComplex}:
 Abstract simplicial complex of dimension 1 on 4 vertices
 Abstract simplicial complex of dimension 1 on 4 vertices
 Abstract simplicial complex of dimension 1 on 4 vertices
 Abstract simplicial complex of dimension 1 on 4 vertices
 Abstract simplicial complex of dimension 1 on 4 vertices
 Abstract simplicial complex of dimension 1 on 4 vertices

julia> facets.(shifts)
6-element Vector{Vector{Set{Int64}}}:
 [Set([3, 1]), Set([4, 1]), Set([2, 1])]
 [Set([3, 1]), Set([2, 3]), Set([2, 1]), Set([4])]
 [Set([3, 1]), Set([4, 2]), Set([2, 1])]
 [Set([4, 3]), Set([3, 1]), Set([2, 1])]
 [Set([2, 1]), Set([2, 3]), Set([4, 2])]
 [Set([2, 1]), Set([2, 3]), Set([4, 3])]

partial_shift_graph(F::Field, complexes::Vector{Simplicialcomplex}; parallel=false, show_progress=true)
partial_shift_graph(F::Field, complexes::Vector{Uniformhypergraph}; parallel=false, show_progress=true)
partial_shift_graph(F::Field, complexes::Vector{Simplicialcomplex}, W::Union{WeylGroup, Vector{WeylGroupElem}}; parallel=false, show_progress=true)
partial_shift_graph(F::Field, complexes::Vector{Uniformhypergraph}, W::Union{WeylGroup, Vector{WeylGroupElem}}; parallel=false, show_progress=true)

Constructs the partial shift graph on complexes.

Returns a tuple (G, EL, VL), where G is a Graph{Directed}, EL is a Dict{Tuple{Int Int}, Vector{Weylgroupelem} and VL is a lexicographically sorted complexes, hence is either a Vector{SimplicialComplex} or Vector{Uniformhypergraph}. EL are the edges labels and VL are the vertex labels. There is an edge from the vertex labelled K to the vertex labelled L if L is the partial shift of K by some w in W. If K and L are the ith and jth entry of VL, resp., EL[i,j] contains all w in W such that L is the partial generic shift of K by w.

Arguments

• complexes: A vector of simplicial complexes or uniform hypergraphs (all should have the same number of vertices).
• W: The user may provide a list W of Weyl group elements to be used to construct the shifts. All elements of W should have the same parent. W must be a subset the (same instance of the) symmetric group of order equal to the number of vertices of a complex in complexes (they should all be equal). If W is not provided, the function will use the symmetric group of the same order as vertices in each complex complexes.
• parallel: run the process in parrallel using the Distributed package; make sure to do @everywhere using Oscar.
• show_progress: Set to true by default, can be used to suppress progress meter.
• task_size: While running in parallel serialization might become a bottleneck,

setting a higher task_size should increase performance if the processes are not running at maximum capacity See [D-VJL24] for background.

Examples

julia> gamma(n,k,l) = uniform_hypergraph.(subsets(subsets(n, k), l), n)
gamma (generic function with 1 method)

julia> Ks = gamma(4,2,5)
6-element Vector{UniformHypergraph}:
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 4], [2, 3], [2, 4], [3, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [1, 4], [2, 4], [3, 4]])
 UniformHypergraph(4, 2, [[1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])

julia> G, EL, VL = partial_shift_graph(QQ, Ks; show_progress=false);

julia> collect(edges(G))
14-element Vector{Edge}:
 Edge(2, 1)
 Edge(3, 1)
 Edge(3, 2)
 Edge(4, 1)
 Edge(4, 2)
 Edge(5, 1)
 Edge(5, 2)
 Edge(5, 3)
 Edge(5, 4)
 Edge(6, 1)
 Edge(6, 2)
 Edge(6, 3)
 Edge(6, 4)
 Edge(6, 5)

julia> EL[6, 5]
4-element Vector{WeylGroupElem}:
 s1 * s2
 s2
 s3 * s1 * s2
 s3 * s2

julia> facets.(VL[[6, 5]])
2-element Vector{Vector{Set{Int64}}}:
 [Set([3, 1]), Set([4, 1]), Set([2, 3]), Set([4, 2]), Set([4, 3])]
 [Set([2, 1]), Set([4, 1]), Set([2, 3]), Set([4, 2]), Set([4, 3])]

contracted_partial_shift_graph(G::Graph{Directed}, edge_labels::Dict{Tuple{Int, Int}, Vector{WeylGroupElem}})

Returns a triple (CG, S, P), where CG is a graph that contains a vertex v for every vertex S[v] in G. S is a list of indices for the sinks in the original graph G. A vertex i is in P[s] if there exists an edge from i to s in G with w0 in its edge label, in this way P is a partition of the vertices of the orignal graph G. There is an edge from s to t in CG whenever there is an edge from i to j in G and i in P[s] and j in P[t]. See [D-VJL24] for background.

Examples

julia> gamma(n,k,l) = uniform_hypergraph.(subsets(subsets(n, k), l), n)
gamma (generic function with 1 method)

julia> Ks = gamma(4,2,5)
6-element Vector{UniformHypergraph}:
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [2, 3], [2, 4], [3, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 4], [2, 3], [2, 4], [3, 4]])
 UniformHypergraph(4, 2, [[1, 2], [1, 3], [1, 4], [2, 4], [3, 4]])
 UniformHypergraph(4, 2, [[1, 3], [1, 4], [2, 3], [2, 4], [3, 4]])

julia> G, EL, VL = partial_shift_graph(QQ, Ks; show_progress=false);

julia> contracted_partial_shift_graph(G, EL)
(Directed graph with 1 nodes and 0 edges, [1], [[5, 4, 6, 2, 3, 1]])