2
$\begingroup$

I am curious if this kind of construction (or something similar) exists:

Consider a convex polytope $P$ and then consider the graph of the polytope $G(P)$ (1-skeleton). Suppose a weighting structure is given to this graph now. So we have a pair $(G(P),w)$ with $w:E(G(P))\rightarrow \mathbb{R}$. We construct a weighting on the polytope $P$ as follows.

First consider a 2-face $F$ bounded by edges $e_1,\ldots,e_k$. We assign the weight $w(F)=\prod_{i=1}^k w(e_i)$.

Continuing in the obvious manner we have a $j+1$-face $F'$ bounded by $j$-faces $F_1,\ldots,F_m$ has weight $w(F')=\prod_{i=1}^m w(F_i)$.

This particular weighting structure is interesting because it seems like a natural generalization of signed-graphs (weighting on the edges is either $+1$ or $-1$) to polytopes.

Are there any interesting weighting structures out there for polytopes?

$\endgroup$

1 Answer 1

2
$\begingroup$

If you are restricting the weighting of the edges (it could just as equivalently be, in this case, weighting of vertices which would yield the same result) to be $\pm 1$, then you've got the weighting of a face being equivalent to the parity of the number of $-1$ weighted edges.

Every $1$ edge contributes no change to the weighting of a face, while every $-1$ edge flips the parity of the weight of the face, thus the weight of a face is $+1$ if there is parity $0$ (an even number of $-1$ weighted edges) and the weight of a face if $-1$ if there is parity $1$ (an odd number of $-1$ weighted edges) surrounding the face.

A similar simplification can be seen for the $j+1$-face: the weight of a $j+1$-face is the parity of the number of $-1$ weighted faces which surround it.

Of course, the obvious physical weightings of polytopes exist: where the weights represent

  • lengths as distances along a path, such as traveling salesman problems, wiring length in a communication network or the network topology of a connected grouping of computers (hypercubes such as the Connection Machine, for example)

  • time delays in network signal propagation (either as maximum time delays in order to calculate the maximal propagation delay times, or as average time delays) representing amount of time for a signal to pass through or the congestion of a network,

  • strength of connectivity or affinity, e.g. bond-strength in chemical structures as in "single-bond", "double-bond", or "triple-bond" for covalent bonds, or energy-of-bond representing the amount of energy required to break a chemical covalent bond (or other type of band, such as Van der Waals, weak hydrogen bonds, etc.)

  • strength of known linkage, as in similarity of sequence for molecular structures made of replicated subunits for DNA or RNA or proteins, or as in interactions between biochemical pathways (some of which form multiple interacting cycles, which can be represented as multidimensional graph structures).

If you look at your +1, -1 weighting of edges, you'll see that the same results would be obtained if the weighting were applied to the vertices, as each face is an $n$-gon polygon, and every (simple non-self-intersecting planar) polygon has the same number of edges and vertices. Is there any particular reason that you are applying the weighting as an attribute to the edges, rather than to the vertices? What kinds of systems are you looking at?

$\endgroup$
1
  • $\begingroup$ These are some interesting remarks, thanks! This is motivated by signed graphs. The most interesting parameter when studying signed graphs is the concept of "balance." We say a cycle in a signed graph is balanced if the product of its edges is +1. A signed graph is balanced if all of its cycles are balanced. This leads to many interesting things like a generalization of graphic matroids, hyperplane arrangements, root systems, etc. If you consider a weighting of +1/-1 on the vertices this actually provides a method of changing the edge signs without affecting balance, called "switching". $\endgroup$
    – hypercube
    Dec 10, 2010 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.