Combinatorial triangles for posets and fans

This provides several classes and methods to convert between them. Elements of the classes are polynomials in two variables \(x\) and \(y\), possibly with other parameters. The conversion methods amount to specific invertible rational change-of-variables involving \(x\) and \(y\).

These polynomial are called triangles because their supports, the sets of exponents where their coefficients can be nonzero, have a triangular shape.

The M-triangle class is motivated by the generating series of Möbius numbers for graded posets. A typical example is:

sage: W = SymmetricGroup(4)                                                         # needs sage.groups
sage: posets.NoncrossingPartitions(W).M_triangle()                                  # needs sage.graphs sage.groups
M: x^3*y^3 - 6*x^2*y^3 + 6*x^2*y^2 + 10*x*y^3 - 16*x*y^2
- 5*y^3 + 6*x*y + 10*y^2 - 6*y + 1
sage: unicode_art(_)                                                                # needs sage.graphs sage.groups sage.modules
⎛ -5  10  -6   1⎞
⎜ 10 -16   6   0⎟
⎜ -6   6   0   0⎟
⎝  1   0   0   0⎠

>>> from sage.all import *
>>> W = SymmetricGroup(Integer(4))                                                         # needs sage.groups
>>> posets.NoncrossingPartitions(W).M_triangle()                                  # needs sage.graphs sage.groups
M: x^3*y^3 - 6*x^2*y^3 + 6*x^2*y^2 + 10*x*y^3 - 16*x*y^2
- 5*y^3 + 6*x*y + 10*y^2 - 6*y + 1
>>> unicode_art(_)                                                                # needs sage.graphs sage.groups sage.modules
⎛ -5  10  -6   1⎞
⎜ 10 -16   6   0⎟
⎜ -6   6   0   0⎟
⎝  1   0   0   0⎠

The F-triangle class is motivated by the generating series of pure simplicial complexes endowed with a distinguished facet. One can also think about complete fans endowed with a distinguished maximal cone. A typical example is:

sage: # needs sage.graphs sage.modules
sage: C = ClusterComplex(['A',3])
sage: f = C.greedy_facet()
sage: C.F_triangle(f)
F: 5*x^3 + 5*x^2*y + 3*x*y^2 + y^3 + 10*x^2 + 8*x*y + 3*y^2 + 6*x + 3*y + 1
sage: unicode_art(_)
⎛ 1  0  0  0⎞
⎜ 3  3  0  0⎟
⎜ 3  8  5  0⎟
⎝ 1  6 10  5⎠

>>> from sage.all import *
>>> # needs sage.graphs sage.modules
>>> C = ClusterComplex(['A',Integer(3)])
>>> f = C.greedy_facet()
>>> C.F_triangle(f)
F: 5*x^3 + 5*x^2*y + 3*x*y^2 + y^3 + 10*x^2 + 8*x*y + 3*y^2 + 6*x + 3*y + 1
>>> unicode_art(_)
⎛ 1  0  0  0⎞
⎜ 3  3  0  0⎟
⎜ 3  8  5  0⎟
⎝ 1  6 10  5⎠

The H-triangles are related to the F-triangles by a relationship similar to the classical link between the f-vector and the h-vector of a simplicial complex.

The Gamma-triangles are related to the H-triangles by an analog of the relationship between gamma-vectors and h-vectors of flag simplicial complexes.

class sage.combinat.triangles_FHM.F_triangle(poly, variables=None)[source]

Bases: Triangle

Class for the F-triangles.

h()[source]

Return the associated H-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import F_triangle
sage: x,y = polygens(ZZ,'x,y')
sage: ft = F_triangle(1+x+y)
sage: ft.h()
H: x*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import F_triangle
>>> x,y = polygens(ZZ,'x,y')
>>> ft = F_triangle(Integer(1)+x+y)
>>> ft.h()
H: x*y + 1
m()[source]

Return the associated M-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).f()
F: x + y + 1
sage: _.m()
M: x*y - y + 1

sage: H_triangle(x^2*y^2 + 2*x*y + x + 1).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
sage: _.m()
M: x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).f()
F: x + y + 1
>>> _.m()
M: x*y - y + 1

