Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## MLSI: Theory, Examples and Consequences

Lecture 3

Prasad Tetali

Georgia Institute of Technology and Indian Institute of Science

ICTS, Bengaluru, August 5-17, 2019

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

1 Discrete curvature and Conjectures

2 SLC and Matroid Bases Exchange

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bochner-Bakry- ´ Emery Criterion

The following 2nd derivative criterion is also useful, and inspires a notion ofdiscrete curvature, mimicking the Ricci curvature.

Proposition (Bochner’46, Lichn´erowicz’58) inff

E(f,f)

Var_{π}f =:λ= inf

f

E(−Lf,f)

E(f,f) =:µ_{P} =:µ .
Proof. λ≤µ: Use Cauchy-Schwartz. Indeed, w/Eπf = 0,

E(f,f) =E(f(−Lf)) ≤

Varπf^{1/2}

E(−Lf)^{2}^{1/2}

≤ 1

√

λ(E(f,f))^{1/2}

E(−Lf)^{2}^{1/2}

= 1

√λ(E(f,f))^{1/2}

E(−Lf,f)1/2

.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bochner-Bakry- ´ Emery Criterion (contd.)

Other direction,λ≥µ: 2nd derivative and integration. Starting with d

dtVar(Htf) =−2E(Htf,Htf) and d

dtE(Htf,Htf) =−2E(Htf,−LHtf). Observe that ast→ ∞, Htf →Eπf, and soE(Htf,Htf)→0. Hence,

E(f,f) = − Z ∞

0

d

dtE(Htf,Htf)dt= 2 Z ∞

0

E(Htf,−L(Htf))dt

= 2

Z ∞

0

E(−L^{∗}(Htf),Htf)dt ≥2µP^{∗}

Z ∞

0

E(Htf,Htf)dt

= −µP^{∗}

Z ∞

0

d

dtVar(H_{t}f)dt=µ_{P}^{∗}Varf,
implying thatλP =λP^{∗}≥µP.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## MLSI and Bakry- ´ Emery Criterion

What about repeating the above for the entropy constant?

Proposition (Bakry- ´Emery’85) inf

f>0

E(f,logf)

Entπf =:α≥inf

f>0

u(f) E(f,logf), where u(f) =E(−Lf,logf) +E(f,(−Lf)/f).

Some relevant references include:

[Boudou, Caputo, Dai Pra, Posta, 2005]. “Spectral gap estimates for interacting particle systems via a Bochner type identity,” J. Funct.

Analysis.

[M. Erbar, J. Maas, P.T. 2015].“Discrete Curvature Bounds for

Bernoulli-Laplace and Random Transposition Models,” Annales Fac. Sci.

Toulouse.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bochner formula (iterated gradient Γ

_{2}

criterion) :

application: discrete Buser ...

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(D−A)

Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V →R, and∀x ∈V,

∆Γ(f,f)(x)−2Γ(f,∆f)(x)≥K Γ(f,f)(x), where

∆f(x) = X

y:(x,y)∈E

