0
$\begingroup$

If we want to negate the statement '$\Phi(G)$ is at least $\Omega(\phi)$', the result is usually '$\Phi(G) < c \cdot \phi$ for all $c > 0$'.

However, I found that a contrapositive only indicates that $\Phi(G) < 3\phi$. Would it make the proof lose generality?

Source: EECS 498 FA 21 Theorem 2.9, proof of "$\Rightarrow$".

($\Phi(G)$ is the conductance of a graph $G$)

enter image description here

Improve this question
New contributor
Tyven is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
2
  • 1
    $\begingroup$ the negation is: for all $c > 0$, we have $\Phi(G) < c\cdot \phi$ for infinitely many graphs. idk why you're saying "why is the negation expressed as", as if that's a universal phenomenon. $\endgroup$
    – mathworker21
    Commented yesterday
  • $\begingroup$ I'm sorry for the confusion. I made changes to the question to make it clearer. I'm curious about the technique used for this particular proof. $\endgroup$
    – Tyven
    Commented 20 hours ago

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.