>>> H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
>>> _.m()
M: x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1
parabolic()[source]

Return a parabolic version of the F-triangle.

This is obtained by replacing the variable \(y\) by \(y-1\).

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).f()
F: x + y + 1
sage: _.parabolic()
F: x + y

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).f()
F: x + y + 1
>>> _.parabolic()
F: x + y
vector()[source]

Return the f-vector as a polynomial in one variable.

This is obtained by letting \(y=x\).

EXAMPLES:

sage: from sage.combinat.triangles_FHM import F_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: ft = 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
sage: F_triangle(ft).vector()
5*x^2 + 5*x + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import F_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> ft = Integer(2)*x**Integer(2) + Integer(2)*x*y + y**Integer(2) + Integer(3)*x + Integer(2)*y + Integer(1)
>>> F_triangle(ft).vector()
5*x^2 + 5*x + 1
class sage.combinat.triangles_FHM.Gamma_triangle(poly, variables=None)[source]

Bases: Triangle

Class for the Gamma-triangles.

h()[source]

Return the associated H-triangle.

The transition between Gamma-triangles and H-triangles is defined by

\[H(x,y) = (1+x)^d \sum_{0\leq i; 0\leq j \leq d-2i} \gamma_{i,j} \left(\frac{x}{(1+x)^2}\right)^i \left(\frac{1+xy}{1+x}\right)^j\]

EXAMPLES:

sage: from sage.combinat.triangles_FHM import Gamma_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: g = y**2 + x
sage: Gamma_triangle(g).h()
H: x^2*y^2 + 2*x*y + x + 1

sage: a, b = polygen(ZZ, 'a, b')
sage: x, y = polygens(a.parent(),'x,y')
sage: g = Gamma_triangle(y**3+a*x*y+b*x,(x,y))
sage: hh = g.h()
sage: hh.gamma() == g
True

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import Gamma_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> g = y**Integer(2) + x
>>> Gamma_triangle(g).h()
H: x^2*y^2 + 2*x*y + x + 1

>>> a, b = polygen(ZZ, 'a, b')
>>> x, y = polygens(a.parent(),'x,y')
>>> g = Gamma_triangle(y**Integer(3)+a*x*y+b*x,(x,y))
>>> hh = g.h()
>>> hh.gamma() == g
True
vector()[source]

Return the gamma-vector as a polynomial in one variable.

This is obtained by letting \(y=1\).

EXAMPLES:

sage: from sage.combinat.triangles_FHM import Gamma_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: gt = y**2 + x
sage: Gamma_triangle(gt).vector()
x + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import Gamma_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> gt = y**Integer(2) + x
>>> Gamma_triangle(gt).vector()
x + 1
class sage.combinat.triangles_FHM.H_triangle(poly, variables=None)[source]

Bases: Triangle

Class for the H-triangles.

f()[source]

Return the associated F-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).f()
F: x + y + 1
sage: H_triangle(x^2*y^2 + 2*x*y + x + 1).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
sage: flo = H_triangle(1+4*x+2*x**2+x*y*(4+8*x)+
....:   x**2*y**2*(6+4*x)+4*(x*y)**3+(x*y)**4).f(); flo
F: 7*x^4 + 12*x^3*y + 10*x^2*y^2 + 4*x*y^3 + y^4 + 20*x^3
+ 28*x^2*y + 16*x*y^2 + 4*y^3 + 20*x^2 + 20*x*y
+ 6*y^2 + 8*x + 4*y + 1
sage: flo(-1-x,-1-y) == flo
True

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).f()
F: x + y + 1
>>> H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)).f()
F: 2*x^2 + 2*x*y + y^2 + 3*x + 2*y + 1
>>> flo = H_triangle(Integer(1)+Integer(4)*x+Integer(2)*x**Integer(2)+x*y*(Integer(4)+Integer(8)*x)+
...   x**Integer(2)*y**Integer(2)*(Integer(6)+Integer(4)*x)+Integer(4)*(x*y)**Integer(3)+(x*y)**Integer(4)).f(); flo
F: 7*x^4 + 12*x^3*y + 10*x^2*y^2 + 4*x*y^3 + y^4 + 20*x^3
+ 28*x^2*y + 16*x*y^2 + 4*y^3 + 20*x^2 + 20*x*y
+ 6*y^2 + 8*x + 4*y + 1
>>> flo(-Integer(1)-x,-Integer(1)-y) == flo
True
gamma()[source]

