Graph Theory » Probabilistic G.T.

Negative association in uniform forests ★★

Author(s): Pemantle

Conjecture   Let $ G $ be a finite graph, let $ e,f \in E(G) $, and let $ F $ be the edge set of a forest chosen uniformly at random from all forests of $ G $. Then \[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]

Keywords: forest; negative association

Posted by mdevos
updated June 30th, 2008
add new comment
Graph Theory » Basic G.T. » Matchings

Exponentially many perfect matchings in cubic graphs ★★★

Author(s): Lovasz; Plummer

Conjecture   There exists a fixed constant $ c $ so that every $ n $-vertex cubic graph without a cut-edge has at least $ e^{cn} $ perfect matchings.

Keywords: cubic; perfect matching

Posted by mdevos
updated December 15th, 2010
2 comments