Hide keyboard shortcuts

Hot-keys on this page

r m x p   toggle line displays

j k   next/prev highlighted chunk

0   (zero) top of page

1   (one) first highlighted chunk

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

r""" 

Associahedron 

 

.. TODO:: 

 

- fix adjacency matrix 

- edit graph method to get proper vertex labellings 

- UniqueRepresentation? 

 

AUTHORS: 

 

- Christian Stump 

""" 

#***************************************************************************** 

# Copyright (C) 2011-2012 Christian Stump <christian.stump@gmail.com> 

# 

# Distributed under the terms of the GNU General Public License (GPL) 

# The full text of the GPL is available at: 

# 

# http://www.gnu.org/licenses/ 

#***************************************************************************** 

from sage.geometry.polyhedron.backend_ppl import Polyhedron_QQ_ppl 

from sage.geometry.polyhedron.parent import Polyhedra_QQ_ppl 

from sage.combinat.root_system.cartan_type import CartanType 

from sage.modules.free_module_element import vector 

from sage.rings.all import QQ 

 

 

def Associahedron(cartan_type): 

r""" 

Construct an associahedron. 

 

The generalized associahedron is a polytopal complex with vertices in 

one-to-one correspondence with clusters in the cluster complex, and with 

edges between two vertices if and only if the associated two clusters 

intersect in codimension 1. 

 

The associahedron of type `A_n` is one way to realize the classical 

associahedron as defined in the :wikipedia:`Associahedron`. 

 

A polytopal realization of the associahedron can be found in [CFZ]_. The 

implementation is based on [CFZ]_, Theorem 1.5, Remark 1.6, and Corollary 

1.9. 

 

EXAMPLES:: 

 

sage: Asso = polytopes.associahedron(['A',2]); Asso 

Generalized associahedron of type ['A', 2] with 5 vertices 

 

sage: sorted(Asso.Hrepresentation(), key=repr) 

[An inequality (-1, 0) x + 1 >= 0, 

An inequality (0, -1) x + 1 >= 0, 

An inequality (0, 1) x + 1 >= 0, 

An inequality (1, 0) x + 1 >= 0, 

An inequality (1, 1) x + 1 >= 0] 

 

sage: Asso.Vrepresentation() 

(A vertex at (1, -1), A vertex at (1, 1), A vertex at (-1, 1), 

A vertex at (-1, 0), A vertex at (0, -1)) 

 

sage: polytopes.associahedron(['B',2]) 

Generalized associahedron of type ['B', 2] with 6 vertices 

 

The two pictures of [CFZ]_ can be recovered with:: 

 

sage: Asso = polytopes.associahedron(['A',3]); Asso 

Generalized associahedron of type ['A', 3] with 14 vertices 

sage: Asso.plot() 

Graphics3d Object 

 

sage: Asso = polytopes.associahedron(['B',3]); Asso 

Generalized associahedron of type ['B', 3] with 20 vertices 

sage: Asso.plot() 

Graphics3d Object 

 

TESTS:: 

 

sage: sorted(polytopes.associahedron(['A',3]).vertices()) 

[A vertex at (-3/2, 0, -1/2), A vertex at (-3/2, 0, 3/2), 

A vertex at (-3/2, 1, -3/2), A vertex at (-3/2, 2, -3/2), 

A vertex at (-3/2, 2, 3/2), A vertex at (-1/2, -1, -1/2), 

A vertex at (-1/2, 0, -3/2), A vertex at (1/2, -2, 1/2), 

A vertex at (1/2, -2, 3/2), A vertex at (3/2, -2, 1/2), 

A vertex at (3/2, -2, 3/2), A vertex at (3/2, 0, -3/2), 

A vertex at (3/2, 2, -3/2), A vertex at (3/2, 2, 3/2)] 

 

sage: sorted(polytopes.associahedron(['B',3]).vertices()) 

[A vertex at (-3, 0, 0), A vertex at (-3, 0, 3), 

A vertex at (-3, 2, -2), A vertex at (-3, 4, -3), 

A vertex at (-3, 5, -3), A vertex at (-3, 5, 3), 

A vertex at (-2, 1, -2), A vertex at (-2, 3, -3), 

A vertex at (-1, -2, 0), A vertex at (-1, -1, -1), 

A vertex at (1, -4, 1), A vertex at (1, -3, 0), 

A vertex at (2, -5, 2), A vertex at (2, -5, 3), 

A vertex at (3, -5, 2), A vertex at (3, -5, 3), 

A vertex at (3, -3, 0), A vertex at (3, 3, -3), 

A vertex at (3, 5, -3), A vertex at (3, 5, 3)] 

 

sage: polytopes.associahedron(['A',4]).f_vector() 

(1, 42, 84, 56, 14, 1) 

sage: polytopes.associahedron(['B',4]).f_vector() 

(1, 70, 140, 90, 20, 1) 

""" 