Return the associated Gamma-triangle.

In some cases, this is a more condensed way to encode the same amount of information.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: ht = x**2*y**2 + 2*x*y + x + 1
sage: H_triangle(ht).gamma()
Γ: y^2 + x

sage: W = SymmetricGroup(5)                                                 # needs sage.groups
sage: P = posets.NoncrossingPartitions(W)                                   # needs sage.graphs sage.groups
sage: P.M_triangle().h().gamma()                                            # needs sage.graphs sage.groups
Γ: y^4 + 3*x*y^2 + 2*x^2 + 2*x*y + x

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> ht = x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)
>>> H_triangle(ht).gamma()
Γ: y^2 + x

>>> W = SymmetricGroup(Integer(5))                                                 # needs sage.groups
>>> P = posets.NoncrossingPartitions(W)                                   # needs sage.graphs sage.groups
>>> P.M_triangle().h().gamma()                                            # needs sage.graphs sage.groups
Γ: y^4 + 3*x*y^2 + 2*x^2 + 2*x*y + x
m()[source]

Return the associated M-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: h = polygen(ZZ, 'h')
sage: x, y = polygens(h.parent(),'x,y')
sage: ht = H_triangle(x^2*y^2 + 2*x*y + 2*x*h - 4*x + 1, variables=[x,y])
sage: ht.m()
M: x^2*y^2 + (-2*h + 2)*x*y^2 + (2*h - 2)*x*y
+ (2*h - 3)*y^2 + (-2*h + 2)*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> h = polygen(ZZ, 'h')
>>> x, y = polygens(h.parent(),'x,y')
>>> ht = H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + Integer(2)*x*h - Integer(4)*x + Integer(1), variables=[x,y])
>>> ht.m()
M: x^2*y^2 + (-2*h + 2)*x*y^2 + (2*h - 2)*x*y
+ (2*h - 3)*y^2 + (-2*h + 2)*y + 1
transpose()[source]

Return the transposed H-triangle.

OUTPUT: another H-triangle

This operation is an involution. When seen as a matrix, it performs a symmetry with respect to the northwest-southeast diagonal.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: H_triangle(1+x*y).transpose()
H: x*y + 1
sage: H_triangle(x^2*y^2 + 2*x*y + x + 1).transpose()
H: x^2*y^2 + x^2*y + 2*x*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> H_triangle(Integer(1)+x*y).transpose()
H: x*y + 1
>>> H_triangle(x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)).transpose()
H: x^2*y^2 + x^2*y + 2*x*y + 1
vector()[source]

Return the h-vector as a polynomial in one variable.

This is obtained by letting \(y=1\).

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygen(ZZ,'x,y')
sage: ht = x**2*y**2 + 2*x*y + x + 1
sage: H_triangle(ht).vector()
x^2 + 3*x + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygen(ZZ,'x,y')
>>> ht = x**Integer(2)*y**Integer(2) + Integer(2)*x*y + x + Integer(1)
>>> H_triangle(ht).vector()
x^2 + 3*x + 1
class sage.combinat.triangles_FHM.M_triangle(poly, variables=None)[source]

Bases: Triangle

Class for the M-triangles.

This is motivated by generating series of Möbius numbers of graded posets.

EXAMPLES:

sage: x, y = polygens(ZZ, 'x,y')
sage: P = Poset({2: [1]})                                                       # needs sage.graphs
sage: P.M_triangle()                                                            # needs sage.graphs
M: x*y - y + 1

>>> from sage.all import *
>>> x, y = polygens(ZZ, 'x,y')
>>> P = Poset({Integer(2): [Integer(1)]})                                                       # needs sage.graphs
>>> P.M_triangle()                                                            # needs sage.graphs
M: x*y - y + 1
dual()[source]

Return the dual M-triangle.

