\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.



Estimating $\pi$:

Problem: rare events:

Solution: “creep up” on volume

Sample method: random walk forbidden to leave




$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: