Problem of the Week
Hilton Memorial Lecture
A gain graph is a graph whose edges are invertibly labelled by elements of a group. Some work in geometry and graph theory due to Forge-Zaslavsky and Noble-Welsh led us (Forge and Zaslavsky) to think there would be some point in a cute and fancy weighted version. The gain group is lattice ordered; this means it is a lattice, with meets and joins, that respect the group operation. There is also an abelian semigroup which is acted upon by the gain group, and the vertices are weighted by this semigroup.
A simple example is where the group is (Z,+) and the semigroup is (Z,max) (due to us). In Noble and Welsh's example, the group is trivial and the semigroup is (P,·), where P is the set of positive integers. These groups are totally ordered so the lattice operations are simple, i.e., join = max and meet = min.
The most interesting example is where the group is (Zd,+) with the standard componentwise max and min lattice operations, and the semigroup is (Zd,join). This leads to a formula for the number of integer lattice points in an orthotope but not in certain hyperplanes in Rd.