This is the M-triangle of the dual poset, hence an involution.

When seen as a matrix, this performs a symmetry with respect to the northwest-southeast diagonal.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import  M_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: mt = M_triangle(x*y - y + 1)
sage: mt.dual() == mt
True

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import  M_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> mt = M_triangle(x*y - y + Integer(1))
>>> mt.dual() == mt
True
f()[source]

Return the associated F-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import M_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: M_triangle(1-y+x*y).f()
F: x + y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import M_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> M_triangle(Integer(1)-y+x*y).f()
F: x + y + 1
h()[source]

Return the associated H-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import M_triangle
sage: x, y = polygens(ZZ,'x,y')
sage: M_triangle(1-y+x*y).h()
H: x*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import M_triangle
>>> x, y = polygens(ZZ,'x,y')
>>> M_triangle(Integer(1)-y+x*y).h()
H: x*y + 1
transmute()[source]

Return the image of self by an involution.

OUTPUT: another M-triangle

The involution is defined by converting to an H-triangle, transposing the matrix, and then converting back to an M-triangle.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import  M_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: nc3 = x^2*y^2 - 3*x*y^2 + 3*x*y + 2*y^2 - 3*y + 1
sage: m = M_triangle(nc3)
sage: m2 = m.transmute(); m2                                                # needs sage.libs.flint
M: 2*x^2*y^2 - 3*x*y^2 + 2*x*y + y^2 - 2*y + 1
sage: m2.transmute() == m                                                   # needs sage.libs.flint
True

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import  M_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> nc3 = x**Integer(2)*y**Integer(2) - Integer(3)*x*y**Integer(2) + Integer(3)*x*y + Integer(2)*y**Integer(2) - Integer(3)*y + Integer(1)
>>> m = M_triangle(nc3)
>>> m2 = m.transmute(); m2                                                # needs sage.libs.flint
M: 2*x^2*y^2 - 3*x*y^2 + 2*x*y + y^2 - 2*y + 1
>>> m2.transmute() == m                                                   # needs sage.libs.flint
True
class sage.combinat.triangles_FHM.Triangle(poly, variables=None)[source]

Bases: SageObject

Common class for different kinds of triangles.

This serves as a base class for F-triangles, H-triangles, M-triangles and Gamma-triangles.

The user should use these subclasses directly.

The input is a polynomial in two variables. One can also give a polynomial with more variables and specify two chosen variables.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import Triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: ht = Triangle(1+4*x+2*x*y)
sage: unicode_art(ht)                                                           # needs sage.modules
⎛0 2⎞
⎝1 4⎠

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import Triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> ht = Triangle(Integer(1)+Integer(4)*x+Integer(2)*x*y)
>>> unicode_art(ht)                                                           # needs sage.modules
⎛0 2⎞
⎝1 4⎠
matrix()[source]

Return the associated matrix for display.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: h = H_triangle(1+2*x*y)
sage: h.matrix()                                                            # needs sage.modules
[0 2]
[1 0]

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> h = H_triangle(Integer(1)+Integer(2)*x*y)
>>> h.matrix()                                                            # needs sage.modules
[0 2]
[1 0]
polynomial()[source]

Return the triangle as a bare polynomial.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: h = H_triangle(1+2*x*y)
sage: h.polynomial()
2*x*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> h = H_triangle(Integer(1)+Integer(2)*x*y)
>>> h.polynomial()
2*x*y + 1
truncate(d)[source]

Return the truncated triangle.

INPUT:

  • d – integer

As a polynomial, this means that all monomials with a power of either \(x\) or \(y\) greater than or equal to d are dismissed.

EXAMPLES:

sage: from sage.combinat.triangles_FHM import H_triangle
sage: x, y = polygens(ZZ, 'x,y')
sage: h = H_triangle(1+2*x*y)
sage: h.truncate(2)
H: 2*x*y + 1

>>> from sage.all import *
>>> from sage.combinat.triangles_FHM import H_triangle
>>> x, y = polygens(ZZ, 'x,y')
>>> h = H_triangle(Integer(1)+Integer(2)*x*y)
>>> h.truncate(Integer(2))
H: 2*x*y + 1