A greedoid polynomial which distinguishes rooted arborescences

1989/10/01 by Gary Gordon, Elizabeth McMahon · 2 citations
Mathematics · Engineering · #Advanced Combinatorial Mathematics #Optical Network Technologies #Algebraic structures and combinatorial models #Algorithm #Artificial intelligence #Computer science

paper · pdf · doi:10.1090/s0002-9939-1989-0967486-0

openalex publication_date 1989/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11

Abstract

We define a two-variable polynomial <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f Subscript upper G Baseline left-parenthesis t comma z right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f_G(t,z)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for a greedoid <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which generalizes the standard one-variable greedoid polynomial <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="lamda Subscript upper G Baseline left-parenthesis t right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi> λ </mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">λ _G(t)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . Several greedoid invariants (including the number of feasible sets, bases, and spanning sets) are easily shown to be evaluations of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f Subscript upper G Baseline left-parenthesis t comma z right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f_G(t,z)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . We prove (Theorem 2.8) that when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a rooted directed arborescence, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f Subscript upper G Baseline left-parenthesis t comma z right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f_G(t,z)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> completely determines the arborescence. We also show the polynomial is irreducible over <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="bold upper Z left-bracket t comma z right-bracket"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">Z</mml:mi> </mml:mrow> </mml:mrow> <mml:mo stretchy="false">[</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">]</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathbf Z[t,z]</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for arborescences with only one edge directed out of the distinguished vertex. When <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a matroid, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f Subscript upper G Baseline left-parenthesis t comma z right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f_G(t,z)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> coincides with the Tutte polynomial. We also give an example to show Theorem 2.8 fails for full greedoids. This example also shows <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="f Subscript upper G Baseline left-parenthesis t comma z right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>f</mml:mi> <mml:mi>G</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>t</mml:mi> <mml:mo>,</mml:mo> <mml:mi>z</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">f_G(t,z)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> does not distinguish

Cited by

• A characteristic polynomial for rooted graphs and rooted digraphs
• Rooted graph [wikipedia]