Transforms and Minors for Binary Functions

详细信息    查看全文

• 作者：G. E. Farr (1)
  
• 关键词：05B99 ; 05C99 ; 05B35 ; 82B20 ; 94B99 ; binary functions ; matroids ; minors ; combinatorial transforms ; rank transform ; generalised Hadamard transform ; duality ; trinity ; weight enumerator ; MacWilliams identity ; Plancherel’s Theorem ; Parseval’s Theorem ; Ising model
• 刊名：Annals of Combinatorics
• 出版年：2013
• 出版时间：September 2013
• 年：2013
• 卷：17
• 期：3
• 页码：477-493
• 全文大小：327KB
• 参考文献：1. Ashkin J., Teller E.: Statistics of two-dimensional lattices with four components. Phys. Rev. 64(5-6), 178-84 (1943) CrossRef
  2. Farr G.E.: A generalization of the Whitney rank generating function. Math. Proc. Cambridge Philos. Soc. 113(2), 267-80 (1993) CrossRef
  3. Farr G.E.: Some results on generalised Whitney functions. Adv. Appl. Math. 32(1-2), 239-62 (2004) CrossRef
  4. Farr, G.E.: Tutte-Whitney polynomials: some history and generalizations. In: Grimmett, G., McDiarmid, C. (eds.) Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, pp. 28-2. Oxford University Press, Oxford (2007)
  5. Farr G.E.: On the Ashkin-Teller model and Tutte-Whitney functions. Combin. Probab. Comput. 16(2), 251-60 (2007) CrossRef
  6. Goodall, A.: Fourier analysis on finite Abelian groups: some graphical applications. In: Grimmett, G., McDiarmid, C. (eds.) Combinatorics, Complexity, and Chance: A Tribute to Dominic Welsh, pp. 103-29. Oxford University Press, Oxford (2007)
  7. Hirvensalo, M.: Quantum Computing, 2nd Edit. Springer-Verlag, Berlin (2004)
  8. Horadam, K.J.: A generalised Hadamard transform. In: IEEE International Symposium on Information Theory, 2005, (ISIT 2005), pp. 1006-008. IEEE, New York (2005)
  9. Ising E.: Beitrag zur Theorie des Ferromagnetismus. Z. Phys. 31(1), 253-58 (1925) CrossRef
  10. Kung J.P.S.: The Rédei function of a relation. J. Combin. Theory Ser. A 29(3), 287-96 (1980) CrossRef
  11. Kuratowski C.: Sur le problème des courbes gauches en topologie. Fund. Math. 15, 271-83 (1930)
  12. MacWilliams F.J.: A theorem on the distribution of weights in a systematic code. Bell System Tech. J. 42, 79-4 (1963) CrossRef
  13. Oxley J.G.: Matroid Theory. Oxford University Press, New York (1992)
  14. Robertson N., Seymour P.D.: Graph minors. XX. Wagner’s conjecture. J. Combin. Theory Ser. B 92(2), 325-57 (2004) CrossRef
  15. Wagner K.: über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114(1), 570-90 (1937) CrossRef
  16. Welsh D.J.A.: Matroid Theory. Academic Press, London-New York (1976)
  17. Welsh D.J.A.: Complexity: Knots, Colourings and Counting. Cambridge University Press, Cambridge (1993) CrossRef
  
• 作者单位：G. E. Farr (1)
  
  1. Clayton School of Information Technology, Monash University, Clayton, Victoria, 3800, Australia
  

文摘

We introduce a family of transforms that extends graph- and matroid-theoretic duality, and includes trinities and so on. Associated with each such transform are λ -minor operations, which extend deletion and contraction in graphs. We establish how the transforms interact with our generalised minors, extending the classical matroid-theoretic relationship between duality and minors: ${(M/e)^* =M^* \backslash e}$ . Composition of the transforms is shown to correspond to complex multiplication of appropriate parameters. A new generalisation of the MacWilliams identity is given, using these transforms in place of ordinary duality. We also relate the weight enumerator of a binary linear code at a real argument <?- to the transform, with parameter on the unit circle, of a close relative of the indicator function of the dual code. This result extends to arbitrary binary codes. The results on weight enumerators can also be recast in terms of the partition function of the Ising model from statistical mechanics. Most of our work is done at the level of binary functions ${f : 2^E \rightarrow \mathbb{C}}$ , which include matroids as a special case. The specialisation to graphs is obtained by letting f be the indicator function of the cutset space of a graph.