A graph with few edges everywhere - MathOverflow

A graph with few edges everywhere

2010-12-18T13:27:34Z

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}$.

Answer by gowers for A graph with few edges everywhere

2010-12-18T18:41:46Z

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.

Answer by Fedor Petrov for A graph with few edges everywhere

2010-12-18T19:27:29Z

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$.

Answer by fedja for A graph with few edges everywhere

2010-12-18T20:30:46Z

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.

Answer by Sergey Norin for A graph with few edges everywhere

2010-12-18T22:44:34Z

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.