The Tutte polynomial modulo a prime Goodall, A.J.
Advances in applied mathematics,
2004, 2004-01-00, 20040101, Letnik:
32, Številka:
1
Journal Article
Recenzirano
Odprti dostop
For
F
p
the field on prime number
p>3 elements, it has been conjectured that there are just
p+3 evaluations of the Tutte polynomial in
F
p
which are computable in polynomial time. In this note it is ...shown that if
p
≡
̷
−1
mod
12
then there are further polynomial-time computable evaluations.
The number of homomorphisms from a finite graph \(F\) to the complete graph \(K_n\) is the evaluation of the chromatic polynomial of \(F\) at \(n\). Suitably scaled, this is the Tutte polynomial ...evaluation \(T(F;1-n,0)\) and an invariant of the cycle matroid of \(F\). De la Harpe and Jaeger \cite{dlHJ95} asked more generally when is it the case that a graph parameter obtained from counting homomorphisms from \(F\) to a fixed graph \(G\) depends only on the cycle matroid of \(F\). They showed that this is true when \(G\) has a generously transitive automorphism group (examples include Cayley graphs on an abelian group, and Kneser graphs). Using tools from multilinear algebra, we prove the converse statement, thus characterizing finite graphs \(G\) for which counting homomorphisms to \(G\) yields a matroid invariant. We also extend this result to finite weighted graphs \(G\) (where to count homomorphisms from \(F\) to \(G\) includes such problems as counting nowhere-zero flows of \(F\) and evaluating the partition function of an interaction model on \(F\)).
This paper is based on a series of talks given at the Patejdlovka Enumeration Workshop held in the Czech Republic in November 2007. The topics covered are as follows. The graph polynomial, ...Tutte-Grothendieck invariants, an overview of relevant elementary finite Fourier analysis, the Tutte polynomial of a graph as a Hamming weight enumerator of its set of tensions (or flows), and a description of a family of polynomials containing the graph polynomial which yield Tutte-Grothendieck invariants in a similar way.
Mackintosh is important not as an innovator or an original thinker but as an exemplar of his times. He was a man who straddled both the ideas of the eighteenth century Enlightenment and those of the ...mid-nineteenth century epitomised by the Rights of Man and utilitarianism. Close study of Mackintosh's developing ideas, political, historical and philosophical yields I better understanding of the position held by the Philosophical Whigs of his day. Mackintosh is also explored in relation to the concept of romantic history which started to surface in England during the 1820s. Mackintosh, who was accepted in his time as a philosopher of history, was a pioneer in detecting and expounding new movements of thought and his writings contain an early prescription for most of the elements of romantic historiography.
Mackintosh is important not as an innovator or an original thinker but as an exemplar of his times. He was a man who straddled both the ideas of the eighteenth century Enlightenment and those of the ...mid-nineteenth century epitomised by the Rights of Man and utilitarianism. Close study of Mackintosh's developing ideas, political, historical and philosophical yields I better understanding of the position held by the Philosophical Whigs of his day. Mackintosh is also explored in relation to the concept of romantic history which started to surface in England during the 1820s. Mackintosh, who was accepted in his time as a philosopher of history, was a pioneer in detecting and expounding new movements of thought and his writings contain an early prescription for most of the elements of romantic historiography.
Isoprenoid Modifications Nguyen, Uyen T. T.; Goodall, Andrew; Alexandrov, Kirill ...
Post-Translational Modifications in Health and Disease,
09/2010
Book Chapter
Up to 2% of mammalian proteome is post-translationally modified with isoprenoid lipids. Many of these molecules are key regulators of signaling pathways involved in cellular homeostasis. Appropriate ...signaling by prenylated proteins requires a combination of correct expression levels, efficient post-translational modification, correct subcellular trafficking and nanolocalisation as well as an appropriately regulated activation/deactivation cycle. Aberrant signaling by prenylated proteins can result from the dysregulation of any of these steps, often contributing to human disease. Owing to the prevalence of dysregulated signaling by prenylated proteins in human disease, considerable research has been undertaken into developing pharmacological inhibitors of protein prenylation. A variety of small molecule farnesyltransferase and geranylgeranyltransferase inhibitors have been developed that have been demonstrated to impair tumor growth in vivo. Additionally the cholesterol lowering drugs known as statins have also been demonstrated to inhibit protein prenylation by preventing the formation of prenylation precursors. This review attempts to summarize the current understanding of protein prenylation and the interplay of processes required for signaling by prenylated proteins. The review also highlights the importance of developing new techniques to assess the effects of current and future therapeutic compounds on global prenylation, so as to accurately explain and predict their effects.
We give a method of generating strongly polynomial sequences of graphs, i.e., sequences \((H_{\mathbf{k}})\) indexed by a multivariate parameter \(\mathbf{k}=(k_1,\ldots, k_h)\) such that, for each ...fixed graph \(G\), there is a multivariate polynomial \(p(G;x_1,\ldots, x_h)\) such that the number of homomorphisms from \(G\) to \(H_{\mathbf{k}}\) is given by the evaluation \(p(G;k_1,\ldots, k_h)\). A classical example is the sequence \((K_k)\) of complete graphs, for which \({\rm hom}(G,K_k)=P(G;k)\) is the evaluation of the chromatic polynomial at \(k\). Our construction produces a large family of graph polynomials that includes the Tutte polynomial, the Averbouch-Godlin-Makowsky polynomial and the Tittmann-Averbouch-Makowsky polynomial. We also introduce a new graph parameter, the {\em branching core size} of a simple graph, related to how many involutive automorphisms with fixed points it has. We prove that a countable family of graphs of bounded branching core size (which in particular implies bounded tree-depth) is always contained in a finite union of strongly polynomial sequences.
On the Parity of Colourings and Flows Goodall, Andrew J.; Welsh, Dominic J.A.
Journal of combinatorial theory. Series B,
03/2002, Letnik:
84, Številka:
2
Journal Article
Recenzirano
Odprti dostop
We extend a result of Tarsi and show that the chromatic polynomial and flow polynomial evaluated at 1+k are up to sign the same modulo k2 for any integer k such that |k|⩾2.
PDF
