1
$\begingroup$

Given a graph on $n$ vertices, I wish to find a lower bound on the number of edges required before the graph can has the following property: Every subset of 4 vertices contains a matching.

Put more formally, for every $v_1,v_2,v_3,v_4\in V$ we have that either $(v_1,v_2), (v_3,v_4)\in E$ or $(v_1,v_3),(v_2,v_4)\in E$ or $(v_1,v_4),(v_2,v_3)\in E$ (more edges are ok as well).

My intuition says the lower bound will be $\Omega(n^2)$; if it is lower it will be very interesting for me.

  • 1
    If I understand correctly, your condition forces the complement of the graph to have the degree of each vertex bounded by $2$. That means the complement graph can have at most $n$ edges, so $G$ has at least $(n^2 - n)/2 - n$ edges. This lower bound can be realized by the complement of an $n$-cycle (for large $n$).2011-11-21

1 Answers 1

1

Here's a quick approach that gives an $\Omega(n^2)$ answer but the bound is not quite as strong as what ccc's comment claims. The main advantage of this approach is its simplicity and generality.

Pick $4$ vertices at random without replacement. Then for any fixed edge $e = xy$ of $G$, we are interested in the probability that $e$ is observed by the sample. Heuristically, we want to sample both $x$ and $y$, so this happens with probability $O(\frac{1}{n^2})$. However, we can also make a more rigorous estimate as follows. Of the four vertices, one of them is $x$ and another is $y$; fixing these positions can be done in $4 \cdot 3$ ways. Once these positions are fixed, the probability that these positions contain $x$ and $y$ respectively is $\frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}$ (assuming $n \geqslant 4)$. Summing over all the $12$ possibilities for the positions (they are all disjoint), the probability that the edge is seen by the sample is $\frac{12}{n(n-1)}$.

Therefore, by linearity of expectations, the expected number of edges within the sample is equal to $\frac{12m}{n(n-1)}$, where $m := |E|$. Lower bounding this by $2$ (since every $4$-tuple of vertices contains a matching), we get $ \frac{12m}{n(n-1)} \geqslant 2 \quad \implies \quad m \geqslant \frac{1}{6} n(n-1). $

  • 0
    Thank you. This lower bound is more than enough for me.2011-11-22