Skip to content

Question about Lemma 1 in "A.2. Proof of Theorem 1" #14

@phucdoitoan

Description

@phucdoitoan

The paper states that Lemma 1 is taken from (Chung, 2007).
However, the closest thing I found in (Chung, 2007) is Lemma 3 ( inequalities (51), (52) ), in which the upper bound contains (beta_k)^2/8 not (lambda_G)^2/2.
I tried to derives Lemma 1 in the paper from Lemma 3 in (Chung, 2007) but have not succeeded.

I would really appreciate if you can provide a proof or point out any sources that lead to the proof of Lemma 1 in the paper.
Thank you!.

(Chung, 2007): Four proofs for the cheeger inequality and graph partition algorithms, ICCM 2007

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions