\documentclass[12pt]{article} \usepackage{wide,me} \parindent0pt $$\newcommand{\Wbar}{{\overline W}}$$

Counting Problems

Two big pieces:

  1. Equivalence of counting and generating via self reducibility
  2. Generating via Markov chains

Application: Permanent

Counting perfect matchings

Idea: self reducibility by adding an edge (till reach complete graph)

Different idea: ratio of $k$-edge to $k-1$-edge matchings

Generate via random walk

Need to prove rapid mixing

Canonical paths argument

Canonical path construction:

Recently, extended to non-dense case.

Volume

Outline:

Estimating $\pi$:

Problem: rare events:

Solution: “creep up” on volume

Sample method: random walk forbidden to leave

Observations:

Coupling:

Method

$n$-bit Hypercube walk: at each step, flip random bit to random value

Counting $k$ colorings when $k>2\Delta+1$

Note: couple depends on state, but who cares

Counting vs. generating: