Algebraic invariants of graphs; a study based on computer exploration

DOI10.1145/377604.377612zbMATH Open1052.05050arXiv0812.3082OpenAlexW1974704708MaRDI QIDQ4810172FDOQ4810172

Authors: Nicolas Thiéry 

Publication date: 1 September 2004

Published in: ACM SIGSAM Bulletin (Search for Journal in Brave)

Abstract: We consider the ring I_n of polynomial invariants over weighted graphs on n vertices. Our primary interest is the use of this ring to define and explore algebraic versions of isomorphism problems of graphs, such as Ulam's reconstruction conjecture. There is a huge body of literature on invariant theory which provides both general results and algorithms. However, there is a combinatorial explosion in the computations involved and, to our knowledge, the ring I_n has only been completely described for n<=4. This led us to study the ring I_n in its own right. We used intensive computer exploration for small n, and developed PerMuVAR, a library for MuPAD, for computing in invariant rings of permutation groups. We present general properties of the ring I_n, as well as results obtained by computer exploration for small n, including the construction of a medium sized generating set for I_5. We address several conjectures suggested by those results (low degree system of parameters, unimodality), for I_n as well as for more general invariant rings. We also show that some particular sets are not generating, disproving a conjecture of Pouzet related to reconstruction, as well as a lemma of Grigoriev on the invariant ring over digraphs. We finally provide a very simple minimal generating set of the field of invariants.

Full work available at URL: https://arxiv.org/abs/0812.3082

Recommendations

• Graph characterising polynomials
• A Database of Invariant Rings
• scientific article; zbMATH DE number 3875344
• Variable neighborhood search for extremal graphs. 20. Automated comparison of graph invariants
• Generation modulo the action of a permutation group

zbMATH Keywords

ringinvariant ringUlam's reconstruction conjectureconjecture of Pouzetisomorphism problems of graphslemma of Grigoriev

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cited In (13)

• Separating invariants
• Problems from CGCS Luminy, May 2007
• Immanantal invariants of graphs
• Hopf algebras of graphs.
• On reconstructing \(n\)-point configurations from the distribution of distances or areas
• Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers
• A computational approach to construct a multivariate complete graph invariant
• Graph characterising polynomials
• A new formula for the generating function of the numbers of simple graphs
• Applications of multisymmetric syzygies in invariant theory
• Some relational structures with polynomial growth and their associated algebras. II: Finite generation.
• Separating invariants over finite fields
• Degree bounds for fields of rational invariants of \(\mathbb{Z}/p\mathbb{Z}\) and other finite groups

Uses Software

• CoCoA
• FGb
• MuPAD
• PerMuVAR

This page was built for publication: Algebraic invariants of graphs; a study based on computer exploration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4810172)