4
$\begingroup$

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 Erdős-Renyi.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I'm guessing if you're asking for Erdos-Renyi, you're probably fine with random graphs with probability $p$ of having an edge. You should tell us what sort of values of $p$ and $s$ you're thinking about in terms of $n$. $\endgroup$
    – Anthony Quas
    Commented May 13, 2012 at 5:47
  • 1
    $\begingroup$ @Anthony: Thanks. Yes, I am primarily interested in an Erdos-Renyi (ER) graph. I stated the problem more generally, in case it is related to a known problem. You can assume an ER graph with p = a/n, where maybe a = O(log n). Also, you can assume s/n < 1/2 and maybe $ s/n \to \gamma (0,1/2)$ as $n \to \infty$. It would be interesting to show that (max N)/n is strictly less than $\gamma$ as $n \to \infty$ with high probability. $\endgroup$
    – passerby51
    Commented May 13, 2012 at 6:04
  • 1
    $\begingroup$ My comment was that (as I understand it) ER didn't consider random graphs where each edge shows up with probability $p$; but rather where you are told the exact number of edges to put down uniformly at random. It is not so surprising that the behaviour of these two models (putting down $pn(n-1)/2$ edges at random and putting in each edge with probability $p$) has very similar behaviour. $\endgroup$
    – Anthony Quas
    Commented May 13, 2012 at 15:05
  • $\begingroup$ You are right, they originally considered the model you mentioned. However, it seems easier for me to consider G(n,p) where you pick each potential edge out of 2-subsets of [n] with probability p. $\endgroup$
    – passerby51
    Commented May 14, 2012 at 14:07

1 Answer 1

Reset to default
1
$\begingroup$

OK. Let me make a wild guess. I'll assume that you're looking at a random graph with $p=(\log n)/n$ and $s=n/4$ for concreteness.

Since for $p$ in that range, there are very few small cycles, the graph is behaving quite a lot like a tree with branching number $\log n$ at each vertex.

An easy lower bound for the number of vertices that you can "infect" is $2\gamma n/\log n$: pick out a set $S$ with this number of vertices arbitrarily; and then infect half of their neighbours. In fact you can clearly do better since some vertices are neighbours with several elements of $S$ - this means you can do extra infection for free.

My guess: $\max N\sim Cn/\log n$ (possibly up to something like $\log\log n$ factors).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks. You estimate seems about right to me, The difficulty however is in proving an upper bound on $\max N$. I have a few ideas, none which developed much due to my lack of knowledge about random graphs. Using your terminology, let us call the nodes that have at least half their neighbors carrying +1, the "infected" nodes. These are the ones that contribute to $N$. One approach is to consider a maximal configuration and look at the set $S$ of infected nodes. The one forms balls of some radius R(n) (say ~ log n) around them and try to show that they do not intersect much ... $\endgroup$
    – passerby51
    Commented May 14, 2012 at 14:14
  • $\begingroup$ ... otherwise maximality is violated. Then, one perhaps gets the estimate R(n) |S| \le n(1+o(1)). Another approach is to try to bound the expectation of N(\sigma) using a covering/chaining type argument. Say, one looks at the distance between two neighboring configurations $\sigma$ and $\sigma'$, defined by $d(\sigma,\sigma') := E |N(\sigma) - N(\sigma')|$ and then tries to cover the space of configurations in balls of some radius in this distance. $\endgroup$
    – passerby51
    Commented May 14, 2012 at 14:21
  • 1
    $\begingroup$ The balls you're suggesting are way too big. The ball of radius 1 has $\log n$ elements. The ball of radius 2 has about $(\log n)^2$. This means the neighbourhoods of any set of size $n/\log n$ will almost certainly cover most of the graph $\log n$ times over. $\endgroup$
    – Anthony Quas
    Commented May 14, 2012 at 14:57
  • $\begingroup$ Sorry, that was a typo, it was thinking of the number of elements in the ball to be ~ log n, not the radius. $\endgroup$
    – passerby51
    Commented May 14, 2012 at 15:04
  • $\begingroup$ ... I mean the R(n) in my original comment is the number of elements in each ball. It seems that one should take the radius to be 1. I am not even sure if taking a ball is a good idea. One might try other neighborhoods (of different shapes) of some size R(n), as your comment suggests that there might not much flexibility working with balls. $\endgroup$
    – passerby51
    Commented May 14, 2012 at 15:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .