| Register | FAQ | Calendar | Search | Today's Posts | Mark Forums Read |
|
#1
| |||
| |||
| I think I am reading a contradiction in a paper I am reading; Am I wrong? "The description of reduction $\tau$ uses special types of expander graphs. The relevant property of these graphs is that for every subset S of the vertices, the number of edges between S and its complement $\overline{S}$ is at least $\min\{|S|,|\overline{S}|\}$. [...] algorithm A constructs in poly(k) time a 14-regular graph $G_k$ on k vertices that is an expander. [...] One of these sets has size at most $m_i/2$; say it is S. In the expander $G_{m_i}$, consider the set of $|S|$ vertices corresponding to [elements] in S. Expansion implies there are at least $|S|+1$ edges leaving this set." Since $|S|\le m_i/2$ we know that in the graph $G_{m_i}$ the cardinality of the complement of the $|S|$ vertices is at least $m_i/ 2$. Therefore $|S|\le |\overline{S}|$. Therefore the number of edges leaving the set of |S| vertices is at least $\min\{|S|,|\overline{S}| \}=|S|$ in an expander graph. So why do the authors state that the number of edges leaving the set of $|S|$ vertices is at least $|S|+1$? Since $|S|\ne |S|+1$, I think this argument is contradictory. in the same way that $a=4 \wedge a>=5$ is unsatisfiable (contradictory). Should I contact one of the authors, if I am right? |
![]() |
| Thread Tools | |
| Display Modes | |
In an effort to better serve ads to our visitors, cookies are used on objectmix.com. For more information, check out our Privacy Policy.