contradiction with expanders and sat?

This is a discussion on contradiction with expanders and sat? within the Theory forums in Theory and Concepts category; 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 ...

Go Back   Application Development Forum > Theory and Concepts > Theory

Object Mix

Register FAQ Calendar Search Today's Posts Mark Forums Read
  #1  
Old 08-30-2008, 12:56 AM
perfectanimezephyr@yahoo.com
Guest
 
Default contradiction with expanders and sat?

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?
Reply With Quote
Reply


Thread Tools
Display Modes


All times are GMT -5. The time now is 03:30 AM.


Powered by vBulletin® Version 3.7.2
Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Search Engine Optimization by vBSEO 3.2.0
vB Ad Management by =RedTyger=

In an effort to better serve ads to our visitors, cookies are used on objectmix.com. For more information, check out our Privacy Policy.