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.

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.

share|improve this question
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$). –  user83827 Nov 21 '11 at 13:21

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
Notice that all we needed was the fact that every induced graph on $4$ vertices contains at least $2$ edges. So, in effect, we are ignoring a lot of structure. –  Srivatsan Nov 21 '11 at 16:25
    
Thank you. This lower bound is more than enough for me. –  Gadi A Nov 22 '11 at 10:37

Your Answer

 
discard

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.