5
$\begingroup$

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every independent set of vertices, say $I$, satisfies $\sum_{v_i\in I}w_{i}\leq 1/2$. I would like to maximize over all choices of the weights the following expression (the average of f):$\\$ $$\sum_{i=1}^{n}f(v_i)w_{i}.\\$$

Question: is it true, that at least one global maximum is achieved by either i) putting weights $1/2$ on a pair of two neighboring vertices or ii) putting a weight $1/2$ on one vertex and $0$ on all of the others?

Remark: the second situation can arise, for example, in the case $G$ is the empty graph and the value of $f$ at one vertex is strictly larger than on the other vertices.

Improve this question
$\endgroup$
5
  • $\begingroup$ By "empty graph" do you mean graph with no edges but having vertices? Other constructions for global maximum are possible I believe. $\endgroup$
    – joro
    Commented Oct 13, 2013 at 11:20
  • $\begingroup$ Yes, by an empty graph I mean that there are no edges. And yes, there can be many global maximums, just take $f=1$ for all $v$. That is not the point. The point is to find the simple possible among all - and I believe that the global maximum is always attained by one of the construction I described. $\endgroup$
    – TOM
    Commented Oct 13, 2013 at 11:23
  • $\begingroup$ Let $W$ be the convex polytope set of all admissible distribution of weights (that is, $w=(w_1,\dots,w_n)$ satisfying the constraints). Your question may be reformulated as: the extremal points of $W$ are exactly those of type (i) or (ii), and the zero distribution. Equivalently, $w\in W$ should be extremal iff for all $i$ there holds $w_i\in\{ 0, 1/2\}$ (the "if" part being clearly true). $\endgroup$
    – Pietro Majer
    Commented Oct 13, 2013 at 19:44
  • $\begingroup$ The other implication, the one you want, consists in the problem: Given $w\in W$ with say $0 < w_1 < 1/2$, find $u\in\mathbb{R}^n$ such that $w\pm u\in W$. This may be difficult, due to the complicated combinatorics of the family of the independent sets. $\endgroup$
    – Pietro Majer
    Commented Oct 13, 2013 at 19:56
  • 4
    $\begingroup$ The life is not that simple. Take the full graph with $n$ vertices and put $f=1, w=\frac 1{2n}$ on it. Now add one isolated vertex and put $f=2, w=\frac 12-\frac 1{2n}$ on that vertex. When $n$ is large, you get about $\frac 32$ though your simple configurations cannot yield more than $1$ here. $\endgroup$
    – fedja
    Commented Oct 14, 2013 at 0:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .