ZIB

Hits per page

hits 1 - 2 | 2 hits

Sorting

Electronic Resource

The Potts model and the Tutte polynomial (2000)

Welsh, D. J. A. ; Merino, C.

College Park, Md. : American Institute of Physics (AIP)

Journal of Mathematical Physics 41 (2000), S. 1127-1152

add to mindlist on the mindlist

Details

ISSN: 1089-7658

Source: AIP Digital Archive

Topics: Mathematics , Physics

Notes: This is an invited survey on the relation between the partition function of the Potts model and the Tutte polynomial. On the assumption that the Potts model is more familiar we have concentrated on the latter and its interpretations. In particular we highlight the connections with Abelian sandpiles, counting problems on random graphs, error correcting codes, and the Ehrhart polynomial of a zonotope. Where possible we use the mean field and square lattice as illustrations. We also discuss in some detail the complexity issues involved. © 2000 American Institute of Physics.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1063/1.533181

Permalink

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

Electronic Resource

A greedy algorithm for solving a certain class of linear programmes (1973)

Dunstan, F. D. J. ; Welsh, D. J. A.

Springer

Mathematical programming 5 (1973), S. 338-353

add to mindlist on the mindlist

Details

ISSN: 1436-4646

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract If is a collection of subsets ofS andw is a nonnegative weight function onS, the problem of selecting a subset belonging to which has maximum weight is solved by a ‘greedy-type’ algorithm forall w if and only if is the set of independent sets of a matroid. This result is then generalised to show that ‘greedy-type’ algorithms select an optimum forall linear functionsc·x; x in some compact set $$U \subseteq R^n $$ andc 〉 0 if and only if the convex closure ofU is essentially a polymatroid. A byproduct of this is a new characterization of polymatroids.