Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is exactly $s$ (hence the number of $-1$s is $n-s$.) Given a configuration $\sigma$, we look at each node $i$ and sum the values assigned to its neighbors, call this $\xi_i(\sigma)$. We then count the number of nodes for which $\xi_i(\sigma)$ is nonnegative:

$$ N(\sigma) := \sum_{i=1}^n 1\{ \xi_i(\sigma) \ge 0\}. $$

The question is: what is the configuration $\sigma$ that maximizes $N(\sigma)$? Can we give a bound on $(\max N)/n$ in terms of $s/n$. If it helps, the graph can be assumed to be Erdos-Renyi.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.