Weighted Polytope - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T22:15:51Z http://mathoverflow.net/feeds/question/48882 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48882/weighted-polytope Weighted Polytope hypercube 2010-12-10T05:42:28Z 2010-12-10T12:58:00Z <p>I am curious if this kind of construction (or something similar) exists:</p> <p>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.</p> <p>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)$.</p> <p>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)$. </p> <p>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.</p> <p>Are there any interesting weighting structures out there for polytopes?</p> http://mathoverflow.net/questions/48882/weighted-polytope/48915#48915 Answer by sleepless in beantown for Weighted Polytope sleepless in beantown 2010-12-10T12:58:00Z 2010-12-10T12:58:00Z <p>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.</p> <p>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.</p> <p>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.</p> <p>Of course, the obvious physical weightings of polytopes exist: where the weights represent </p> <ul> <li><p>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)</p></li> <li><p>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,</p></li> <li><p>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.)</p></li> <li><p>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).</p></li> </ul> <p>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?</p>