{
  "id": "0812.3082",
  "version": "v1",
  "published": "2008-12-16T15:18:49.000Z",
  "updated": "2008-12-16T15:18:49.000Z",
  "title": "Algebraic invariants of graphs; a study based on computer exploration",
  "authors": [
    "Nicolas M. Thiéry"
  ],
  "journal": "SIGSAM Bulletin (ACM Special Interest Group on Symbolic and Algebraic Manipulation), 34(3): 9-20, September 2000",
  "categories": [
    "math.CO",
    "math.AC"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2008-12-16T15:18:49.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C60",
      "13A50"
    ],
    "keywords": [
      "algebraic invariants",
      "simple minimal generating set",
      "low degree system",
      "general invariant rings",
      "ulams reconstruction conjecture"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0812.3082T"
    }
  }
}