I am working on a modeling project whose mathematical formalism uses 2D integer periodic lattices. The problem I'm actually interested in can be generalized to the following graph theory problem, which might perhaps be easier by virtue of there being less structure available. Given a fixed undirected graph $G=(V,E)$ and an arbitrary function $F : V \to \{ 1,2,\dots,|V| \}$ (not necessarily injective or surjective), we define
$$B(F,v)=\# \{ u \in V : (u,v) \in E \text{ and } F(u) \geq F(v) \}$$ where $\#A$ is the number of elements in a finite set $A$. The occurrences being counted here are called bonds experienced at the site $v$.
We then define:
$$D(F)=\sum_{v \in V} \# \{ u \in V : (u,v) \in E \text{ and } F(u)>F(v) \text{ and } B(F,u)>B(F,v) \}.$$
Each of the occurrences being counted in this sum is called a discrepancy between $u$ and $v$ in favor of $u$.
I want to understand the optimization problem of choosing $F$ to make $D(F)$ as large as possible.
Some initial intuition follows:
- Discrepancies are possible. An example of a labeled graph with a discrepancy is $V=\{ 1,2,3,4 \},E=\{ (1,2),(2,3),(2,4) \}$ (the "T" graph) labeled with $F(1)=2,F(2)=2,F(3)=2,F(4)=1$. Then there will be a discrepancy between $2$ and $4$ in favor of $2$.
- However, discrepancies are "unusual" because if $F(u)>F(v)$ then a bond is experienced to $u$ at $v$ but not vice versa. So vertices with higher values of $F$ will tend to have fewer bonds, especially if the degree of all vertices is constant (as in the cases of interest to me).
My limited thoughts on the problem:
- The obvious bound on $D(F)$ is $\sum_{v \in V} \operatorname{deg}(v)-B(F,v)$, which is what you get if you just forget about the $B(F,u)>B(F,v)$ part. But my experiments show that at least in the class of graphs I am interested in (2D rectangular periodic lattices) $D(F)$ is much smaller. For instance this bound might be about $200$ while the actual value of $D$ is about $5$.
Some alternative ways to formulate the problem:
- We can forget about $F$ and think purely in terms of an arbitrary total preorder on $V$. Unfortunately we cannot specialize to actual orders, because $F$ was allowed to be non-injective.
- We can pose everything in graph theory language. To do this, we take $G$ and then half-remove edges from it to make a directed graph. In this framework, a discrepancy occurs when there is a directed edge from $v$ to $u$ and the out-degree of $u$ (counting both directed edges and undirected edges) is higher than that of $v$. The problem with this formulation is that we cannot simply half-remove edges willy-nilly: we have to remove them in such a way that there are no cycles containing directed edges. Yet we still have more leeway than in the case of constructing an acyclic orientation of an undirected graph, because purely undirected cycles are OK (and in particular, the original graph is OK, though it has zero discrepancies).