Solution

Under the standard intended reading that the added edges form a perfect matching between

G_{n}

and

H_{n}

, the claim follows as follows. Degrees in

M_{n}

remain bounded in terms of

Δ

. For

A \subseteq V (M_{n})

, write

A_{G} = A \cap V (G_{n})

and

A_{H} = A \cap V (H_{n})

. The matching contributes at least

∣ A_{G} ∣ - ∣ A_{H} ∣

boundary edges, while expansion inside

G_{n}

contributes a constant multiple of

min {∣ A_{G} ∣, n - ∣ A_{G} ∣}

. A case split according as

∣ A_{G} ∣ \leq n /2

∣ A_{G} ∣ > n /2

shows

∣ \partial_{M_{n}} A ∣ \geq c_{α, Δ} min {∣ A ∣, 2 n - ∣ A ∣} .

Thus

M_{n}

π_{m i n} ≍ 1/ n

. The usual spectral mixing estimate, or part (b), then gives

t_{mix} ≲ lo g n

If “adding

n

edges” permits all

G_{n}

vertices to attach to the same vertex of

H_{n}

, the assertion is false as written. Take

H_{n}

to be a path and attach every vertex of the expander to one endpoint. A walk started at the other endpoint needs order

n^{2}

time to reach the attachment endpoint, so its mixing time is not

O (lo g n)

. The perfect-matching interpretation is therefore necessary.

Solved by gpt-5.6-sol high.

 Ancestors (11)

There are no discussions about this article yet.

There are currently no matching articles.