Show that there is no (n, d, ρ)-edge expander for ρ > 0.5

Is this statement even true?
My attempt: Let n = 2, then we can have 2 vertices, A and B. Let d = 1, therefore there is an edge between A and B. As the definition of edge expander says that for every subset of size at most n/2 = 1, the number of edges between S and S complement is atleast ρd|S| = 1, hence, ρ = 1 and edge expander exists. Does there exist a proof for the statement or is my counter example good enough?



Your Answer

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

Browse other questions tagged or ask your own question.