Tutte polynomial
E1025362
The Tutte polynomial is a fundamental graph invariant in combinatorics that encodes extensive structural information about a graph, unifying and generalizing numerous other graph invariants such as the chromatic and flow polynomials.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Tutte polynomial canonical | 4 |
How this entity was disambiguated
This entity first appeared as the object of triple T13153058 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Tutte polynomial Context triple: [Bill Tutte, notableWork, Tutte polynomial]
-
A.
Pólya enumeration theorem
The Pólya enumeration theorem is a fundamental result in combinatorics that counts distinct configurations of objects under group actions by using cycle index polynomials and generating functions.
-
B.
Alon–Tarsi conjecture
The Alon–Tarsi conjecture is a prominent open problem in combinatorics and graph theory concerning orientations and colorings of graphs, with deep connections to Latin squares and polynomial method techniques.
-
C.
Symanzik polynomials
Symanzik polynomials are graph-based polynomials that arise in the parametric representation of Feynman integrals in quantum field theory, encoding the topology and kinematic dependence of Feynman diagrams.
-
D.
matrix-tree theorem
The matrix-tree theorem is a fundamental result in algebraic graph theory that expresses the number of spanning trees of a graph as a determinant of a matrix derived from the graph’s Laplacian.
-
E.
Combinatorial Nullstellensatz
Combinatorial Nullstellensatz is a powerful algebraic tool in combinatorics that uses polynomial methods over fields to derive results about combinatorial structures, such as existence and counting theorems.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Tutte polynomial Target entity description: The Tutte polynomial is a fundamental graph invariant in combinatorics that encodes extensive structural information about a graph, unifying and generalizing numerous other graph invariants such as the chromatic and flow polynomials.
-
A.
Pólya enumeration theorem
The Pólya enumeration theorem is a fundamental result in combinatorics that counts distinct configurations of objects under group actions by using cycle index polynomials and generating functions.
-
B.
Alon–Tarsi conjecture
The Alon–Tarsi conjecture is a prominent open problem in combinatorics and graph theory concerning orientations and colorings of graphs, with deep connections to Latin squares and polynomial method techniques.
-
C.
Symanzik polynomials
Symanzik polynomials are graph-based polynomials that arise in the parametric representation of Feynman integrals in quantum field theory, encoding the topology and kinematic dependence of Feynman diagrams.
-
D.
matrix-tree theorem
The matrix-tree theorem is a fundamental result in algebraic graph theory that expresses the number of spanning trees of a graph as a determinant of a matrix derived from the graph’s Laplacian.
-
E.
Combinatorial Nullstellensatz
Combinatorial Nullstellensatz is a powerful algebraic tool in combinatorics that uses polynomial methods over fields to derive results about combinatorial structures, such as existence and counting theorems.
- F. None of above. chosen
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
combinatorial invariant
ⓘ
graph invariant ⓘ polynomial invariant ⓘ |
| alsoKnownAs | dichromate ⓘ |
| appliesTo |
looped graphs
ⓘ
multigraphs ⓘ planar graphs ⓘ |
| captures |
deletion–contraction structure of a graph
ⓘ
rank and nullity of edge subsets ⓘ |
| codomain | bivariate polynomials over integers ⓘ |
| computationalComplexity | #P-hard to evaluate at most points ⓘ |
| dependsOn |
edge set
ⓘ
graph ⓘ vertex set ⓘ |
| domain |
graphs
ⓘ
matroids ⓘ |
| encodes |
connected subgraph information
ⓘ
cut structure information ⓘ cycle structure information ⓘ spanning tree information ⓘ |
| field |
combinatorics
ⓘ
graph theory ⓘ |
| generalizes |
Jones polynomial of alternating links
ⓘ
linked to:
Jones polynomial
chromatic polynomial ⓘ flow polynomial ⓘ reliability polynomial ⓘ |
| hasSpecialization |
Potts model partition function
ⓘ
linked to:
Potts model
all-terminal reliability polynomial ⓘ chromatic polynomial at (1-q,0) ⓘ flow polynomial at (0,1-q) ⓘ number of connected spanning subgraphs ⓘ number of forests ⓘ number of spanning trees ⓘ |
| hasSymmetry | duality relation for planar graphs ⓘ |
| hasVariable |
x
ⓘ
y ⓘ |
| isBivariate | true ⓘ |
| isDefinedFor |
finite graphs
ⓘ
matroids ⓘ |
| isExtensionOf | rank generating function of a matroid ⓘ |
| isInvariantUnder |
graph isomorphism
ⓘ
matroid isomorphism ⓘ |
| namedAfter | W. T. Tutte ⓘ |
| relatedTo |
Fortuin–Kasteleyn representation
ⓘ
linked to:
Fortuin–Kasteleyn random cluster model
Potts model in statistical mechanics ⓘ |
| satisfies |
deletion–contraction recurrence
ⓘ
duality T_G(x,y)=T_{G*}(y,x) for planar dual G* ⓘ |
| usedIn |
knot theory
ⓘ
network reliability ⓘ statistical physics ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Tutte polynomial Description of subject: The Tutte polynomial is a fundamental graph invariant in combinatorics that encodes extensive structural information about a graph, unifying and generalizing numerous other graph invariants such as the chromatic and flow polynomials.
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.