cartan_type = CartanType(cartan_type) 

parent = Associahedra(QQ, cartan_type.rank(), 'ppl') 

return parent(cartan_type) 

 

 

class Associahedron_class(Polyhedron_QQ_ppl): 

r""" 

The Python class of an associahedron 

 

You should use the :func:`Associahedron` convenience function to 

construct associahedra from the Cartan type. 

 

TESTS:: 

 

sage: Asso = polytopes.associahedron(['A',2]); Asso 

Generalized associahedron of type ['A', 2] with 5 vertices 

sage: TestSuite(Asso).run() 

""" 

 

def _repr_(self): 

r""" 

Return a string representation of ``self``. 

 

EXAMPLES:: 

 

sage: polytopes.associahedron(['A',3])._repr_() 

"Generalized associahedron of type ['A', 3] with 14 vertices" 

""" 

msg = 'Generalized associahedron of type {} with {} vertices' 

return msg.format(self._cartan_type, self.n_vertices()) 

 

def cartan_type(self): 

r""" 

Return the Cartan type of ``self``. 

 

EXAMPLES:: 

 

sage: polytopes.associahedron(['A',3]).cartan_type() 

['A', 3] 

""" 

return self._cartan_type 

 

def vertices_in_root_space(self): 

r""" 

Return the vertices of ``self`` as elements in the root space. 

 

EXAMPLES:: 

 

sage: Asso = polytopes.associahedron(['A',2]) 

sage: Asso.vertices() 

(A vertex at (1, -1), A vertex at (1, 1), 

A vertex at (-1, 1), A vertex at (-1, 0), 

A vertex at (0, -1)) 

 

sage: Asso.vertices_in_root_space() 

(alpha[1] - alpha[2], alpha[1] + alpha[2], -alpha[1] + alpha[2], 

-alpha[1], -alpha[2]) 

""" 

root_space = self._cartan_type.root_system().root_space() 

return tuple(root_space.from_vector(vector(V)) 

for V in self.vertex_generator()) 

 

 

class Associahedra(Polyhedra_QQ_ppl): 

""" 

Parent of Associahedra of specified dimension 

 

EXAMPLES:: 

 

sage: from sage.combinat.root_system.associahedron import Associahedra 

sage: parent = Associahedra(QQ,2,'ppl'); parent 

Polyhedra in QQ^2 

sage: type(parent) 

<class 'sage.combinat.root_system.associahedron.Associahedra_with_category'> 

sage: parent(['A',2]) 

Generalized associahedron of type ['A', 2] with 5 vertices 

 

Importantly, the parent knows the dimension of the ambient 

space. If you try to construct an associahedron of a different 

dimension, a ``ValueError`` is raised:: 

 

sage: parent(['A',3]) 

Traceback (most recent call last): 

... 

ValueError: V-representation data requires a list of length ambient_dim 

""" 

Element = Associahedron_class 

 

def _element_constructor_(self, cartan_type, **kwds): 

""" 

The element constructor. 

 

This method is called internally when we try to convert 

something into an element. In this case, the only thing that 

can be converted into an associahedron is the Cartan type. 

 

EXAMPLES:: 

 

sage: from sage.combinat.root_system.associahedron import Associahedra 

sage: parent = Associahedra(QQ,2,'ppl') 

sage: parent(['A',2]) 

Generalized associahedron of type ['A', 2] with 5 vertices 

sage: parent._element_constructor_(['A',2]) 

Generalized associahedron of type ['A', 2] with 5 vertices 

""" 

cartan_type = CartanType(cartan_type) 

if not cartan_type.is_finite(): 

raise ValueError("the Cartan type must be finite") 

root_space = cartan_type.root_system().root_space() 

# TODO: generalize this as a method of root lattice realization 

rhocheck = sum(beta.associated_coroot() 

for beta in root_space.positive_roots()) / 2 

I = root_space.index_set() 

inequalities = [] 

for orbit in root_space.almost_positive_roots_decomposition(): 

c = rhocheck.coefficient(orbit[0].leading_support()) 

for beta in orbit: 

inequalities.append([c] + [beta.coefficient(i) for i in I]) 

associahedron = super(Associahedra, self)._element_constructor_(None, [inequalities, []]) 

associahedron._cartan_type = cartan_type 

return associahedron