Chow ring ideals of matroids¶
AUTHORS:
Shriya M
- class sage.matroids.chow_ring_ideal.AugmentedChowRingIdeal_atom_free(M, R)[source]¶
Bases:
ChowRingIdeal
The augmented Chow ring ideal for a matroid \(M\) over ring \(R\) in the atom-free presentation.
The augmented Chow ring ideal in the atom-free presentation for a matroid \(M\) is defined as the ideal \(I_{af}(M)\) of the polynomial ring:
\[R[x_{F_1}, \ldots, x_{F_k}],\]where \(F_1, \ldots, F_k\) are the non-empty flats of \(M\) and \(I_{af}(M)\) is the ideal generated by
all quadratic monomials \(x_{F} x_{F'}\) for all incomparable elements \(F\) and \(F'\) in the lattice of flats,
for all flats \(F\) and \(i \in E \setminus F\)
\[x_F \sum_{i \in F'} x_{F'}\]and for all \(i \in E\)
\[\sum_{i \in F'} (x_{F'})^2.\]
REFERENCES:
INPUT:
M
– matroidR
– commutative ring
EXAMPLES:
Augmented Chow ring ideal of Wheel matroid of rank 3:
sage: ch = matroids.Wheel(3).chow_ring(QQ, True, 'atom-free') sage: ch.defining_ideal() Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6 elements with 16 bases in the atom-free presentation
>>> from sage.all import * >>> ch = matroids.Wheel(Integer(3)).chow_ring(QQ, True, 'atom-free') >>> ch.defining_ideal() Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6 elements with 16 bases in the atom-free presentation
- groebner_basis(algorithm='', *args, **kwargs)[source]¶
Return the Groebner basis of
self
.EXAMPLES:
sage: M1 = matroids.Uniform(3,6) sage: ch = M1.chow_ring(QQ, True, 'atom-free') sage: ch.defining_ideal().groebner_basis(algorithm='') Polynomial Sequence with 253 Polynomials in 22 Variables sage: ch.defining_ideal().groebner_basis(algorithm='').is_groebner() True sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
>>> from sage.all import * >>> M1 = matroids.Uniform(Integer(3),Integer(6)) >>> ch = M1.chow_ring(QQ, True, 'atom-free') >>> ch.defining_ideal().groebner_basis(algorithm='') Polynomial Sequence with 253 Polynomials in 22 Variables >>> ch.defining_ideal().groebner_basis(algorithm='').is_groebner() True >>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
- normal_basis(algorithm='', *args, **kwargs)[source]¶
Return the monomial basis of the quotient ring of this ideal.
EXAMPLES:
sage: ch = Matroid(graphs.CycleGraph(3)).chow_ring(QQ, True, 'atom-free') sage: I = ch.defining_ideal() sage: I.normal_basis() [1, A0, A1, A2, A3, A3^2] sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True sage: ch = matroids.Wheel(3).chow_ring(QQ, True, 'atom-free') sage: I = ch.defining_ideal() sage: I.normal_basis() Polynomial Sequence with 30 Polynomials in 14 Variables sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True
>>> from sage.all import * >>> ch = Matroid(graphs.CycleGraph(Integer(3))).chow_ring(QQ, True, 'atom-free') >>> I = ch.defining_ideal() >>> I.normal_basis() [1, A0, A1, A2, A3, A3^2] >>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True >>> ch = matroids.Wheel(Integer(3)).chow_ring(QQ, True, 'atom-free') >>> I = ch.defining_ideal() >>> I.normal_basis() Polynomial Sequence with 30 Polynomials in 14 Variables >>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True
- class sage.matroids.chow_ring_ideal.AugmentedChowRingIdeal_fy(M, R)[source]¶
Bases:
ChowRingIdeal
The augmented Chow ring ideal of matroid \(M\) over ring \(R\) in the Feitchner-Yuzvinsky presentation.
The augmented Chow ring ideal for a matroid \(M\) is defined as the ideal \((I_M + J_M)\) of the following polynomial ring
\[R[y_{e_1}, \ldots, y_{e_n}, x_{F_1}, \ldots, x_{F_k}],\]where
\(F_1, \ldots, F_k\) are the proper flats of \(M\),
\(e_1, \ldots, e_n\) are \(n\) elements of groundset of \(M\),
\(J_M\) is the ideal generated by all quadratic monomials \(x_{F} x_{F'}\), where \(F\) and \(F'\) are incomparable elements in the lattice of flats and \(y_{i} x_F\) for all flats \(F\) and \(i \in E \setminus F\) and
\(I_M\) is the ideal generated by all linear forms
\[y_i - \sum_{i \notin F} x_F\]for all \(i \in E\).
The augmented Chow ring ideal in the Feitchner-Yuzvinsky presentation for a simple matroid \(M\) is defined as the ideal \(I_{FY}(M)\) of the following polynomial ring
\[R[y_{e_1}, \ldots, y_{e_n}, y_{F_1 \cup e}, \ldots, y_{F_k \cup e}],\]where \(F_1, \ldots, F_k\) are the flats of \(M\), \(e_1, \ldots, e_n\) are \(n\) elements of groundset of \(M\), and \(I_{FY}(M)\) is the ideal generated by
all quadratic monomials \(y_{F \cup e} y_{F' \cup e}\), for incomparable elements \(F\) and \(F'\) in the lattice of flats,
\(y_{i} y_{F \cup e}\) for all flats \(F\) and all \(i \in E \setminus F\)
for all \(i \in E\)
\[y_i + \sum_{i \in F} y_{F \cup e}\]and
\[\sum_{F} y_{F \cup e}.\]
Setting \(x_F = y_{F \cup e}\) and using the last linear form to eliminate \(x_E\) recovers the usual presentation of augmented Chow ring of \(M\).
REFERENCES:
INPUT:
M
– matroidR
– commutative ring
EXAMPLES:
Augmented Chow ring ideal of Wheel matroid of rank 3:
sage: ch = matroids.Wheel(3).chow_ring(QQ, True, 'fy') sage: ch.defining_ideal() Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6 elements with 16 bases of Feitchner-Yuzvinsky presentation
>>> from sage.all import * >>> ch = matroids.Wheel(Integer(3)).chow_ring(QQ, True, 'fy') >>> ch.defining_ideal() Augmented Chow ring ideal of Wheel(3): Regular matroid of rank 3 on 6 elements with 16 bases of Feitchner-Yuzvinsky presentation
- groebner_basis(algorithm='', *args, **kwargs)[source]¶
Return the Groebner basis of
self
.EXAMPLES:
sage: ch = matroids.catalog.NonFano().chow_ring(QQ, True, 'fy') sage: ch.defining_ideal().groebner_basis(algorithm='') Polynomial Sequence with 178 Polynomials in 25 Variables sage: ch.defining_ideal().groebner_basis(algorithm='').is_groebner() True sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
>>> from sage.all import * >>> ch = matroids.catalog.NonFano().chow_ring(QQ, True, 'fy') >>> ch.defining_ideal().groebner_basis(algorithm='') Polynomial Sequence with 178 Polynomials in 25 Variables >>> ch.defining_ideal().groebner_basis(algorithm='').is_groebner() True >>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
- normal_basis(algorithm='', *args, **kwargs)[source]¶
Return the monomial basis of the quotient ring of this ideal.
EXAMPLES:
sage: ch = matroids.Uniform(2,5).chow_ring(QQ, True, 'fy') sage: I = ch.defining_ideal() sage: I.normal_basis() [1, B0, B1, B2, B3, B4, B01234, B01234^2] sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True sage: ch = matroids.catalog.Fano().chow_ring(QQ, True, 'fy') sage: I = ch.defining_ideal() sage: I.normal_basis() Polynomial Sequence with 32 Polynomials in 15 Variables sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True
>>> from sage.all import * >>> ch = matroids.Uniform(Integer(2),Integer(5)).chow_ring(QQ, True, 'fy') >>> I = ch.defining_ideal() >>> I.normal_basis() [1, B0, B1, B2, B3, B4, B01234, B01234^2] >>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True >>> ch = matroids.catalog.Fano().chow_ring(QQ, True, 'fy') >>> I = ch.defining_ideal() >>> I.normal_basis() Polynomial Sequence with 32 Polynomials in 15 Variables >>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True
- class sage.matroids.chow_ring_ideal.ChowRingIdeal(ring, gens, coerce=True)[source]¶
Bases:
MPolynomialIdeal
- matroid()[source]¶
Return the matroid of the given Chow ring ideal.
EXAMPLES:
sage: ch = matroids.Uniform(3,6).chow_ring(QQ, False) sage: ch.defining_ideal().matroid() U(3, 6): Matroid of rank 3 on 6 elements with circuit-closures {3: {{0, 1, 2, 3, 4, 5}}}
>>> from sage.all import * >>> ch = matroids.Uniform(Integer(3),Integer(6)).chow_ring(QQ, False) >>> ch.defining_ideal().matroid() U(3, 6): Matroid of rank 3 on 6 elements with circuit-closures {3: {{0, 1, 2, 3, 4, 5}}}
- class sage.matroids.chow_ring_ideal.ChowRingIdeal_nonaug(M, R)[source]¶
Bases:
ChowRingIdeal
The Chow ring ideal of a matroid \(M\).
The Chow ring ideal for a matroid \(M\) is defined as the ideal \((I_M + J_M)\) of the polynomial ring
\[R[x_{F_1}, \ldots, x_{F_k}],\]where
\(F_1, \ldots, F_k\) are the non-empty flats of \(M\),
\(I_M\) is the Stanley-Reisner ideal, i.e., it is generated by products \(x_{F_1}, \ldots, x_{F_t}\) for subsets \(\{F_1, \ldots, F_t\}\) of flats that are not chains, and
\(J_M\) is the ideal generated by all linear forms
\[\sum_{a \in F} x_F\]for all atoms \(a\) in the lattice of flats.
INPUT:
M
– matroidR
– commutative ring
REFERENCES:
EXAMPLES:
Chow ring ideal of uniform matroid of rank 3 on 6 elements:
sage: ch = matroids.Uniform(3,6).chow_ring(QQ, False) sage: ch.defining_ideal() Chow ring ideal of U(3, 6): Matroid of rank 3 on 6 elements with circuit-closures {3: {{0, 1, 2, 3, 4, 5}}} - non augmented sage: ch = matroids.catalog.Fano().chow_ring(QQ, False) sage: ch.defining_ideal() Chow ring ideal of Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) - non augmented
>>> from sage.all import * >>> ch = matroids.Uniform(Integer(3),Integer(6)).chow_ring(QQ, False) >>> ch.defining_ideal() Chow ring ideal of U(3, 6): Matroid of rank 3 on 6 elements with circuit-closures {3: {{0, 1, 2, 3, 4, 5}}} - non augmented >>> ch = matroids.catalog.Fano().chow_ring(QQ, False) >>> ch.defining_ideal() Chow ring ideal of Fano: Binary matroid of rank 3 on 7 elements, type (3, 0) - non augmented
- groebner_basis(algorithm='', *args, **kwargs)[source]¶
Return a Groebner basis of
self
.EXAMPLES:
sage: ch = Matroid(groundset='abc', bases=['ab', 'ac']).chow_ring(QQ, False) sage: ch.defining_ideal().groebner_basis() [Aa*Abc, Aa + Aabc, Abc + Aabc, Aa*Aabc, Abc*Aabc, Aabc^2] sage: ch.defining_ideal().groebner_basis().is_groebner() True sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
>>> from sage.all import * >>> ch = Matroid(groundset='abc', bases=['ab', 'ac']).chow_ring(QQ, False) >>> ch.defining_ideal().groebner_basis() [Aa*Abc, Aa + Aabc, Abc + Aabc, Aa*Aabc, Abc*Aabc, Aabc^2] >>> ch.defining_ideal().groebner_basis().is_groebner() True >>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
Another example would be the Groebner basis of the Chow ring ideal of the matroid of the length 3 cycle graph:
sage: ch = Matroid(graphs.CycleGraph(3)).chow_ring(QQ, False) sage: ch.defining_ideal().groebner_basis() [A0*A1, A0*A2, A1*A2, A0 + A3, A1 + A3, A2 + A3, A0*A3, A1*A3, A2*A3, A3^2] sage: ch.defining_ideal().groebner_basis().is_groebner() True sage: ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
>>> from sage.all import * >>> ch = Matroid(graphs.CycleGraph(Integer(3))).chow_ring(QQ, False) >>> ch.defining_ideal().groebner_basis() [A0*A1, A0*A2, A1*A2, A0 + A3, A1 + A3, A2 + A3, A0*A3, A1*A3, A2*A3, A3^2] >>> ch.defining_ideal().groebner_basis().is_groebner() True >>> ch.defining_ideal().hilbert_series() == ch.defining_ideal().gens().ideal().hilbert_series() True
- normal_basis(algorithm='', *args, **kwargs)[source]¶
Return the monomial basis of the quotient ring of this ideal.
EXAMPLES:
sage: ch = matroids.Z(3).chow_ring(QQ, False) sage: I = ch.defining_ideal() sage: I.normal_basis() [1, Ax2x3y1, Ax1x3y2, Ax1x2y3, Ay1y2y3, Atx1y1, Atx2y2, Atx3y3, Atx1x2x3y1y2y3, Atx1x2x3y1y2y3^2] sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True sage: ch = matroids.AG(2,3).chow_ring(QQ, False) sage: I = ch.defining_ideal() sage: I.normal_basis() [1, A012, A236, A046, A156, A345, A247, A057, A137, A258, A678, A038, A148, A012345678, A012345678^2] sage: set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True
>>> from sage.all import * >>> ch = matroids.Z(Integer(3)).chow_ring(QQ, False) >>> I = ch.defining_ideal() >>> I.normal_basis() [1, Ax2x3y1, Ax1x3y2, Ax1x2y3, Ay1y2y3, Atx1y1, Atx2y2, Atx3y3, Atx1x2x3y1y2y3, Atx1x2x3y1y2y3^2] >>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True >>> ch = matroids.AG(Integer(2),Integer(3)).chow_ring(QQ, False) >>> I = ch.defining_ideal() >>> I.normal_basis() [1, A012, A236, A046, A156, A345, A247, A057, A137, A258, A678, A038, A148, A012345678, A012345678^2] >>> set(I.gens().ideal().normal_basis()) == set(I.normal_basis()) True