MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given a graph $G(V,E)$ whose edges are colored in two colors: red and blue. Suppose the following two conditions hold:

  • for any $S\subseteq V$, there are at most $O(|S|)$ red edges in $G[S]$
  • for any $S\subseteq V$, if $G[S]$ contains no red edges, then it contains $O(|S|)$ blue edges

My question is: can we conclude from this that the total number of blue edges is linear? I have no strong intuition for this, but it seems that it might be possible (some averaging/probabilistic argument?). To try to give an intuition, we can rephrase it as follows. The red graph is very sparse, even locally. The blue graph is also sparse in all regions that are free of red edges. Due to the sparseness of the red graph those 'regions' are numerous, so we hope this might imply that the blue graph is also sparse.

One can maybe consider first an easier version, if we assume that the red degree of every vertex is $O(1)$. In this case I also don't know the answer.

Note that it's already too weak if we replace the first condition with just: the total number of red edges is linear. Look at the example: a blue $K_{\sqrt n,n-\sqrt n}$ with a red $\sqrt n$-clique added in the corresponding part. This graph has $\Omega(n^{3/2})$ blue edges (example by D. Palvolgyi). We can still ask in this version whether one can do better than $n^{3/2}$.

share|cite|improve this question
up vote 12 down vote accepted

I think one can push through the probabilistic arguments of Tim Gowers and Fedor Petrov in the general case, as follows.

Let $c$ be a constant such that the number of red edges in $G[S]$ is at most $c|S|$ for every $S \subseteq V(G)$. One can order the vertices of $G$: $v_1, v_2, \ldots, v_n$, so that every vertex has at most $2c$ neighbors with lower indices. (Define the ordering starting with the highest index. If $v_n, \ldots,v_{i+1}$ are defined, set $v_i$ to be the vertex with the smallest degree in the subgraph induced by the vertices which are not yet indexed. This is a standard trick.)

Now we define a random subset $S$ of $V(G)$ recursively: if $S \cap$ {$v_1, \ldots, v_i$} is chosen put $v_{i+1}$ in $S$ with probability $1/2$ if it is not joined by a red edge to any of the vertices already in $S$, otherwise don't put it in $S$. Then $S$ is red-free and, just as in Fedor's answer, we can see that the probability that a pair of vertices $u$ and $v$ joined by a blue edge both lie in $S$ is at least $2^{-4c-2}$. Therefore the number of blue edges is at most

$2^{4c+2}c' \mathbf{E}[|S|] \leq 2^{4c+1}c'|V(G)|,$

where $c'$ is the constant implicitly present in the condition on the density of the blue edges.

share|cite|improve this answer
I think you mean that the probability that both ends of a blue edge are chosen is at least $2^{-4c-2}$, and a complete write-up should also account for the additive constants allowed by big-O notation, but I'm convinced this will work. – Tracy Hall Dec 18 '10 at 23:13
@Tracy: Thank you, corrected $2c$ to $4c$. Additive constants in big-O could be absorbed into multiplicative ones. – Sergey Norin Dec 18 '10 at 23:15
very nice proof! thank you all for combined efforts. – filipm Dec 19 '10 at 9:58

Suppose that the red edges can be written as a union of k matchings, $M_1,\dots,M_k$. Now choose a random set of vertices as follows. For each edge in $M_1$ choose one of its end points randomly. Put in all other vertices with probability 1/2. Then do the same for $M_2,\dots,M_k$. This gives us sets $A_1,\dots,A_k$. Let $A$ be the intersection of these sets. Then each vertex has a probability $2^{-k}$ of belonging to $A$. Also, $A$ contains no red edges. More importantly, given a non-red edge, there is a probability $4^{-k}$ that both its end points belong to $A$. If we choose a random pair in $A$, the probability that it is a blue edge is at most $C/n$ for some $C$. I think (I haven't checked carefully enough to be sure) that this does the bounded-degree case, showing that we have at most $4^kCn$ blue edges. Maybe it even does the general case.

share|cite|improve this answer
This certainly does bounded-degree case, since edges of a graph with maximal degree $d$ lie in a union of $d+1$ matchings (it is called Vizing's theorem, $2d-1$ matchings instead $d+1$ is almost obvious). General case may be done, if we replace matchings to trees and then change the probabilistic argument as Sergey suggests: enumerate vertices of each tree by ranges (starting from the root) and take each vertex with probability 1/2 if its (unique) already considered neighbor is not still taken. – Fedor Petrov Dec 19 '10 at 20:52

It is not an answer, but bounded degree case only. If all red degrees do not exceed $d$. choose random (w.r.t. uniform distribution) red independent set $I$. I claim that for each edge $uv$ both $u$, $v$ belong to $I$ with probability bounded from below. Indeed, denote by $N$ the union of $u$, $v$ and their red neighbors. Then if we fix an intersection of $I$ and $V\setminus N$, then conditional probability that $u,v$ both lie in $I$ is at least $1/2^{n}$, where $n=|N|\leq 2d+2$.

share|cite|improve this answer

Here are just a couple of ideas (too long to fit a comment window). Let $R_i$ and $B_i$ be the red and the blue degrees of the $i$-th vertex. Take your graph and remove all vertices with $B_i\le MR_i+M$. Take the remaining subgraph and remove all vertices with $B_i\le MR_i+M$ (using the counts in the remaining subgraph, of course), and so on. No matter how many times we go, we remove at most $O(Mn)$ blue edges. If we stop, we have a graph in which each blue degree is at least $M$ times the corresponding red degree plus $M$.

Now arrange the vertices in random order and select the red-independent set as the set of all vertices that preceede all their neighbors in the ordering. Each vertex $i$ will survive with probability $(R_i+1)^{-1}$. Moreover, if $(i,j)$ is not a red edge, then the probability that both $i,j$ survive is at least $\frac12(R_i+1)^{-1}(R_j+1)^{-1}$. This puts the expected number of surviving blue edges at $$\frac 12\sum_{(i,j)\in E_{\text{blue}}}(R_i+1)^{-1}(R_j+1)^{-1}$$ and the expectation of the surviving number of vertices at $\sum_{i}(R_i+1)^{-1}$.

If all degrees are bounded by $K$, then we, clearly, have what we want with much better bound than $4^K$. Unfortunately, if the degrees are unbounded, we still have a problem.

share|cite|improve this answer
hmm, why probability that a vertex survives is $(R_j+1)^{-1}$? Is not it $(R_j!)^{-1}$? – Fedor Petrov Dec 19 '10 at 14:40
It just needs to be the first in the ordering, not to dictate the whole ordering. Anyway, this post is obsolete after Sergei's construction (only, of course, the vertex has to be chosen not with probability $1/2$ but with probability $1/c$ or so, so his survial chance for the pair is $(1-1/c)^{4c}c^{-2}\approx c^{-2}$). – fedja Dec 19 '10 at 23:09
oh, indeed (stupid me). I think, polynomial estimate is in general better then exponential, and it may be important in some other applications (say, if red degrees slowly grow). – Fedor Petrov Dec 19 '10 at 23:21

Your Answer


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

Not the answer you're looking for? Browse other questions tagged or ask your own question.