(f(y)−f(x)). And givenf,g :V →R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)−f(y))(g(x)−g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = ^{1}_{2}P

y:(x,y)∈E(f(x)−f(y))^{2}=:|∇f(x)|^{2}.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(D−A) Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V →R, and∀x ∈V,

∆Γ(f,f)(x)−2Γ(f,∆f)(x)≥K Γ(f,f)(x),

where

∆f(x) = X

y:(x,y)∈E

(f(y)−f(x)). And givenf,g :V →R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)−f(y))(g(x)−g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = ^{1}_{2}P

y:(x,y)∈E(f(x)−f(y))^{2}=:|∇f(x)|^{2}.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(D−A) Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V →R, and∀x ∈V,

∆Γ(f,f)(x)−2Γ(f,∆f)(x)≥K Γ(f,f)(x), where

∆f(x) = X

y:(x,y)∈E

(f(y)−f(x)). And givenf,g :V →R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)−f(y))(g(x)−g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = ^{1}_{2}P

y:(x,y)∈E(f(x)−f(y))^{2}=:|∇f(x)|^{2}.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bakry- ´ Emery, ... , Schmuckenschl¨ ager,...

G= (V,E), and Graph Laplacian ∆ =−(D−A) Definition [Bochner w/ parameter K]

Curvature ofG is at leastK, if∀f :V →R, and∀x ∈V,

∆Γ(f,f)(x)−2Γ(f,∆f)(x)≥K Γ(f,f)(x), where

∆f(x) = X

y:(x,y)∈E

(f(y)−f(x)). And givenf,g :V →R, also define:

Γ(f,g)(x) = 1 2

X

y:(x,y)∈E

(f(x)−f(y))(g(x)−g(y)).

Note: Γ(f)(x) := Γ(f,f)(x) = ^{1}_{2}P

y:(x,y)∈E(f(x)−f(y))^{2}=:|∇f(x)|^{2}.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

_{2}

Calculus

Equivalently ...

Curvature ofG is at least K, if∀f :V →R, and ∀x∈V, Γ2(f)(x)≥K Γ(f)(x),

where

Γ2(f) := Γ2(f,f) = 1

2∆Γ(f)−Γ(f,∆f).

Basically, using the iterated gradient:

2Γ_{2}(f,g) = ∆Γ(f,g)−Γ(f,∆g)−Γ(∆f,g).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

_{2}

## Calculus

Equivalently ...

Curvature ofG is at least K, if∀f :V →R, and ∀x∈V, Γ2(f)(x)≥K Γ(f)(x),

where

Γ2(f) := Γ2(f,f) = 1

2∆Γ(f)−Γ(f,∆f).

Basically, using the iterated gradient:

2Γ_{2}(f,g) = ∆Γ(f,g)−Γ(f,∆g)−Γ(∆f,g).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

_{2}

Calculus

Equivalently ...

Curvature ofG is at least K, if∀f :V →R, and ∀x∈V, Γ2(f)(x)≥K Γ(f)(x),

where

Γ2(f) := Γ2(f,f) = 1

2∆Γ(f)−Γ(f,∆f). Basically, using the iterated gradient:

2Γ_{2}(f,g) = ∆Γ(f,g)−Γ(f,∆g)−Γ(∆f,g).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

_{2}

## Calculus (contd.)

The iterated gamma can be written out:

2Γ_{2}(f)(x) = ∆Γ(f)(x)−2Γ(f,∆f)(x)

=X

v∼x

Γ(f)(v)−d(x)Γ(f)(x)−X

v∼x

f(v) ∆f(v)−∆f(x)

=X

v∼x

f(v)^{2}

−d(x) 2

X

v∼x

f^{2}(v) + X

u∼v∼x

f^{2}(u)−4f(u)f(v) + 3f^{2}(v)
2

=X

v∼x

f(v)^{2}

−X

v∼x

d(x) +d(v)

2 f^{2}(v) +1
2

X

u∼v∼x

(f(u)−2f(v)2

. (2.1) Ford-regular, further simplifies to:

2Γ2(f)(x) =dX

v∼x

f^{2}(v) + X

v∼x

f(v)^{2}

+X

v∼x

X

u∼v

f^{2}(u)

2 −2f(u)f(v) . (2.2)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

_{2}

Calculus (contd.)

The iterated gamma can be written out:

2Γ_{2}(f)(x) = ∆Γ(f)(x)−2Γ(f,∆f)(x)

=X

v∼x

Γ(f)(v)−d(x)Γ(f)(x)−X

v∼x

f(v) ∆f(v)−∆f(x)

=X

v∼x

f(v)^{2}

−d(x) 2

X

v∼x

f^{2}(v) + X

u∼v∼x

f^{2}(u)−4f(u)f(v) + 3f^{2}(v)
2

=X

v∼x

f(v)^{2}

−X

v∼x

d(x) +d(v)

2 f^{2}(v) +1
2

X

u∼v∼x

(f(u)−2f(v)2

. (2.1)

Ford-regular, further simplifies to: 2Γ2(f)(x) =dX

v∼x

f^{2}(v) + X

v∼x

f(v)^{2}

+X

v∼x

X

u∼v

f^{2}(u)

2 −2f(u)f(v) . (2.2)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Γ

_{2}

## Calculus (contd.)

The iterated gamma can be written out:

2Γ_{2}(f)(x) = ∆Γ(f)(x)−2Γ(f,∆f)(x)

=X

v∼x

Γ(f)(v)−d(x)Γ(f)(x)−X

v∼x

f(v) ∆f(v)−∆f(x)

=X

v∼x

f(v)^{2}

−d(x) 2

X

v∼x

f^{2}(v) + X

u∼v∼x

f^{2}(u)−4f(u)f(v) + 3f^{2}(v)
2

=X

v∼x

f(v)^{2}

−X

v∼x

d(x) +d(v)

2 f^{2}(v) +1
2

X

u∼v∼x

(f(u)−2f(v)2

. (2.1) Ford-regular, further simplifies to:

2Γ2(f)(x) =dX

v∼x

f^{2}(v) + X

v∼x

f(v)^{2}

+X

v∼x

X

u∼v

f^{2}(u)

2 −2f(u)f(v) . (2.2)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Cheeger is tight if curvature ≥ 0

h:=h(G) := min_{A⊂V}|∂A|/|A|, the Cheeger const, ofG;λ >0: gap(G).

Theorem (A-M, L-S, J-S 80’s)
h^{2}

c1maxdeg(G) ≤λ≤c2h. Theorem (Klartag-Kozma-Ralli-T. ’14)

1. Bochner w/ parameter K implies: for any subset A⊂V ,

|∂A| ≥ 1 2minn√

λ, λ

p2|K| o|A|

1− |A|

|V|

.

2. Bochner w/ parameter K ≥0impliesλ≥K , and hence:

λ≤16h^{2}.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## CD(K, ∞ ) with K ≥ 0 : Examples

1. Complete graph Kn: Curvature = 1 +n/2.

2. Discrete n-cube Qn: Curvature = 2.

3. Symmetric group S(n) with the transposition metric:

Curvature = 2

4. General Proposition. If T is the maximum number of triangles containing any edge, then K ≤2 +T/2.

5. Abelian necessary! OnS_{n}, the (left) Cayley graph
generated by (12),(12...n)±1, the Cheeger constant is
c_{1}n^{−2}, while the spectral gap is c_{2}n^{−3}, with c_{1},c_{2}>0,
independent of n.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Cheeger, CD(K, ∞ ) with K ≥ 0

Qn. 1 Can we characterize the graphs or Markov kernels which satisfy non-negative curvature?

Qn. 2 Can we characterize the graphs for which the Cheeger inequality is tight?

Qn. 3 More examples? Non-crossing partition lattice NC(n)?

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Ollivier-Villani

“ In positive curvature, balls are closer than their centers.”

Coarse Ricci: Take two small balls and compute the transportation distance between them. If it is smaller than the distance between the centers of the balls, then coarse Ricci ispositive.

W_{1}(µ_{x}, µ_{y}) =: (1−κ(x,y))d(x,y),
Examples.

1. n-cube: µx uniform on the n+1 neighbors of x (including itself). For x,y, neighbors,κ(x,y) = 2/(n+ 1).

2. Snwith transpositions: Forσ, τ differing in a transposition,
κ(x,y) = 1/ ^{n}_{2}

.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## (Coarse) Ricci of Hypercube

Proposition (folklore)

The n-cube hascoarse Ricci=2/(n+ 1).

Proof sketch.

(i) Consider thelazyrandom walk on then-cube.

(ii) Use a simple (path) coupling argument to show that two copies of
the chain started atneighboring verticesx,y ∈ {0,1}^{n} can be “coupled”

with probability at least 2/(n+ 1) in one step.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## (Coarse) Ricci of Transposition Graph

Proposition

Snwith transpositions has coarse Ricci=1/ ^{n}_{2}
.

Proof sketch.

Lower bound:

(i) Consider thelazyrandom transposition chain onSn.

(ii) Use a simple (path) coupling argument to show that two copies of
the chain started atσ, τ ∈Sn withd(σ, τ) = 1, can be coupled with
probability at least 1/ ^{n}_{2}

in one step.

Upper bound: Follows by showing that there is no better coupling – use
(Kantorovich’s) dual formulation ofW_{1}:

W1(ν, µ) = sup

f: 1−Lip

Eνf −Eµf .

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Peres-Tetali “Conjecture”!

Doescoarse Ricci at least κ >0 imply the MLSI constantα≥κ?

Something weaker is known: namely that aW1 transport-Entropy inequality follows, thanks to(Marton??, Eldan, Lehec, Lee’16)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

MLSI for Bases Exchange Walk

I am thankful to Heng Guo for letting me borrow some of his slides in this section.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Matroid

A matroidM= (E,I) consists of a finite ground setE and a collectionI of subsets ofE (independent sets) such that:

∅ ∈ I;

if S ∈ I,T ⊆S, then T ∈ I (downward closed);

if S,T ∈ I and |S|>|T|, then there exists an element i ∈S\T such thatT ∪ {i} ∈ I (augment axiom).

Maximum independent sets are thebases.

For any two bases, there is a sequence of exchanges of ground set elements that take one basis to the other.

Letn=|E|andr be the rank, namely the size of any basis.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bases-exchange walk

The following Markov chainP_{BX,π} converges to a “homogeneous
SLC”π:

1 remove an element uniformly at random from the current basis (call the resulting set S);

2 addi 6∈S with probability proportional to π(S∪ {i}).

The implementation of the second step may be non-trivial.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## MLSI for Matroid Basis Exchange

Theorem (Mary Cryan-Heng Guo-Giorgos Mousa) For any f : Ω→R≥0,

E_{P}_{BX,π}(f,logf)≥ 1

r ·Ent_{π}(f),
where r is the rank of the matroid.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Many open problems remain!

Sampling spanning trees ofG with no broken circuit- the
same as evaluation TG(1,0) of the Tutte polynomial, leading
coefficient |a_{1}[χ_{G}(λ)]|of the chromatic polynomial (up to
sign), number of maximumG-parking functions, sampling
acyclic orientations with a unique sink...

Sampling all acyclic orientations of G Negative correlation for random forests ofG

(More generally) characterization of matroids with negative correlation for random bases.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Strongly log-concave polynomials

Log-concave polynomial

A polynomialp ∈R≥0[x_{1}, . . . ,x_{n}] is log-concave(atx) if the
Hessian∇^{2}logp(x) is negative semi-definite.

⇒ ∇^{2}p(x) has at most one positive eigenvalue.

Strongly log-concave polynomial

A polynomialp ∈R≥0[x1, . . . ,xn] is strongly log-concaveif for any
index setI ⊆[n],∂_{I}p is log-concave at 1.

Originally introduced byGurvits(2009), equivalent to:

Completely log-concave (Anari, Oveis Gharan, and Vinzant, 2018);

Lorentzian polynomials (Br¨and´en and Huh, 2019+).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Strongly log-concave distributions

A distributionπ: 2^{[n]}→R≥0 is strongly log-concaveif so is its
generating polynomial

g_{π}(x) = X

S⊆[n]

π(S)Y

i∈S

x_{i}.

An important example of homogeneous strongly log-concave distributions is the uniform distribution over bases of a matroid (Anari, Oveis Gharan, and Vinzant 2018; Br¨and´en and Huh 2019+).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Alternative characterization for SLC

Br¨and´en and Huh(2019+): Anr-homogeneous multiaffine

polynomialp with non-negative coefficients isstrongly log-concave if and only if:

the support of p is the bases of some matroid;

after taking r−2 partial derivatives, the quadratic is real stableor 0.

Real stable: p(x)6= 0 if=(x_{i})>0 for alli.

Real stable polynomials (and strongly Rayleigh distributions) capture only “balanced” matroids, whereas SLC polynomials capture all matroids.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bases-exchange walk

The following Markov chainP_{BX,π} converges to a homogeneous
SLCπ:

1 remove an element uniformly at random from the current basis (call the resulting set S);

2 addi 6∈S with probability proportional to π(S∪ {i}).

The implementation of the second step may be non-trivial.

Recall the mixing time defn.

t_{mix}(P, ε) := min

t

t | kP^{t}(x_{0},·)−πk_{TV}≤ε .

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Theorem (Cryan-Guo-Mousa 2019)

For any r -homogeneous strongly log-concave distributionπ,
t_{mix}(P_{BX,π}, ε)≤r

log log 1 πmin

+ log 1
2ε^{2}

,

whereπ_{min}= minx∈Ωπ(x).

Previously,Anari, Liu, Oveis Gharan, and Vinzant(2019):

tmix(PBX,π, ε)≤r

log 1 πmin

+ log1 ε

E.g. for the uniform distribution over bases of matroids (withn
elements and rankr), the new bound is O(r(logr+ log logn)),
whereas the previous bound isO(r^{2}logn).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Levels of independent sets

The set of all independent sets of a matroidMisdownward closed.

LetM(k) be the set of independent sets of size k. Thus,M(r) is the set of all bases.

LetM_{i} denote the matroid Mafter contractingi, which is
another matroid itself.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Weights for independent sets

EquipMwith the following inductively defined weight function:

w(I) :=

(π(I)Zr if|I|=r, P

I^{0}⊃I,|I^{0}|=|I|+1w(I^{0}) if|I|<r,
for some normalization constantZ_{r} >0.

For example, we may choosew(B) = 1 for allB ∈ B andZ_{r} =|B|,
which corresponds to the uniform distribution overB.

Letπk be the distribution such thatπk(I)∝w(I), and Zk be the corresponding normalizing constant.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Different views

Polynomial: _{∂x}^{∂p}

i;settingx_{i} = 0; (r−k)!_{∂x}^{∂}

Ip(1)

Matroid: contraction over i;deletion of i;w(I)

Distribution: conditioning on having i;conditioning on not
having i; proportional toπ_{k}(I)

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Random walk between levels

There are two natural random walks converging toπ_{k}.
The “down-up” random walk P_{k}^{∨}:

→ 1. remove an element of I ∈ M(k) uniformly at random to get
I^{0} ∈ M(k−1);

2. move toJ such thatJ ∈ M(k),J ⊃I^{0} with probability _{w(I}^{w(J)}0).
The bases-exchange walkPBX,π=P_{r}^{∨}.

The “up-down” walk P_{k}^{∧} is defined similarly.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Random walk between levels

There are two natural random walks converging toπ_{k}.
The “down-up” random walk P_{k}^{∨}:

1. remove an element of I ∈ M(k) uniformly at random to get
I^{0} ∈ M(k−1);

→ 2. move toJ such thatJ ∈ M(k),J ⊃I^{0} with probability _{w(I}^{w(J)}0).
The bases-exchange walkPBX,π=P_{r}^{∨}.

The “up-down” walk P_{k}^{∧} is defined similarly.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Decomposing the walks

LetA_{k} be the matrix whose rows are indexed by M(k) and
columns byM(k+ 1) such thatA_{k}(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}_{I∈M(k}_{)}, and
P_{k+1}^{↓} := 1

k+ 1·A^{T}_{k};

P_{k}^{↑} := diag(w_{k})^{−1}A_{k}diag(w_{k+1}).
We have

P_{k}^{∨}_{+1}=P_{k+1}^{↓} P_{k}^{↑};
P_{k}^{∧} =P_{k}^{↑}P_{k+1}^{↓} .

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Decomposing the walks

LetA_{k} be the matrix whose rows are indexed by M(k) and
columns byM(k+ 1) such thatA_{k}(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}_{I∈M(k}_{)}, and
P_{k+1}^{↓} := 1

k+ 1·A^{T}_{k};

P_{k}^{↑} := diag(w_{k})^{−1}A_{k}diag(w_{k+1}).

We have

P_{k}^{∨}_{+1}=P_{k+1}^{↓} P_{k}^{↑};
P_{k}^{∧} =P_{k}^{↑}P_{k+1}^{↓} .

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Decomposing the walks

LetA_{k} be the matrix whose rows are indexed by M(k) and
columns byM(k+ 1) such thatA_{k}(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}_{I∈M(k}_{)}, and
P_{k+1}^{↓} := 1

k+ 1·A^{T}_{k};

P_{k}^{↑} := diag(w_{k})^{−1}A_{k}diag(w_{k+1}).

We have

P_{k}^{∨}_{+1}=P_{k+1}^{↓} P_{k}^{↑};
P_{k}^{∧} =P_{k}^{↑}P_{k+1}^{↓} .

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Decomposing the walks

_{k} be the matrix whose rows are indexed by M(k) and
columns byM(k+ 1) such thatA_{k}(I,J) = 1 if and only ifI ⊂J.

Letwk ={w(I)}_{I∈M(k}_{)}, and
P_{k+1}^{↓} := 1

k+ 1·A^{T}_{k};

P_{k}^{↑} := diag(w_{k})^{−1}A_{k}diag(w_{k+1}).

We have

P_{k}^{∨}_{+1}=P_{k+1}^{↓} P_{k}^{↑};
P_{k}^{∧} =P_{k}^{↑}P_{k+1}^{↓} .

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Key lemma

Lemma

For any k≥2and f :M(k)→R≥0,
Ent_{π}_{k}(f)

k ≥ Ent_{π}_{k−1}(P_{k−1}^{↑} f)
k−1 .

ApplyingP_{k−1}^{↑} to the left corresponds to the random walkP_{k}^{↓}.
The lemma asserts that P_{k}^{↓} contracts the relative entropy by
at least (1−1/k):

Ent_{π}_{k−1}(P_{k−1}^{↑} f)≤(1−1/k)Ent_{π}_{k}(f).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Key lemma

Lemma

For any k≥2and f :M(k)→R≥0,
Ent_{π}_{k}(f)

k ≥ Ent_{π}_{k−1}(P_{k−1}^{↑} f)
k−1 .

ApplyingP_{k−1}^{↑} to the left corresponds to the random walkP_{k}^{↓}.
The lemma asserts that P_{k}^{↓} contracts the relative entropy by
at least (1−1/k):

Ent_{π}_{k−1}(P_{k−1}^{↑} f)≤(1−1/k)Ent_{π}_{k}(f).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Base case

For the base case, we want to show that

Ent_{π}_{2}(f)−2Ent_{π}_{1}(P_{1}^{↑}f)≥0.

Usingalog^{a}_{b} ≥a−b for a,b>0, we can get
Ent_{π}_{2}(f)−2Ent_{π}_{1}(P_{1}^{↑}f)≥1− 1

2Z_{2} ·h^{T}Wh,
whereW_{ij} =w({i,j}) andh=P_{1}^{↑}f.

SinceW = (r−2)!Z_{r}∇^{2}g_{π}(1), it has at most one positive
eigenvalue. The quadratic form is maximized ath =P_{1}^{↑}f =1,
which helps prove the base case...

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Base case

For the base case, we want to show that

Ent_{π}_{2}(f)−2Ent_{π}_{1}(P_{1}^{↑}f)≥0.

Usingalog^{a}_{b} ≥a−b for a,b>0, we can get
Ent_{π}_{2}(f)−2Ent_{π}_{1}(P_{1}^{↑}f)≥1− 1

2Z_{2} ·h^{T}Wh,
whereW_{ij} =w({i,j}) andh=P_{1}^{↑}f.

SinceW = (r−2)!Z_{r}∇^{2}g_{π}(1), it has at most one positive
eigenvalue. The quadratic form is maximized ath =P_{1}^{↑}f =1,
which helps prove the base case...

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Base case

For the base case, we want to show that

Ent_{π}_{2}(f)−2Ent_{π}_{1}(P_{1}^{↑}f)≥0.

Usingalog^{a}_{b} ≥a−b for a,b>0, we can get
Ent_{π}_{2}(f)−2Ent_{π}_{1}(P_{1}^{↑}f)≥1− 1

2Z_{2} ·h^{T}Wh,
whereW_{ij} =w({i,j}) andh=P_{1}^{↑}f.

SinceW = (r−2)!Z_{r}∇^{2}g_{π}(1), it has at most one positive
eigenvalue. The quadratic form is maximized ath=P_{1}^{↑}f =1,
which helps prove the base case...

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Bound the mixing time directly

For a distributionτonM(k), the relative entropyD(τkπk) = Entπ_{k}(D_{k}^{−1}τ) where
Dk= diag(πk). Moreover, after one step ofP_{k}^{∨}, the distribution is

(τ^{T}P_{k}^{∨})^{T}= (P_{k}^{∨})^{T}τ. SinceP_{k}^{∨}is reversible,D_{k}^{−1}(P_{k}^{∨})^{T}=P_{k}^{∨}D_{k}^{−1}.
D (P_{k}^{∨})^{T}τkπk

= Entπ_{k}(D_{k}^{−1}(P_{k}^{∨})^{T}τ)

= Entπ_{k}(P_{k}^{∨}D^{−1}_{k} τ)

= Entπ_{k}(P_{k}^{↓}P_{k−1}^{↑} D_{k}^{−1}τ)

≤Entπ_{k−1}(P_{k−1}^{↑} D_{k}^{−1}τ) (Jensen’s inequality)

≤

1−1 k

Entπ_{k}(D_{k}^{−1}τ) (entropy contraction)

=

1−1 k

D(τ kπk).

The mixing time bound follows from Pinsker’s inequality
2kτ−σk^{2}_{TV}≤D(τkσ).

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

## Many open problems remain!

Sampling spanning trees ofG with no broken circuit- the
same as evaluation TG(1,0) of the Tutte polynomial, leading
coefficient |a_{1}[χ_{G}(λ)]|of the chromatic polynomial (up to
sign), number of maximumG-parking functions, sampling
acyclic orientations with a unique sink...

Sampling all acyclic orientations of G Negative correlation for random forests ofG

(More generally) characterization of matroids with negative correlation for random bases.

Outline Discrete curvature and Conjectures SLC and Matroid Bases Exchange

Fin