1 /* Copyright (c) 1997-2021 2 Ewgenij Gawrilow, Michael Joswig, and the polymake team 3 Technische Universität Berlin, Germany 4 https://polymake.org 5 6 This program is free software; you can redistribute it and/or modify it 7 under the terms of the GNU General Public License as published by the 8 Free Software Foundation; either version 2, or (at your option) any 9 later version: http://www.gnu.org/licenses/gpl.txt. 10 11 This program is distributed in the hope that it will be useful, 12 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 GNU General Public License for more details. 15 -------------------------------------------------------------------------------- 16 */ 17 18 #include "polymake/client.h" 19 #include "polymake/Integer.h" 20 #include "polymake/topaz/multi_associahedron_sphere.h" 21 22 namespace polymake { namespace topaz { 23 24 using namespace multi_associahedron_sphere_utils; 25 26 BigObject 27 multi_associahedron_sphere(Int n, Int k, OptionSet options) 28 { 29 const Int 30 m (n*(n-1)/2-n*k), // the number of vertices = relevant diagonals 31 nu (n-2*k-1), // the complexity measure 32 dim(k*nu-1); // the dimension of the sphere 33 34 const bool no_facets = options["no_facets"]; 35 const bool no_crossings = options["no_crossings"]; exchangePath(const graph::ShrinkingLattice<graph::lattice::BasicDecoration> & M,MorseEdgeMap & EM,const Array<Int> & p,Int u,Int v,Int & size)36 37 if (k<=0) throw std::runtime_error("multi_associahedron_sphere: require k>=1"); 38 if (m<=0) throw std::runtime_error("multi_associahedron_sphere: require (n choose 2) > n*k"); 39 assert(n>=3); 40 41 DiagonalIndex index_of; 42 DiagonalList diagonals; diagonals.reserve(m); 43 DiagonalLabels labels; labels.reserve(m); 44 prepare_diagonal_data(n, k, index_of, diagonals, labels); 45 assert(index_of.size() == size_t(m)); 46 47 BigObject ind_Aut("group::Group"); 48 BigObject induced_action("group::PermutationAction"); 49 Array<Array<Int>> igens; 50 51 if (nu > 1) { 52 BigObject Aut = group::dihedral_group(2*n); 53 const Array<Array<Int>> gens = Aut.give("PERMUTATION_ACTION.GENERATORS"); 54 igens = induced_action_gens_impl(gens, diagonals, index_of); 55 56 induced_action.set_description("action of D_" + std::to_string(2*n) 57 + " on the vertices of the simplicial complex, induced by the action of D_" 58 + std::to_string(2*n) + " on the vertices of the polygon"); 59 60 const group::ConjugacyClassReps<> class_reps = Aut.give("PERMUTATION_ACTION.CONJUGACY_CLASS_REPRESENTATIVES"); 61 group::ConjugacyClassReps<> induced_ccr(class_reps.size()); 62 auto iicr_it = entire(induced_ccr); checkAcyclicDFS(const graph::ShrinkingLattice<graph::lattice::BasicDecoration> & M,const MorseEdgeMap & EM,Array<Int> & marked,Int v,bool lower,Int base)63 for (const auto& r: class_reps) { 64 *iicr_it = induced_gen(r, diagonals, index_of); 65 ++iicr_it; 66 } 67 induced_action.take("CONJUGACY_CLASS_REPRESENTATIVES") << induced_ccr; 68 ind_Aut.take("CHARACTER_TABLE") << group::dn_character_table(2*n); 69 ind_Aut.take("ORDER") << 2*n; 70 } else { 71 induced_action.set_description("action of S" + std::to_string(m) 72 + " on the vertices of the simplicial complex, induced by the action of D_" 73 + std::to_string(2*n) + " on the vertices of the polygon"); 74 igens = group::symmetric_group_gens(m); 75 if (m<8) { 76 induced_action.take("CONJUGACY_CLASS_REPRESENTATIVES") << group::sn_reps(m); 77 ind_Aut.take("CHARACTER_TABLE") << group::sn_character_table(m); 78 } 79 ind_Aut.take("ORDER") << Integer::fac(m); 80 } 81 82 induced_action.take("GENERATORS") << igens; 83 ind_Aut.take("PERMUTATION_ACTION") << induced_action; 84 85 hash_set<Set<Int>> lower_rep_level, k_plus_1_crossings; 86 87 if (!no_crossings || !no_facets) { 88 // accumulate all k-cliques, to prepare for calculating the (k+1)-crossings and the f-vector 89 for (auto cit = entire(all_subsets_of_k(sequence(0,m), k)); !cit.at_end(); ++cit) 90 lower_rep_level += *cit; 91 } 92 93 if (!no_crossings) { 94 // now calculate the (k+1)-crossings 95 for (const auto& c : lower_rep_level) 96 for (Int d_index = 0; d_index < m; ++d_index) 97 if (!c.contains(d_index) && contains_new_k_plus_1_crossing(d_index, k, c, diagonals)) 98 k_plus_1_crossings += group::unordered_orbit<group::on_container>(igens, Set<Int>(c+d_index)); 99 } 100 101 Array<Int> f_vector(dim+1); 102 103 if (!no_facets) { 104 // the complex is k-neighborly, so we know part of the f-vector 105 auto fvec_it = f_vector.begin(); 106 *fvec_it++ = m; 107 for (Int kk = 2; kk <= k; ++kk) 108 *fvec_it++ = Int(Integer::binom(m,kk)); 109 110 // build up the face lattice in layers, starting from representatives of the k-cliques 111 for (Int n_vertices = k+1; n_vertices <= dim+1; ++n_vertices) { 112 hash_set<Set<Int>> upper_rep_level; 113 for (const auto& c : lower_rep_level) 114 for (Int d_index = 0; d_index < m; ++d_index) 115 if (!c.contains(d_index) && !contains_new_k_plus_1_crossing(d_index, k, c, diagonals)) 116 upper_rep_level += group::unordered_orbit<group::on_container>(igens, Set<Int>(c+d_index)); 117 118 *fvec_it++ = upper_rep_level.size(); 119 lower_rep_level = upper_rep_level; 120 } 121 } 122 123 BigObject s("SimplicialComplex"); 124 s.set_description() << "Simplicial complex of " << k << "-triangulations of a convex " << n << "-gon" << endl; 125 s.take("N_VERTICES") << m; 126 s.take("VERTEX_LABELS") << labels; 127 s.take("DIM") << dim; 128 s.take("PURE") << true; 129 s.take("SPHERE") << true; 130 s.take("GROUP") << ind_Aut; 131 132 if (!no_crossings) { 133 s.attach("K_PLUS_1_CROSSINGS") << Set<Set<Int>>(entire(k_plus_1_crossings)); 134 } 135 136 if (!no_facets) { 137 s.take("FACETS") << Set<Set<Int>>(entire(lower_rep_level)); findMaximumForest(const Graph<Undirected> & G,const EdgeMap<Undirected,Int> & EM,Array<Int> & p,Array<Int> & visited)138 s.take("F_VECTOR") << f_vector; 139 } 140 141 return s; 142 } 143 144 UserFunction4perl("# @category Producing from scratch" 145 "# Produce the simplicial sphere //Δ(n,k)// of (//k//+1)-crossing free multitriangulations" 146 "# of an //n//-gon //P//, along with the group action on the diagonals induced from //D//_{2//n//}." 147 "# //Δ(n,k)// is the simplicial complex on the set of relevant diagonals of //P// whose faces are those sets" 148 "# of diagonals such that no //k//+1 of them mutually cross. A diagonal is //relevant// if it leaves" 149 "# //k// or more vertices of //P// on both sides. (Any diagonal having less than //k// vertices on one" 150 "# side trivially cannot participate in a (//k//+1)-crossing, so is //irrelevant//. The corresponding" 151 "# complex on //all// diagonals is therefore the simplicial join of this one with the simplex of irrelevant" 152 "# diagonals.)" 153 "# \t Jakob Jonsson, \"Generalized triangulations and diagonal-free subsets of stack polyominoes\"," 154 "# \t J. Combin. Theory Ser. A, 112(1):117–142, 2005" 155 "# //Δ(n,k)// is known to be a //k//-neighborly vertex-decomposable sphere of dimension //k//ν-1," 156 "# where the parameter ν=//n//-2//k//-1 measures the complexity of this construction." 157 "# For ν=0, the complex is a point; for ν=1 a //k//-simplex; for ν=2 the boundary of a cyclic polytope." 158 "# Setting //k//=1 yields the boundary of the simplicial associahedron." 159 "# The list of (//k//+1)-crossings in the //n//-gon is included as the attachment K_PLUS_1_CROSSINGS. It can" 160 "# also be obtained as the property MINIMAL_NON_FACES, but this requires the HASSE_DIAGRAM to be computed." 161 "# @param Int n the number of vertices of the polygon" 162 "# @param Int k the number of diagonals that are allowed to mutually cross" 163 "# @option Bool no_facets don't calculate the facets (for large examples)? Default 0" 164 "# @option Bool no_crossings don't calculate the crossings? Default 0" 165 "# @return SimplicialComplex" 166 "# @example The f-vector of Δ(9,3) is that of a neighborly polytope, since ν=2:" 167 "# > print multi_associahedron_sphere(9,3)->F_VECTOR;" 168 "# | 9 36 84 117 90 30" 169 "# @example The option no_facets=>1 still leaves useful information:" 170 "# > $s = multi_associahedron_sphere(8,2, no_facets=>1);" 171 "# > print $s->VERTEX_LABELS;" 172 "# | (0 3) (1 4) (2 5) (3 6) (4 7) (0 5) (1 6) (2 7) (0 4) (1 5) (2 6) (3 7)" 173 "# > print $s->GROUP->PERMUTATION_ACTION->GENERATORS;" 174 "# | 7 0 1 2 3 4 5 6 11 8 9 10" 175 "# | 4 3 2 1 0 7 6 5 11 10 9 8" 176 "# > print $s->get_attachment(\"K_PLUS_1_CROSSINGS\")->size();" 177 "# | 28" 178 , 179 &multi_associahedron_sphere, 180 "multi_associahedron_sphere($$ { no_facets=>0, no_crossings=>0 })"); 181 182 } } 183 184 // Local Variables: 185 // mode:C++ 186 // c-basic-offset:3 187 // indent-tabs-mode:nil 188 // End: 189